結果
問題 | No.1310 量子アニーリング |
ユーザー |
![]() |
提出日時 | 2020-12-07 04:03:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 47 ms / 2,000 ms |
コード長 | 1,513 bytes |
コンパイル時間 | 957 ms |
コンパイル使用メモリ | 117,428 KB |
最終ジャッジ日時 | 2025-01-16 18:52:28 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include<iostream>#include<string>#include<algorithm>#include<vector>#include<iomanip>#include<math.h>#include<complex>#include<queue>#include<deque>#include<stack>#include<map>#include<set>#include<bitset>#include<functional>#include<assert.h>#include<numeric>using namespace std;#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )#define rep(i,n) REP(i,0,n)using ll = long long;constexpr int inf=1e9+7;constexpr ll longinf=1LL<<60 ;constexpr ll mod=998244353 ;vector<ll> inv,fact,invfact;void mod_build(int n=101010){fact.resize(n+1);inv.resize(n+1);invfact.resize(n+1);fact[0]=inv[0]=invfact[0]=1;inv[1]=1;rep(i,n){fact[i+1]=fact[i]*(i+1)%mod;if(i>0)inv[i+1]=mod-inv[mod%(i+1)]*(mod/(i+1))%mod;invfact[i+1]=invfact[i]*inv[i+1]%mod;}}ll perm(int n,int k){if(n<0||k<0||k>n)return 0;return fact[n]*invfact[n-k]%mod;}ll comb(int n,int k){if(n<0||k<0||k>n)return 0;return (fact[n]*invfact[n-k]%mod)*invfact[k]%mod;}ll powmod(ll n,ll k){k%=mod-1;if(k<0)k+=mod-1;ll ret=1;while(k){if(k&1)ret=ret*n%mod;n=n*n%mod;k>>=1;}return ret;}int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int n;cin>>n;mod_build(1234567);ll ans = 0;ll cur = n;for(int i=0;i<=n;i+=2){ans += 2 * comb(n, i) * powmod(2, abs(cur)) % mod;cur -= 4;}cout << ans % mod << endl;return 0;}