結果
問題 | No.2653 [Cherry 6th Tune] Re: start! (Make it Zero!) |
ユーザー |
![]() |
提出日時 | 2024-02-23 22:54:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 408 ms / 2,000 ms |
コード長 | 887 bytes |
コンパイル時間 | 1,036 ms |
コンパイル使用メモリ | 82,084 KB |
実行使用メモリ | 119,656 KB |
最終ジャッジ日時 | 2024-09-29 08:10:17 |
合計ジャッジ時間 | 15,567 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 72 |
ソースコード
Q=int(input()) for _ in range(Q): N,M=map(int,input().split()) A=list(map(int,input().split())) L=[] mod=M for i in range(N): if A[i]==-1: L.append(i) if len(L)==0: if (sum(A))%M!=0: print(0) else: result=N x=0 for i in range(N): x+=A[i] x%=mod if x==0: result-=1 print(result) continue mod=998244353 count=len(L) p1=pow(M,count-1,mod) p2=pow(M,count-2,mod) result=p1*N result%=mod pos=L[0] x=0 for i in range(pos): x+=A[i] x%=M if x==0: result-=p1 result%=mod for i in range(len(L)-1): pos1=L[i] pos2=L[i+1] result-=(pos2-pos1)*p2 result%=mod T={} T[0]=1 x=0 pos=L[-1] for i in range(pos+1,N): x+=A[i] x%=M if not x in T: T[x]=1 else: T[x]+=1 result-=T[x]*p1 result%=mod print(result)