結果
問題 | No.1310 量子アニーリング |
ユーザー |
|
提出日時 | 2020-12-07 22:50:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 59 ms / 2,000 ms |
コード長 | 1,245 bytes |
コンパイル時間 | 587 ms |
コンパイル使用メモリ | 70,272 KB |
実行使用メモリ | 6,400 KB |
最終ジャッジ日時 | 2024-09-17 14:05:17 |
合計ジャッジ時間 | 1,470 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include<iostream>#include<vector>using namespace std;typedef long long ll;const ll mod = 998244353;ll modpow(ll a, ll b, ll p = mod){if(b == 0) return 1;if(b % 2 == 0){ll d = modpow(a, b/2, p);return (d*d) % p;}else{return (a%p * modpow(a, b-1, p)) % p;}}struct ModComb{vector<ll> po, inv;ll N;ModComb(ll n) : N(n), po(n), inv(n) {po[0] = 1;for(int i = 1; i < N; i++) po[i] = (po[i-1] * i) % mod;inv[N-1] = modpow(po[N-1], mod-2, mod);for(int i = N-2; i >= 0; i--) inv[i] = (inv[i+1] * (i+1)) % mod;}ll nCk(ll n, ll k){if(k == 0) return 1;if(n < k) return 0;return (((po[n]*inv[n-k])%mod)*inv[k])%mod;}ll nPk(ll n, ll k){if(k == 0) return 1;if(n < k) return 0;return (po[n]*inv[n-k])%mod;}ll nHk(ll n, ll k){if(n == 0 && k == 0) return 1;return nCk(n+k-1, k-1);}};int main(){int n;cin >> n;ModComb mc(n+1);ll ans = 0;for(int i = 0; i <= n; i += 2){ans += mc.nCk(n, i)*modpow(2,abs(n-2*i),mod)%mod*2%mod;ans %= mod;}cout << ans << endl;return 0;}