結果
問題 | No.1702 count good string |
ユーザー |
![]() |
提出日時 | 2021-10-08 23:13:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 1,781 bytes |
コンパイル時間 | 1,759 ms |
コンパイル使用メモリ | 172,108 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-23 07:00:34 |
合計ジャッジ時間 | 3,339 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 47 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using V = vector<ll>; using VV = vector<V>; using VVV = vector<VV>; using VS = vector<string>; using P = pair<ll,ll>; using M = map<ll,ll>; using Q = queue<ll>; using PQ = priority_queue<ll>; using PQG = priority_queue<ll,V,greater<ll>>; using S = set<ll>; const ll MOD = 1000000007; const ll Mod = 998244353; const ll INF = 1LL << 60; #define rep(i,n) for(ll i = 0; i < n; i++) #define rep2(i,s,n) for(ll i = s; i < n; i++) #define rep3(i,s,n) for(ll i = s; i <= n; i++) #define all(x) (x).begin(),(x).end() #define MP(a,b) make_pair(a,b) #define fi first #define se second #define pb push_back #define pf push_front #define ppb pop_back #define ppf pop_front template<class T>bool chmin(T&a, const T&b){if(a>b){a=b;return 1;}return 0;} template<class T>bool chmax(T&a, const T&b){if(a<b){a=b;return 1;}return 0;} template<class T>void Vin(vector<T>&a){rep(i,(int)a.size())cin>>a[i];} template<class T>void Vout(const vector<T>&a){rep(i,(int)a.size())cout<<a[i]<<endl;} ll power(ll a,ll b,const ll&M){a%=M;ll res=1;while(b>0){if(b&1)res=res*a%M;a=a*a%M;b>>=1;}return res;} const ll H[4] = {0,1,0,-1}, W[4] = {1,0,-1,0}; int main() { ll n, ans = 0; string s, t = "yukicoder"; cin >> n >> s; VV dp(10,V(9)); for(char c : s) { rep(i,9) if(c == t[i]) { rep(j,10) if(i != j) { if(i == 0) dp[j][i] = (dp[j][i] + 1) % MOD; else dp[j][i] = (dp[j][i] + dp[j][i-1]) % MOD; } break; } if(c == '?') rep(i,9) { if(i == 0) dp[i][i] = (dp[i][i] + 1) % MOD; else dp[i][i] = (dp[i][i] + dp[i][i-1]) % MOD; } } rep(i,10) ans = (ans + dp[i][8]) % MOD; cout << ans << endl; }