結果
問題 | No.1171 Runs in Subsequences |
ユーザー |
|
提出日時 | 2020-08-14 22:26:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 930 ms / 2,000 ms |
コード長 | 1,118 bytes |
コンパイル時間 | 1,609 ms |
コンパイル使用メモリ | 171,508 KB |
実行使用メモリ | 118,848 KB |
最終ジャッジ日時 | 2024-10-10 15:48:02 |
合計ジャッジ時間 | 9,276 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h> #define MOD 1000000007LL using namespace std; typedef long long ll; typedef pair<int,int> P; ll mod_pow(ll x,ll n){ ll res=1; while(n>0){ if(n&1){ res=res*x%MOD; } x=x*x%MOD; n>>=1; } return res; } class segtree{ public: static const int N=1<<18; ll dp[1<<19]; segtree(){ memset(dp,0,sizeof(dp)); } void update(int k,ll v){ k+=N-1; dp[k]+=v; while(k>0){ k=(k-1)/2; dp[k]=(dp[k*2+1]+dp[k*2+2])%MOD; } } ll query(int a,int b,int k=0,int l=0,int r=N){ if(b<=l || r<=a)return 0; if(a<=l && r<=b)return dp[k]; int mid=(l+r)/2; ll vl=query(a,b,k*2+1,l,mid); ll vr=query(a,b,k*2+2,mid,r); return (vl+vr)%MOD; } }; string s; ll dp[200005]; ll sum[200005]; segtree seg[28]; int main(void){ cin >> s; int n=s.size(); ll ans=0; dp[0]=1; seg[26].update(0,1); for(int i=0;i<s.size();i++){ ll sum=0; for(int j=0;j<28;j++){ ll val=seg[j].query(0,i+1); if((s[i]-'a')!=j){ sum+=val; sum%=MOD; } } ans+=sum*mod_pow(2,n-i-1)%MOD; ans%=MOD; seg[(s[i]-'a')].update(i+1,mod_pow(2,i)); } printf("%lld\n",ans); return 0; }