問題 2以上の整数bと、1以上の整数nに対し、関数f(b,n)を以下のように定める。 n n >= bのとき、f(b, n) = f(b, floor(n/b)) + (n mod b) これは、直感的には、nをb進表記したときの各桁の和を表す。整数nとsが与えられる。f(b, n)=sとなる2以上の整数bの最…

問題 整数N, Mが与えられる。 a_1 * a_2 * ... * a_N = Mであるような、長さNの数列aの何通りあり得るか10^9+7で割ったあまりで答えよ。 ただし、数列aとbが異なるとは、あるiが存在してa_i != b_iであることをいう。 制約 1 1 解法 (約数を列挙したDPや行列…

問題 3つの文字列a,b,cが与えられる。 これらの文字列は、以下の方法で作られたことがわかっている。 ある文字列sがあり、その連続部分文字列tを取り出す tのいくつかの文字を'?'に置き換える このとき、元の文字列sの長さとして考えられる最小の長さを求め…

問題 長さNの、英小文字からなる文字列を考える。 ある文字列sとtは、以下の条件の時「同型」という。 |s| = |t| 任意のi,jに対して以下のいずれかが成り立つ s[i]==s[j] かつ t[i]==t[j] s[i]!=s[j] かつ t[i]!=t[j] また、文字列の標準形とは、 任意のsと…