結果
問題 | No.2083 OR Subset |
ユーザー | chestnut_68 |
提出日時 | 2023-06-23 03:14:08 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,461 bytes |
コンパイル時間 | 3,840 ms |
コンパイル使用メモリ | 237,888 KB |
実行使用メモリ | 286,976 KB |
最終ジャッジ日時 | 2024-06-30 08:52:25 |
合計ジャッジ時間 | 8,562 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 14 ms
20,736 KB |
testcase_01 | AC | 14 ms
15,488 KB |
testcase_02 | AC | 17 ms
15,684 KB |
testcase_03 | TLE | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep1(a) for(int z = 0; z < a; z++) #define rep2(i, a) for(int i = 0; i < a; i++) #define rep3(i, a, b) for(int i = a; i < b; i++) #define rep4(i, a, b, c) for(int i = a; i < b; i += c) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) const int MOD=998244353; const int64_t INF = 1LL<<60; void YN(bool x){ if(x) cout<<"Yes"; else cout<<"No"; } const int MAX = 510000; int64_t fac[MAX],finv[MAX],inv[MAX]; void COMinit() { fac[0]=fac[1]=1; finv[0]=finv[1]=1; inv[1]=1; for(int i=2;i<MAX;i++){ fac[i]=fac[i-1]*i%MOD; inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD; finv[i]=finv[i-1]*inv[i]%MOD; } } int64_t COM(int n,int k){ if(n<k)return 0; if(n<0||k<0)return 0; return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD; } map<pair<int,int>,mint>M; mint S(int n,int k){ mint one=1; if(M.count({n,k}))return M[{n,k}]; if(n==0&&k==0)return M[{n,k}]=one; if(k==1)return M[{n,k}]=one; if(n==k)return M[{n,k}]=one; return M[{n,k}]=S(n-1,k-1)+k*S(n-1,k); } int main(){ COMinit(); int64_t N;cin>>N; vector<int64_t> A(N+1,1); rep(i,N)A[i+1]=(A[i]*2)%MOD; mint ans=A[N]; rep(i,2,N+1){ rep(j,i,N+1){ mint tmp=COM(N,j)*S(j,i); tmp*=pow_mod(A[i]-i,N-j,MOD); ans+=tmp; } } cout<<ans.val()<<endl; }