結果
問題 |
No.1725 [Cherry 3rd Tune D] 無言の言葉
|
ユーザー |
![]() |
提出日時 | 2021-12-02 21:56:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 178 ms / 4,000 ms |
コード長 | 2,101 bytes |
コンパイル時間 | 3,753 ms |
コンパイル使用メモリ | 231,956 KB |
実行使用メモリ | 24,412 KB |
最終ジャッジ日時 | 2024-07-05 02:07:44 |
合計ジャッジ時間 | 9,835 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 42 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll=long long; using Graph=vector<vector<int>>; #define INF 1000000000 #define MOD 998244353 #define MAX 1000000 string X,Y; int dfs(int i,int R,char c,vector<int> &length,vector<vector<int>> &cnt,vector<vector<int>> &sumX,vector<vector<int>> &sumY){ if(i==1){ return sumX[c-'a'][R]; } if(R<=length[i-1]){ return dfs(i-1,R,c,length,cnt,sumX,sumY); } if(R<=length[i-1]+(int)Y.size()){ return cnt[c-'a'][i-1]+sumY[c-'a'][R-length[i-1]]; } return 2*cnt[c-'a'][i-1]+sumY[c-'a'][Y.size()]-dfs(i-1,2*length[i-1]+(int)Y.size()-R,c,length,cnt,sumX,sumY); } int main(){ int Q; cin>>X>>Y>>Q; vector<vector<int>> sumY(26,vector<int>(Y.size()+1,0)); vector<vector<int>> sumX(26,vector<int>(X.size()+1,0)); for(int j=0;j<Y.size();j++){ for(int i=0;i<26;i++){ sumY[i][j+1]=sumY[i][j]; } sumY[Y[j]-'a'][j+1]++; } for(int j=0;j<X.size();j++){ for(int i=0;i<26;i++){ sumX[i][j+1]=sumX[i][j]; } sumX[X[j]-'a'][j+1]++; } vector<int> length(33); vector<vector<int>> cnt(26,vector<int>(33,0)); length[1]=X.size(); for(int j=0;j<26;j++){ cnt[j][1]=sumX[j][X.size()]; } for(int i=2;i<33;i++){ length[i]=2*length[i-1]+(int)Y.size(); if(length[i]>INF){ length[i]=INF; } for(int j=0;j<26;j++){ cnt[j][i]=2*cnt[j][i-1]+sumY[j][Y.size()]; if(cnt[j][i]>INF){ cnt[j][i]=INF; } } } for(int i=0;i<Q;i++){ int L,R; char C; cin>>L>>R>>C; cout<<dfs(32,R,C,length,cnt,sumX,sumY)-dfs(32,L-1,C,length,cnt,sumX,sumY)<<'\n'; } //X.count(C)=a,Y.count(C)=b //F[n].count(C)=(a+b)*2^(n-1)-b //len(F[n])=(len(X)+len(Y))*2^(n-1)-len(Y) //F(n,C) =F[n]に含まれるCの数 //f(n,R,C)=F[n]のR番目までに含まれるCの数 // =f(n-1,R,C) ; R<=len(F[n-1]) // =F(n-1,C)+alpha ; len(F[n-1])<R<=len(F[n-1])+len(Y) // =2*F(n-1,C)+alpha-f(n-1,len(F[n])-R,C) ; R>len(F[n-1])+len(Y) }