900ptということで簡単。
https://community.topcoder.com/stat?c=problem_statement&pm=14467
問題
整数N,K,vが与えられる。
各要素0~(K-1)のいずれかの整数をとるN要素の数列X[i]のうち、全要素の積をとったとき、Kで割った余りがvとなるのは何通りあるか。
解法
Kが小さいので、行列乗算に持ちもこう。
以下のベクトルを考える。
f(n) = Xのうちn要素まで積をとったとき、積をKで割った余りが0~(K-1)となる組み合わせ。
以下の行列を考えると、下記のように行列累乗に持ち込める。
A[i][j] = 0~(K-1)のうち、(i-1)と掛け合わせてKで割った余りが(j-1)となるような値の個数
const int MAT=100; ll G[MAT][MAT],G2[MAT][MAT]; ll mo=1000000007; void powmat(ll p,int n,ll a[MAT][MAT],ll r[MAT][MAT]) { int i,x,y,z; ll a2[MAT][MAT]; FOR(x,n) FOR(y,n) a2[x][y]=a[x][y]; FOR(x,n) FOR(y,n) r[x][y]=(x==y); while(p) { ll h[MAT][MAT]; if(p%2) { FOR(x,n) FOR(y,n) h[x][y]=0; FOR(x,n) FOR(z,n) FOR(y,n) h[x][y] += (r[x][z]*a2[z][y]) % mo; FOR(x,n) FOR(y,n) r[x][y]=h[x][y]%mo; } FOR(x,n) FOR(y,n) h[x][y]=0; FOR(x,n) FOR(z,n) FOR(y,n) h[x][y] += (a2[x][z]*a2[z][y]) % mo; FOR(x,n) FOR(y,n) a2[x][y]=h[x][y]%mo; p>>=1; } } class ModEquationEasy { public: int count(int n, int K, int v) { int i,j; ZERO(G); FOR(i,K) FOR(j,K) G[i][i*j%K]++; powmat(n,K,G,G2); return G2[1][v]; } }
まとめ
どうりで正答者多め。