結果
問題 | No.1710 Minimum OR is X |
ユーザー |
|
提出日時 | 2021-10-15 22:29:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 634 ms / 2,000 ms |
コード長 | 1,113 bytes |
コンパイル時間 | 4,056 ms |
コンパイル使用メモリ | 235,228 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-17 17:42:15 |
合計ジャッジ時間 | 9,337 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; typedef long long int ll; typedef long double ld; #define FOR(i,l,r) for(ll i=l;i<r;i++) #define REP(i,n) FOR(i,0,n) #define RFOR(i,l,r) for(ll i=r-1;i>=l;i--) #define RREP(i,n) RFOR(i,0,n) #define ALL(x) x.begin(),x.end() #define P pair<ll,ll> #define F first #define S second #define BS(A,x) binary_search(ALL(A),x) #define LB(A,x) (ll)(lower_bound(ALL(A),x)-A.begin()) #define UB(A,x) (ll)(upper_bound(ALL(A),x)-A.begin()) #define COU(A,x) UB(A,x)-LB(A,x) template<typename T>using min_priority_queue=priority_queue<T,vector<T>,greater<T>>; //using mint=modint1000000007; using mint=modint998244353; signed main(){ ll N,M,K;string X;cin>>N>>M>>K>>X; vector<vector<mint>>DP(N+1,vector<mint>(M+1)); vector<mint>T(N+1,1);FOR(i,1,N+1)T[i]=T[i-1]*i; FOR(i,K,N+1)DP[i][M]=1; RREP(i,M)FOR(n,K,N+1){ if(X[i]=='0')FOR(j,K,n+1)DP[n][i]+=T[n]/T[j]/T[n-j]*pow_mod(2,(M-1-i)*(n-j),998244353)*DP[j][i+1]; if(X[i]=='1')REP(j,K)DP[n][i]+=T[n]/T[j]/T[n-j]*DP[n][i+1]; } cout<<DP[N][0].val()<<endl; return 0; }