結果
問題 |
No.2904 Distinct Multisets in a Way
|
ユーザー |
|
提出日時 | 2024-08-21 23:09:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 259 ms / 2,000 ms |
コード長 | 447 bytes |
コンパイル時間 | 440 ms |
コンパイル使用メモリ | 82,336 KB |
実行使用メモリ | 87,760 KB |
最終ジャッジ日時 | 2024-08-21 23:12:21 |
合計ジャッジ時間 | 5,927 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 42 |
ソースコード
MOD=998244353 n=int(input()) inv=[1]*(n+1) fact=[1]*(n+1) factinv=[1]*(n+1) for i in range(2,n+1): inv[i]=pow(i, -1, MOD) fact[i]=fact[i-1]*i fact[i]%=MOD factinv[i]=factinv[i-1]*inv[i] factinv[i]%=MOD ans=0 i=1 while 2*i<=n: tmp=fact[n] tmp*=factinv[i] tmp%=MOD tmp*=factinv[i] tmp%=MOD tmp*=factinv[n-2*i] tmp%=MOD ans+=tmp ans%=MOD i+=1 if n>1: ans*=inv[2] ans%=MOD print(ans)