Codeforces ECR #148 : E. Combinatorics Problem

一転してこっちは短い。
https://codeforces.com/contest/1832/problem/E

問題

整数列Aが与えられる。
を求めよ。

解法

グリッド上の遷移を考えると、初期状態で(x,0)に到達するパターンがA(x)あるとき、右または上の格子点への移動を繰り返して(i,K)に到達するパターンの総和がB(i)となる。
よって(0,0)-(i,K)への遷移パターンをDPで数え上げて行けばよい。

int N;
ll A[10101011][6];
const ll mo=998244353;
ll X,Y,M,K;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A[1][0]>>X>>Y>>M>>K;
	for(i=2;i<=N;i++) A[i][0]=(A[i-1][0]*X+Y)%M;
	FOR(y,6) FOR(x,N+5) {
		if(x) A[x][y]+=A[x-1][y];
		if(y) A[x][y]+=A[x][y-1];
		if(A[x][y]>=mo) A[x][y]-=mo;
	}
	
	ll ret=0;
	for(i=1;i<=N;i++) if(i-(K-1)>=0) ret^=A[i-(K-1)][K]*i;
	cout<<ret<<endl;
	
}

まとめ

グリッド上の処理を思いつければあとは簡単。