結果
問題 |
No.1310 量子アニーリング
|
ユーザー |
👑 ![]() |
提出日時 | 2025-08-02 03:07:31 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,155 bytes |
コンパイル時間 | 402 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 105,348 KB |
最終ジャッジ日時 | 2025-08-02 03:07:34 |
合計ジャッジ時間 | 3,100 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 WA * 8 |
ソースコード
""" https://yukicoder.me/problems/no/1310 """ #逆元 def inverse(a,mod): #aのmodを法にした逆元を返す return pow(a,mod-2,mod) #modのn!と、n!の逆元を格納したリストを返す(拾いもの) #factorialsには[1, 1!%mod , 2!%mod , 6!%mod… , n!%mod] が入っている #invsには↑の逆元が入っている def modfac(n, MOD): f = 1 factorials = [1] for m in range(1, n + 1): f *= m f %= MOD factorials.append(f) inv = pow(f, MOD - 2, MOD) invs = [1] * (n + 1) invs[n] = inv for m in range(n, 1, -1): inv *= m inv %= MOD invs[m - 1] = inv return factorials, invs def modnCr(n,r): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる) return fac[n] * inv[n-r] * inv[r] % mod mod = 998244353 N = int(input()) fac,inv = modfac(N+10,mod) ans = 0 two = [1] for i in range(N+10): two.append(two[-1]*2 % mod) for diff in range(0,N,2): same = N - diff E = -(same-diff) ans += two[abs(E)] * modnCr(N,diff) * 2 ans %= mod print (ans % mod)