kmjp's blog

競技プログラミング参加記です

AtCoder ABC #156 : F - Modularness

妙な数式が見えて一瞬びっくりするけどそうでもなかった。
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;
		
	}
}

まとめ

さてもうすぐだ…。