{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n\t\t\t\n\t\t\t\u003ch3\u003e問題\u003c/h3\u003e\r\n\r\n\u003cp\u003e\r\nUinny は言わずと知れた自作ポエムを共有するツールである。\r\nこのソフトウェアを使ってポエムを共有するためには、まずポエムを Uinny に登録し、そのポエムから計算することができるハッシュと呼ばれる文字列を、有名な掲示板に投稿する必要がある(ここまでの作業を放流と呼ぶ)。ポエムを読みたいと思った人は、そのハッシュを Uinny に打ち込むことにより、自動的にポエムがダウンロードされるという仕組みになっている。\r\nあなたは HAIKU と呼ばれる一種のポエムを創作するのが趣味である。\r\nHAIKU とは小文字アルファベットを50文字以下で繋げた短い並びに、自然の美しさ、恋の辛さ、人生の儚さ、などの思いを託した芸術作品である。\r\nあなたは素晴らしい HAIKU を幾度も放流した実績により、掲示板では神と呼ばれるほどの名声を確立していた。\r\nところがある日、公開した HAIKU の評判をみようと掲示板を開くと、自分に対する罵詈雑言が大量に投稿されている事に気づいた。\r\nどうやら自分が公開したハッシュが他の有名な作品のハッシュと同じものとなってしまい、自分が盗作、著作権法違反をしたかのような扱いとなっているのだ。\r\nたまたま同じハッシュが生成されただけで、自分の本当の作品は別にあると主張したが、掲示板の匿名ユーザーは聞く耳を持ってくれない。\r\nそこであなたは同じハッシュを持つ複数の HAIKU を生成することで、このような現象は起こりうるのだと立証することにした。\r\nUinny の技術という本によると、ある HAIKU \u003cvar\u003e\\(s\\)\u003c/var\u003e のハッシュ \u003cvar\u003e\\(h\\)\u003c/var\u003e は、\r\n\u003c/p\u003e\r\n\r\n\u003cpre\u003e\r\nh \u003d 0\r\nfor i\u003d0,...|s|-1\r\n h \u003d (h * a + (s[i] - \u0027a\u0027 + 1)) % b\r\n\u003c/pre\u003e\r\n\r\n\u003cp\u003e\r\nとして計算されるようだ、\r\nただしここで、 s[i] は \u003cvar\u003e\\(s\\)\u003c/var\u003eの\u003cvar\u003e\\(i\\)\u003c/var\u003e番目の文字を表し、(s[i] - \u003ccode\u003ea\u003c/code\u003e + 1) は、s[i]\u003d\u003ccode\u003ea\u003c/code\u003eならば 1 であり、s[i]\u003d\u003ccode\u003ez\u003c/code\u003e ならば 26 となる式である。\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\na と b の値はプログラムを解析すると簡単にわかるらしい。\r\nさあ、同じハッシュを持つ HAIKU を大量に生成して、自分の容疑が冤罪であると立証するのだ!\r\n\u003c/p\u003e\r\n\r\n\u003chr\u003e\r\n\r\n\u003ch3\u003e入力\u003c/h3\u003e\r\n\r\n\u003cp\u003e\r\n1 行に数値\u003cvar\u003e\\(a\\)\u003c/var\u003e \u003cvar\u003e\\(b\\)\u003c/var\u003eが空白区切りで与えられる。\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003e出力\u003c/h3\u003e\r\n\r\n\u003cp\u003e\r\nハッシュが同じ,すべて小文字アルファベットの,互いに異なる文字列(長さは50まで) を最大 100 個、それぞれ 1 行に 1 個ずつ出力せよ.\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003e制約\u003c/h3\u003e\r\n\r\n\u003cul\u003e\r\n\u003cli\u003e \u003cvar\u003e\\(b \\leq 10^9\\)\u003c/var\u003e, \u003cvar\u003e\\(26 \\leq a \\lt b \\)\u003c/var\u003e\u003c/li\u003e\r\n\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003e部分点\u003c/h3\u003e\r\n\r\n\u003cp\u003e\r\n出力できた文字列の個数を\u003cvar\u003e\\(n\\)\u003c/var\u003eとしたとき,各テストケースごとに,\u003cvar\u003e\\(n\\)\u003c/var\u003e% の点が入る.\r\nすなわち,以下のようにしてこの問題の点数は計算される.\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nテストケース数を \u003cvar\u003e\\(N\\)\u003c/var\u003e とする.\r\n\u003cvar\u003e\\(i\\)\u003c/var\u003e番目のテストケースのスコア\u003cvar\u003e\\(s_i\\)\u003c/var\u003e を,出力した文字列の個数として定める.\r\nただし,誤答の場合や,100より多くの文字列を出力した場合は,\r\n\u003cvar\u003e\\(s_i \u003d 0\\)\u003c/var\u003e となる.\r\nすべての\u003cvar\u003e\\(s_i\\)\u003c/var\u003eの総和を\u003cvar\u003e\\(S\\)\u003c/var\u003eとしたとき,\r\nこの問題の点数として,\u003cvar\u003e\\(2S/N\\)\u003c/var\u003e 点が与えられる.\r\n\u003c/p\u003e\r\n\r\n\u003chr\u003e\r\n\r\n\u003ch3\u003e入力例 1\u003c/h3\u003e\r\n\r\n\u003cpre\u003e\r\n26 52\r\n\u003c/pre\u003e\r\n\r\n\u003ch3\u003e入力例 1 に対する出力例\u003c/h3\u003e\r\n\r\n\u003cpre\u003e\r\naaz\r\nbaz\r\ncaz\r\ndaz\r\neaz\r\nfaz\r\ngaz\r\nhaz\r\niaz\r\njaz\r\nkaz\r\nlaz\r\nmaz\r\nnaz\r\noaz\r\npaz\r\nqaz\r\nraz\r\nsaz\r\ntaz\r\nuaz\r\nvaz\r\nwaz\r\nxaz\r\nyaz\r\nzaz\r\naaaz\r\nabaz\r\nacaz\r\nadaz\r\naeaz\r\nafaz\r\nagaz\r\nahaz\r\naiaz\r\najaz\r\nakaz\r\nalaz\r\namaz\r\nanaz\r\naoaz\r\napaz\r\naqaz\r\naraz\r\nasaz\r\nataz\r\nauaz\r\navaz\r\nawaz\r\naxaz\r\nayaz\r\nazaz\r\nbaaz\r\nbbaz\r\nbcaz\r\nbdaz\r\nbeaz\r\nbfaz\r\nbgaz\r\nbhaz\r\nbiaz\r\nbjaz\r\nbkaz\r\nblaz\r\nbmaz\r\nbnaz\r\nboaz\r\nbpaz\r\nbqaz\r\nbraz\r\nbsaz\r\nbtaz\r\nbuaz\r\nbvaz\r\nbwaz\r\nbxaz\r\nbyaz\r\nbzaz\r\ncaaz\r\ncbaz\r\nccaz\r\ncdaz\r\nceaz\r\ncfaz\r\ncgaz\r\nchaz\r\nciaz\r\ncjaz\r\nckaz\r\nclaz\r\ncmaz\r\ncnaz\r\ncoaz\r\ncpaz\r\ncqaz\r\ncraz\r\ncsaz\r\nctaz\r\ncuaz\r\ncvaz\r\n\u003c/pre\u003e\r\n\n\t\t"}}]}