TopCoder SRM 704 Div2 Hard ModEquationEasy

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];
	}
}

まとめ

どうりで正答者多め。