結果
問題 | No.2711 Connecting Lights |
ユーザー | ensembleaverage |
提出日時 | 2024-03-31 14:31:27 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 140 ms / 5,000 ms |
コード長 | 2,076 bytes |
コンパイル時間 | 1,769 ms |
コンパイル使用メモリ | 172,796 KB |
実行使用メモリ | 9,088 KB |
最終ジャッジ日時 | 2024-03-31 14:31:32 |
合計ジャッジ時間 | 3,648 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,676 KB |
testcase_01 | AC | 2 ms
6,676 KB |
testcase_02 | AC | 2 ms
6,676 KB |
testcase_03 | AC | 2 ms
6,676 KB |
testcase_04 | AC | 2 ms
6,676 KB |
testcase_05 | AC | 4 ms
6,676 KB |
testcase_06 | AC | 2 ms
6,676 KB |
testcase_07 | AC | 3 ms
6,676 KB |
testcase_08 | AC | 3 ms
6,676 KB |
testcase_09 | AC | 82 ms
6,784 KB |
testcase_10 | AC | 57 ms
6,676 KB |
testcase_11 | AC | 106 ms
8,192 KB |
testcase_12 | AC | 25 ms
6,676 KB |
testcase_13 | AC | 31 ms
6,676 KB |
testcase_14 | AC | 4 ms
6,676 KB |
testcase_15 | AC | 15 ms
6,676 KB |
testcase_16 | AC | 4 ms
6,676 KB |
testcase_17 | AC | 5 ms
6,676 KB |
testcase_18 | AC | 6 ms
6,676 KB |
testcase_19 | AC | 84 ms
7,184 KB |
testcase_20 | AC | 31 ms
6,676 KB |
testcase_21 | AC | 4 ms
6,676 KB |
testcase_22 | AC | 2 ms
6,676 KB |
testcase_23 | AC | 4 ms
6,676 KB |
testcase_24 | AC | 51 ms
6,676 KB |
testcase_25 | AC | 64 ms
6,676 KB |
testcase_26 | AC | 139 ms
9,088 KB |
testcase_27 | AC | 130 ms
9,088 KB |
testcase_28 | AC | 140 ms
9,088 KB |
testcase_29 | AC | 123 ms
9,088 KB |
ソースコード
#include "bits/stdc++.h" /* #include "boost/multiprecision/cpp_int.hpp" namespace mp = boost::multiprecision; using i128=mp::cpp_int; */ using namespace std; typedef long long ll; typedef int64_t i64; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<vvi> vvvi; typedef vector<ll> vll; typedef vector<vll> vvll; typedef vector<vvll> vvvll; typedef vector<string> vs; typedef vector<char> vc; typedef vector<vc> vvc; typedef vector<double> vd; typedef vector<vd> vvd; #define rep(i,a,n) for(int i=a;i<n;i++) #define drep(i,a,n) for(int i=a;i>n;i--) #define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl; #define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl; #define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl; #define iINF 1000000007 #define lINF 10000000000007 #define llINF 4000000000000000007 #define all(x) x.begin(),x.end() #define so(x) sort(all(x)) #define re(x) reverse(all(x)) const double PI = acos(-1); //累乗余り ll modexpo(ll x,ll n,ll m){ if(x==0) return 0; x%=m; ll ans=1; ll change=x; while(n>0){ if(n%2==1){ans*=change; ans%=m;} change*=change; change%=m; n/=2; } return ans; } int main(){ vll ex(10); ex[0]=1; rep(i,1,10) ex[i]=ex[i-1]*2; const ll mod=998244353; ll n,m,K; cin>>n>>m>>K; if(m==1){ cout<<ex[n]<<endl; return 0; } ll N=ex[n]; vvll dp(m,vll(N)); rep(i,0,N) dp[0][i]=1; rep(i,1,m){ rep(j,0,N){ rep(k,0,N){ ll cnt=0; rep(l,0,n){ if((j&k)&ex[l]) cnt++; } //cout<<cnt<<" "; if(cnt>=K) dp[i][j]+=dp[i-1][k]; dp[i][j]%=mod; } /*cout<<endl; cout<<dp[i][j]<<" "; cout<<endl;*/ } //cout<<endl; } /*rep(i,0,m){ rep(j,0,N) cout<<dp[i][j]<<" "; cout<<endl; }*/ ll ans=0; rep(i,0,N) ans+=dp[m-1][i]; ans%=mod; cout<<ans<<endl; }