実装は短いんだよな。
https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_f
問題
H*Wのグリッドがある。
このグリッドはトーラス上になっており、左と右、上と下がつながっているものとする。
各マスに、時刻1毎に右マスに移動・下マスに移動・移動しないのいずれかを行うロボットを配置したとする。
正整数Tに対し、Tの整数倍の時間が経った段階で全マスにロボットが1体だけいるようなロボの配置は何通りか。
解法
各ロボ、T毎に右にGCD(W,T)または下にGCD(H,T)に移動すると考えても問題ない。
また、盤面を横GCD(W,T)個、縦GCD(H,T)毎に独立に考えてよい。
よって、幅W'=W/GCD(W,T)、高さH'=H/GCD(H,T)の盤面の組み合わせを考えよう。そうするとT=1と仮定して問題ないことになる。
この結果に対し、GCD(W,T)*GCD(H,T)乗すれば求める解となる。
下移動または停止のみの場合を考えると、下移動のロボがいる列は皆同じく下に移動しなければならない。
右に関しても同じ。
1体も動かないケースの重複を除くと、ここまで(2^H')+(2^W')-1通り。
右と下が最低1体ずついるケースを考えよう。
各マスにおいて、1つ左下または1つ右上にあるマスは同グループと考えよう。
このグループ内のロボットは、皆右か下揃って移動しないといずれグループ内のロボが衝突する。
また、移動しないロボがいると、(全体が停止していない限り)いずれどこかで衝突が起きる。
この時のグループはGCD(H',W')通りに分けられる。全グループが右または下に移動するケースを除くと、2^(GCD(H',W'))-2通り。
よって全部合わせると*1-3)^(GCD(W,T)*GCD(H,T))通り。
int H,W,T; ll mo=1000000007; ll modpow(ll a, ll n = mo-2) { ll r=1;a%=mo; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } ll hoge(int H,int W) { ll ret=0; ret=modpow(2,H)+modpow(2,W)+mo-1; ret+=modpow(2,__gcd(H,W))+mo-2; return ret%mo; } void solve() { int i,j,k,l,r,x,y; string s; cin>>H>>W>>T; ll HP=__gcd(T,H); ll WP=__gcd(T,W); ll ret=hoge(H/HP,W/WP); ret=modpow(ret,HP*WP)%mo; cout<<ret<<endl; }
まとめ
Eで時間食い過ぎたのがいかんなぁ。
*1:2^H')+(2^W')+2^(GCD(H',W'
