結果

問題 No.1171 Runs in Subsequences
ユーザー eQeeQe
提出日時 2020-08-27 11:33:05
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,361 ms / 2,000 ms
コード長 2,557 bytes
コンパイル時間 4,026 ms
コンパイル使用メモリ 161,812 KB
実行使用メモリ 44,800 KB
最終ジャッジ日時 2024-11-07 15:35:26
合計ジャッジ時間 12,098 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 33 ms
44,416 KB
testcase_01 AC 33 ms
44,288 KB
testcase_02 AC 32 ms
44,416 KB
testcase_03 AC 32 ms
44,544 KB
testcase_04 AC 32 ms
44,288 KB
testcase_05 AC 32 ms
44,544 KB
testcase_06 AC 32 ms
44,544 KB
testcase_07 AC 32 ms
44,544 KB
testcase_08 AC 32 ms
44,544 KB
testcase_09 AC 32 ms
44,544 KB
testcase_10 AC 37 ms
44,416 KB
testcase_11 AC 36 ms
44,544 KB
testcase_12 AC 36 ms
44,416 KB
testcase_13 AC 36 ms
44,544 KB
testcase_14 AC 36 ms
44,416 KB
testcase_15 AC 1,309 ms
44,800 KB
testcase_16 AC 1,280 ms
44,800 KB
testcase_17 AC 1,348 ms
44,672 KB
testcase_18 AC 1,361 ms
44,800 KB
testcase_19 AC 1,345 ms
44,800 KB
testcase_20 AC 1,349 ms
44,672 KB
testcase_21 AC 1,343 ms
44,800 KB
権限があれば一括ダウンロードができます

ソースコード

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;
  
  for(i=1; i<=N; i++) {
    for(ll p=0; p<26; p++) sum[p][i]=sum[p][i-1];
    sum[s[i]-'a'][i]+=mll(2).pow(i-1);
  }
  
  mll ans=mll(2).pow(N)-1;
  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