結果

問題 No.2653 [Cherry 6th Tune] Re: start! (Make it Zero!)
ユーザー 沙耶花
提出日時 2024-02-23 22:53:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 100 ms / 2,000 ms
コード長 1,106 bytes
コンパイル時間 5,090 ms
コンパイル使用メモリ 250,440 KB
最終ジャッジ日時 2025-02-19 20:26:42
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 72
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000001
#define Inf64 1000000000000000001


int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int _t;
	cin>>_t;
	
	rep(_,_t){
		int N,M;
		cin>>N>>M;
		vector<int> a(N);
		long long s = 0;
		long long f = 0;
		rep(i,N){
			cin>>a[i];
			if(a[i]==-1){
				f ++;
			}
			else{
				s += a[i];
			}
			
		}
		s %= M;
		mint ans = 0;
		if(f){
			mint t = mint(M).pow(f-1);
			ans = t;
		}
		else{
			if(s!=0){
				cout<<0<<endl;
				continue;
			}
			ans = 1;
			
		}
		ans *= N-1;
		
		long long sx = 0,sy = 0,fx = 0,fy = 0;
		sy = s,fy = f;
		rep(i,N-1){
			if(a[i]==-1){
				fx ++;
				fy --;
			}
			else{
				sx += a[i];
				sy -= a[i];
				sy += M;
				sx %= M;
				sy %= M;
			}
			mint t = 1;
			if(sx!=0&&fx==0)continue;
			if(sy!=0&&fy==0)continue;
			if(fx>0)t *= mint(M).pow(fx-1);
			if(fy>0)t *= mint(M).pow(fy-1);
			ans -= t;
		}
		
		cout<<ans.val()<<endl;
	}
	
	return 0;
}
0