yukicoder : No.2144 MM

なるほど…。
https://yukicoder.me/problems/no/2144

問題

整数Mと、各要素0以上(M-2)以下のN要素からなる整数列Aが与えられる。
Aのうち隣接する2要素をそれぞれインクリメントすることを繰り返し、Aの各要素をMの倍数にできるか。
できるなら、そのような数列のうち入力の数列は辞書順で何番目かを答えよ。

解法

Mの倍数にできるかどうかは、先頭の要素からMの倍数にすることを考えれば容易に判定できる。
問題は後者。

この数列を(M-1)進数と考えると、隣接する2要素に1を足すことは、(M-1)進数の値にあるMの倍数を加算することに相当する。
よって、この数列が(M-1)進数表記した場合にMの倍数の中で何番目かを求めればよい。
これは、(M-1)進数表記した値をMで割って1足せば求まる。

int N,M;
int A[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>>N>>M;
	ll S=0;
	FOR(i,N) {
		cin>>A[i];
		if(i%2==0) S+=A[i];
		else S-=A[i];
	}
	if(S%M) {
		cout<<-1<<endl;
		return;
	}
	ll num=0;
	FOR(i,N) num=(num*(M-1)+A[i])%mo;
	cout<<(num*modpow(M)+1)%mo<<endl;
}

まとめ

自分は消えロールが苦手なのでMVまでしか出ません。