これAC数妙に少ないのなんでだろ。
https://yukicoder.me/problems/no/1815
問題
N*Mのグリッドの各セルをK色で塗り分ける。
隣接セルが同色にならない、かつK色すべてが1回以上使われる塗り方は何通りか。
解法
f(k) := k色以下を使い塗り分ける塗り方
とすると、解はとなる。
あとはf(k)を求めよう。
左端の列の色を定めると、
- N=1の時、右隣の列の色の組み合わせは(K-1)通り
- N=2の時、右隣の列の色の組み合わせは( (K-2)^2+(K-1) )通り
- N=3の時、最上段と最下段の色が等しい場合と異なる場合それぞれにおいて、右隣の列の色の組み合わせを考えよう。あとは行列累乗の要領で全体の数を数え上げられる。
- 右隣の列の色の組み合わせは、以下のコードではDFSで頑張っているが、数式で計算することもできるようだ。
int N; ll M,K; const ll mo=1000000007; const int NUM_=400001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; ll comb(ll N_, ll C_) { if(C_<0 || C_>N_) return 0; return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo; } ll P(ll N_, ll C_) { if(C_<0 || C_>N_) return 0; return factr[N_-C_]*fact[N_]%mo; } const int MAT=2; struct Mat { ll v[MAT][MAT]; Mat(){ZERO(v);};}; Mat mulmat(Mat& a,Mat& b,int n=MAT) { ll mo2=4*mo*mo; int x,y,z; Mat r; FOR(x,n) FOR(y,n) r.v[x][y]=0; FOR(x,n) FOR(z,n) FOR(y,n) { r.v[x][y] += a.v[x][z]*b.v[z][y]; if(r.v[x][y]>mo2) r.v[x][y] -= mo2; } FOR(x,n) FOR(y,n) r.v[x][y]%=mo; return r; } Mat powmat(ll p,Mat a,int n=MAT) { int i,x,y; Mat r; FOR(x,n) FOR(y,n) r.v[x][y]=0; FOR(i,n) r.v[i][i]=1; while(p) { if(p%2) r=mulmat(r,a,n); a=mulmat(a,a,n); p>>=1; } return r; } void dfs(vector<int> V,Mat& A,int K) { int ma=*max_element(ALL(V))+1; if(V.size()==6) { if(V[0]==V[3]) return; if(V[1]==V[4]) return; if(V[2]==V[5]) return; if(V[3]==V[4]) return; if(V[4]==V[5]) return; int x=V[0]==V[2]; int y=V[3]==V[5]; if(x) A.v[y][x]+=P(K-2,ma-2); else A.v[y][x]+=P(K-3,ma-3); } else { int i; FOR(i,ma+1) { V.push_back(i); dfs(V,A,K); V.pop_back(); } } } ll hoge(ll K) { Mat A; ll ret; if(N==1) { A.v[0][0]=K-1; A=powmat(M-1,A); ret=K*A.v[0][0]%mo; } else if(N==2) { A.v[0][0]=((K-2)*(K-2)+K-1)%mo; A=powmat(M-1,A); ret=K*(K-1)%mo*A.v[0][0]%mo; } else { dfs({0,1,0},A,K); dfs({0,1,2},A,K); int x,y; FOR(x,2) FOR(y,2) A.v[y][x]%=mo; A=powmat(M-1,A); ll XYX=K*(K-1)%mo; ll XYZ=K*(K-1)%mo*(K-2)%mo; ret=XYZ*(A.v[0][0]+A.v[1][0])+XYX*(A.v[0][1]+A.v[1][1]); } return ret%mo; } void solve() { int i,j,k,l,r,x,y; string s; inv[1]=fact[0]=factr[0]=1; for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo; for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo; cin>>N>>M>>K; ll ret=0; for(i=1;i<=K;i++) { ll a=hoge(i)*comb(K,i)%mo; if((K-i)%2) { ret+=mo-a; } else { ret+=a; } } cout<<ret%mo<<endl; }
まとめ
DFS部分が地味に面倒だった。