結果
問題 |
No.2437 Fragile Multiples of 11
|
ユーザー |
|
提出日時 | 2023-08-11 21:03:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,610 ms / 2,000 ms |
コード長 | 1,189 bytes |
コンパイル時間 | 378 ms |
コンパイル使用メモリ | 82,152 KB |
実行使用メモリ | 141,636 KB |
最終ジャッジ日時 | 2024-11-18 14:58:28 |
合計ジャッジ時間 | 28,317 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 34 |
ソースコード
N=int(input()) X=input() X=list(map(lambda x: int(x),X)) mod=998244353 dp0 = [[[0]* 11 for _ in range(2**11) ] for _ in range(N)] dp1 = [[[0]* 11 for _ in range(2**11) ] for _ in range(N)] for i in range(1,int(X[0])): dp0[0][1][i]=1 dp1[0][1][int(X[0])]=1 for i in range(N-1): for S in range(2**11): for k in range(11): n_bit=0 for l in range(11): if S>>l&1: n_bit|= 1<<(l*10)%11 for l in range(10): nxt_bit=(n_bit|(1<<k)) dp0[i+1][nxt_bit][(k*10+l)%11]= (dp0[i+1][nxt_bit][(k*10+l)%11]+dp0[i][S][k])%mod if l<X[i+1]: dp0[i+1][nxt_bit][(k*10+l)%11]= (dp0[i+1][nxt_bit][(k*10+l)%11]+dp1[i][S][k])%mod elif l==X[i+1]: dp1[i+1][nxt_bit][(k*10+l)%11]= (dp1[i+1][nxt_bit][(k*10+l)%11]+dp1[i][S][k])%mod n_bit<<=1 if ((n_bit>>11)&1): n_bit^=((1<<11) | 1) for l in range(1,10): dp0[i+1][1][l]=(dp0[i+1][1][l]+1)%mod ans=0 for S in range(2**11): if S&1: continue ans=(ans+dp0[N-1][S][0]+dp1[N-1][S][0])%mod print(ans)