結果
問題 | No.2279 OR Insertion |
ユーザー | Ujjwal Rana |
提出日時 | 2023-04-21 23:04:10 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 581 ms / 2,000 ms |
コード長 | 4,170 bytes |
コンパイル時間 | 3,178 ms |
コンパイル使用メモリ | 253,288 KB |
実行使用メモリ | 269,368 KB |
最終ジャッジ日時 | 2024-04-27 04:48:46 |
合計ジャッジ時間 | 19,014 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 36 ms
21,556 KB |
testcase_01 | AC | 38 ms
23,368 KB |
testcase_02 | AC | 84 ms
104,020 KB |
testcase_03 | AC | 59 ms
78,888 KB |
testcase_04 | AC | 556 ms
257,128 KB |
testcase_05 | AC | 43 ms
50,540 KB |
testcase_06 | AC | 195 ms
149,596 KB |
testcase_07 | AC | 208 ms
157,048 KB |
testcase_08 | AC | 83 ms
101,632 KB |
testcase_09 | AC | 265 ms
184,352 KB |
testcase_10 | AC | 471 ms
255,028 KB |
testcase_11 | AC | 73 ms
96,952 KB |
testcase_12 | AC | 343 ms
222,608 KB |
testcase_13 | AC | 52 ms
70,212 KB |
testcase_14 | AC | 56 ms
76,092 KB |
testcase_15 | AC | 227 ms
164,920 KB |
testcase_16 | AC | 43 ms
42,052 KB |
testcase_17 | AC | 195 ms
147,732 KB |
testcase_18 | AC | 302 ms
202,316 KB |
testcase_19 | AC | 392 ms
242,208 KB |
testcase_20 | AC | 214 ms
157,796 KB |
testcase_21 | AC | 170 ms
134,812 KB |
testcase_22 | AC | 35 ms
21,724 KB |
testcase_23 | AC | 39 ms
22,508 KB |
testcase_24 | AC | 37 ms
22,040 KB |
testcase_25 | AC | 35 ms
21,832 KB |
testcase_26 | AC | 38 ms
22,024 KB |
testcase_27 | AC | 36 ms
22,104 KB |
testcase_28 | AC | 36 ms
21,924 KB |
testcase_29 | AC | 35 ms
22,360 KB |
testcase_30 | AC | 35 ms
21,552 KB |
testcase_31 | AC | 36 ms
21,580 KB |
testcase_32 | AC | 480 ms
269,196 KB |
testcase_33 | AC | 487 ms
269,172 KB |
testcase_34 | AC | 482 ms
269,312 KB |
testcase_35 | AC | 488 ms
269,312 KB |
testcase_36 | AC | 480 ms
269,256 KB |
testcase_37 | AC | 479 ms
269,248 KB |
testcase_38 | AC | 471 ms
269,204 KB |
testcase_39 | AC | 476 ms
269,176 KB |
testcase_40 | AC | 485 ms
269,228 KB |
testcase_41 | AC | 581 ms
269,300 KB |
testcase_42 | AC | 493 ms
269,180 KB |
testcase_43 | AC | 492 ms
269,060 KB |
testcase_44 | AC | 477 ms
269,000 KB |
testcase_45 | AC | 457 ms
269,368 KB |
testcase_46 | AC | 456 ms
269,148 KB |
testcase_47 | AC | 462 ms
269,148 KB |
testcase_48 | AC | 491 ms
269,188 KB |
testcase_49 | AC | 454 ms
269,016 KB |
ソースコード
#pragma GCC target ("avx2") #pragma GCC optimize ("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize ("unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; #define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define endl '\n' typedef long long ll; // #define mod1 (ll)1000000007 #define mod2 (ll)998244353 #define pll pair<ll,ll> typedef long double lb; typedef tree< pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; #define eps (lb)(1e-9) struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; // Operator overloads template<typename T1, typename T2> // cin >> pair<T1, T2> istream& operator>>(istream &istream, pair<T1, T2> &p) { return (istream >> p.first >> p.second); } template<typename T> // cin >> vector<T> istream& operator>>(istream &istream, vector<T> &v) { for (auto &it : v) cin >> it; return istream; } template<typename T1, typename T2> // cout << pair<T1, T2> ostream& operator<<(ostream &ostream, const pair<T1, T2> &p) { return (ostream << p.first << " " << p.second); } template<typename T> // cout << vector<T> ostream& operator<<(ostream &ostream, const vector<T> &c) { for (auto &it : c) cout << it << " "; return ostream; } // Utility functions template <typename T> void print(T &&t) { cout << t << "\n"; } template <typename T, typename... Args> void print(T &&t, Args &&... args) { cout << t << " "; print(forward<Args>(args)...); } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ll random(ll p){ // gives random number in [0,p] return uniform_int_distribution<ll>(0, p)(rng); } ll n; vector<ll>v; ll mod=mod2; ll mod1=mod2; ll dp[4000][4000]; ll sum[4000][4000]; ll pwr[5000]; ll power(ll a, ll b, ll c=mod1){ if(a==0){ return 0;} else if(b==0||a==1){ return 1;} ll p=power(a,b/2,c); p*=p; p%=c; if(b%2){p*=a;} p%=c; return p;} ll modinv(ll a, ll c=mod1){ return power(a,c-2,c); } const ll MAXN =1000000; ll fac[MAXN+1]; ll invfac[MAXN+1]; void factorial(ll mod=mod1){ fac[0]=1; for(ll i(1);i<=MAXN;++i){fac[i]=i*fac[i-1]; fac[i]%=mod;} invfac[MAXN]=modinv(fac[MAXN],mod); for(ll i(MAXN-1);i>-1;--i) { invfac[i]=(i+1ll)*invfac[i+1]; invfac[i]%=mod; } for(ll i(0);i<5000;++i){ pwr[i]=power(2,i); } } ll C(ll n,ll r,ll mod=mod1){ if(n<0||r<0||r>n){return 0;} ll p=fac[n]; ll q=invfac[n-r]*invfac[r]; q%=mod; p*=q; p%=mod; return p; } void pre(){ for(ll j(0);j<n;++j){ ll rs=0; for(ll i(0);i<n;++i){ if(j>i){ dp[i][j]=0; } else if(j==i){ dp[i][j]=(v[0]==1); } else if(v[i-j]==0){ dp[i][j]=sum[i-1][j]; } else{ dp[i][j]=pwr[i-j]; if(j>0){ dp[i][j]+=(sum[i-1][j]-sum[i-j-1][j]); } } rs+=dp[i][j]; rs%=mod; sum[i][j]=rs; } } } void solve(); int main() { io; ll t=1,n=1; // cin>>t; factorial(); while (t--){ solve(); } return 0; } void solve(){ cin>>n; v.resize(n); for(ll i(0);i<n;++i){ char p; cin>>p; v[i]=p-'0'; } pre(); ll ans=0; for(ll i(0);i<n;++i){ ll c=power(2,i); ans+=c*dp[n-1][i]; ans%=mod; } cout<<ans<<endl; } // Do not get stuck on a single approach for long, think of multiple ways