妙な数式が見えて一瞬びっくりするけどそうでもなかった。
https://atcoder.jp/contests/abc156/tasks/abc156_f
問題
K要素の整数列Dが与えられる。
N,X,Mの3値で構成されたクエリが与えられるので、以下答えよ。
- A[0] = X
- A[i+1] = A[i]+D[i%K]
となるN要素の数列Aを考える。
A[i]%M<A[i+1]%Mとなるiは何通りか。
解法
A[i]%M=A[i+1]%Mとなるケースと、A[i]%M>A[i+1]%Mとなるケースを引くことを考える。
まず、E[i]=D[i]%Mとし、A[i+1] = A[i]+E[i%K]としても解に影響しないので、以後DではなくこのEを用いる。
- A[i]%M=A[i+1]%Mとなるケース
- これはE[i%K]=0となるケースを数えれば済む
- A[i]%M>A[i+1]%Mとなるケース
- Aの初項をX、末尾をYとする。E[i]はM未満なので、A[i]%M>A[i+1]%Mとなるのはfloow(Y/M)-floow(X/M)回である。
よってそれぞれを求めればよい。
int K,Q; int D[5050],E[5050]; ll N,X,M,S; void solve() { int i,j,k,l,r,x,y; string s; cin>>K>>Q; FOR(i,K) cin>>D[i]; while(Q--) { cin>>N>>X>>M; ll S=0; ll num0=0; FOR(i,K) { E[i]=D[i]%M; S+=E[i]; if(E[i]==0) num0++; } ll Y=X+(N-1)/K*S; num0*=(N-1)/K; FOR(i,(N-1)%K) { Y+=E[i]; if(E[i]==0) num0++; } ll rev=(Y/M-X/M); cout<<N-1-rev-num0<<endl; } }
まとめ
さてもうすぐだ…。