結果
問題 | No.2653 [Cherry 6th Tune] Re: start! (Make it Zero!) |
ユーザー |
|
提出日時 | 2024-02-23 22:23:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 42 ms / 2,000 ms |
コード長 | 790 bytes |
コンパイル時間 | 991 ms |
コンパイル使用メモリ | 77,672 KB |
実行使用メモリ | 6,524 KB |
最終ジャッジ日時 | 2024-09-29 07:15:49 |
合計ジャッジ時間 | 5,660 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 72 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>#include<cassert>#include<atcoder/modint>using namespace std;using mint=atcoder::modint998244353;int M;vector<mint>solve(vector<int>X){vector<mint>L(X.size()+1);L[0]=1;int emp=0;mint coef=1;int sum=0;for(int i=0;i<X.size();i++){if(X[i]==-1){if(emp>0)coef*=M;emp++;}else sum=(sum+X[i])%M;if(emp>0)L[i+1]=coef;else if(sum==0)L[i+1]=1;}return L;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin>>T;for(;T--;){int N;cin>>N>>M;vector<int>X(N);for(int i=0;i<N;i++)cin>>X[i];vector<mint>L=solve(X);reverse(X.begin(),X.end());vector<mint>R=solve(X);mint ans=L[N]*(N-1);for(int i=1;i<N;i++)ans-=L[i]*R[N-i];cout<<ans.val()<<"\n";}}