結果

問題 No.1171 Runs in Subsequences
コンテスト
ユーザー eQe
提出日時 2020-08-27 11:15:41
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,518 bytes
コンパイル時間 3,195 ms
コンパイル使用メモリ 161,904 KB
実行使用メモリ 44,928 KB
最終ジャッジ日時 2024-11-07 15:34:34
合計ジャッジ時間 13,845 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 4
other WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define ft first
#define sc second
#define pt(sth) cout << sth << "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
template<class T>bool chmax(T &a, const T &b) {if(a<b) {a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if(b<a) {a=b; return 1;} return 0;}
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=1e9+7;
//for(i=0; i<N; i++) cin >> a[i];

struct mll {
  ll val;
  mll(ll val=0):val((val%MOD+MOD)%MOD){}
  
  mll pow(ll t) const {
    if (!t) return 1;
    mll a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
  mll inv() const { return pow(MOD-2); }
  
  mll operator-() const { return mll(-val);}
  mll& operator+=(const mll a) {
    if ((val += a.val) >= MOD) val -= MOD;
    return *this;
  }
  mll& operator-=(const mll a) {
    if ((val += MOD-a.val) >= MOD) val -= MOD;
    return *this;
  }
  mll& operator*=(const mll a) {
    (val *= a.val%MOD) %= MOD;
    return *this;
  }
  mll& operator/=(const mll a) {
    return (*this) *= a.inv();
  }
  
  mll operator+(const mll a) const {
    mll res(*this);
    return res+=a;
  }
  mll operator-(const mll a) const {
    mll res(*this);
    return res-=a;
  }
  mll operator*(const mll a) const {
    mll res(*this);
    return res*=a;
  }
  mll operator/(const mll a) const {
    mll res(*this);
    return res/=a;
  }
  
  mll& operator++(   ) { val++; return *this; }
  mll  operator++(int) { mll res(*this); val++; return res; }
  mll& operator--(   ) { val--; return *this; }
  mll  operator--(int) { mll res(*this); val--; return res; }
  
  bool operator< (const mll a) const { return val< a.val; }
  bool operator<=(const mll a) const { return val<=a.val; }
  bool operator> (const mll a) const { return val> a.val; }
  bool operator>=(const mll a) const { return val>=a.val; }
  bool operator==(const mll a) const { return val==a.val; }
  
  friend istream& operator>>(istream &input, mll &a) {
    input >> a.val;
    return input;
  }
  
  friend ostream& operator<<(ostream &output, mll &a) {
    output << a.val;
    return output;;
  }
  
};

mll sum[26][MAX*2]={};

int main(void) {
  ll i, j, k;
  
  string s;
  cin >> s;
  ll N=s.size();
  s='#'+s;
  pt(s);
  for(i=1; i<=N; i++) {
    sum[s[i]-'a'][i]+=sum[s[i]-'a'][i-1]+mll(2).pow(i-1);
  }
  
  mll ans=0;
  for(j=1; j<=N; j++) {
    for(ll p=0; p<26; p++) {
      if(p==s[j]-'a') continue;
      ans+=sum[p][j-1]*mll(2).pow(N-j);
    }
  }
  
  pt(ans);
  
}
0