結果
問題 | No.1702 count good string |
ユーザー |
![]() |
提出日時 | 2021-10-08 23:14:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 121 ms / 2,000 ms |
コード長 | 2,216 bytes |
コンパイル時間 | 2,030 ms |
コンパイル使用メモリ | 175,520 KB |
実行使用メモリ | 62,080 KB |
最終ジャッジ日時 | 2024-07-23 07:01:06 |
合計ジャッジ時間 | 5,747 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 47 |
ソースコード
#include <bits/stdc++.h>//eolibraries#define lnf 3999999999999999999#define inf 999999999#define fi first#define se second#define pb push_back#define all(c) (c).begin(),(c).end()#define sz(c) (int)(c).size()#define make_unique(a) sort(all(a)),a.erase(unique(all(a)),a.end());#define rep(i,n) for(int i=0;i<n;i++)#define drep(i,n) for(int i=n-1;i>=0;i--)#define crep(i,x,n) for(int i=x;i<n;i++)#define vec(...) vector<__VA_ARGS__>#define _3ioVv0Q ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)//eodefineusing namespace std;typedef long long i64;typedef long double ld;using pii=pair<int,int>;using tpii=pair<int,pii>;using vi=vec(i64);const int mxn=12000;const int mod=1e9+7;//snuke's modular int// template <i64 mod>struct modularint{i64 x;modularint(i64 x=0):x(x%mod){}modularint& operator+=(const modularint a){if ((x += a.x) >= mod) x -= mod;return *this;}modularint& operator-=(const modularint a){if ((x += mod-a.x) >= mod) x -= mod;return *this;}modularint& operator*=(const modularint a){(x *= a.x) %= mod;return *this;}modularint operator+(const modularint a)const{modularint res(*this);return res+=a;}modularint operator-(const modularint a)const{modularint res(*this);return res-=a;}modularint operator*(const modularint a)const{modularint res(*this);return res*=a;}modularint pow(i64 n)const{modularint res=1,x(*this);while(n){if(n&1)res*=x;x*=x;n>>=1;}return res;}modularint inv()const{return pow(mod-2);}};using mint=modularint;int main(){_3ioVv0Q;int n;string s;cin>>n;cin>>s;string yuki="yukicoder";int m=sz(yuki);// cout<<m<<"\n";// vec(vec(mint)) dp(n+1,vec(mint)(m+1));vec(vec(vec(mint))) dp(n+1,vec(vec(mint))(m+1,vec(mint)(2,0)));dp[0][0][0]=1;rep(i,n){rep(j,m+1){rep(t,2) dp[i+1][j][t]+=dp[i][j][t];}if(s[i]=='?'){rep(j,m){dp[i+1][j+1][1]+=dp[i][j][0];}}else{int _j=-inf;rep(j,m){if(s[i]==yuki[j]){_j=j;break;}}if(_j==-inf) continue;rep(t,2){dp[i+1][_j+1][t]+=dp[i][_j][t];}}}dp[n][m][0]+=dp[n][m][1];cout<<dp[n][m][0].x<<"\n";//return 0;}