yukicoder : No.2653 [Cherry 6th Tune] Re: start! (Make it Zero!)

これはどうにか解けたな。
https://yukicoder.me/problems/no/2653

問題

N要素の整数列Aと正整数Mがあったとする。
隣接する2要素を選び、その和を取ってMで割った余りに置き換える作業を繰り返し、Aの全要素を0にできたとする。
その時のスコアは、置き換え作業の最小値とする。
全要素を0にできない場合、スコアは0となる。

今Aが与えられる。ただし一部の要素は不定で0～(M-1)のいずれかが入るとする。
あり得るAのスコアの総和を求めよ。

解法

Aのprefix sumをBとする。
sum(B)%M=0かつB[i] % M != 0の場合、解が1増加する。
よってiを総当たりすることを考える。

• B[i]%M!=0となるのは:
  • A[i]以前に不定の箇所がn個(＞0)の場合、B[i]%M!=0となるのはM^(n-1)*(M-1)通りである。
  • A[i]以前に不定の箇所が0個の場合、B[i]%M=0となるかは実際にB[i]を計算すればよい。
• sum(B)%M=0となるのは:
  • A[i]以降に不定の箇所がn個(＞0)の場合、B[i]%M!=0となるのはM^(n-1)通りである。
  • A[i]以降に不定の箇所が0個の場合、sum(B)%M=0となるかは実際にB[i]を計算すればよい。

int T;
ll N,M;
ll X[202020],S[202020];
int NZ[202020];
const ll mo=998244353;

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;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		int nm=0;
		cin>>N>>M;
		ll sum=0;
		FOR(i,N) {
			cin>>X[i];
			S[i+1]=S[i]+X[i];
			NZ[i+1]=NZ[i];
			if(X[i]==-1) NZ[i+1]++;
		}
		if(NZ[N]==0) {
			int ret=0;
			if(S[N]%M==0) {
				FOR(i,N) {
					if(S[i+1]%M) ret++;
				}
			}
			cout<<ret<<endl;
			continue;
		}
		sum=0;
		ll ret=0;
		for(i=1;i<N;i++) {
			if(NZ[i]==0) {
				if(S[i]%M) ret+=modpow(M,NZ[N]-1);
			}
			else if(NZ[N]-NZ[i]==0) {
				if((S[N]-S[i])%M) ret+=modpow(M,NZ[N]-1);
			}
			else {
				(ret+=(M-1)*modpow(M,NZ[N]-2))%=mo;
			}
		}
		
		
		cout<<ret%mo<<endl;
	}
}

まとめ

大げさに見えて、意外に場合分けは単純。