結果

問題 No.1171 Runs in Subsequences
ユーザー eQeeQe
提出日時 2020-08-27 11:48:47
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 175 ms / 2,000 ms
コード長 2,408 bytes
コンパイル時間 1,505 ms
コンパイル使用メモリ 162,568 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-07 15:35:32
合計ジャッジ時間 3,516 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 3 ms
5,248 KB
testcase_15 AC 168 ms
5,248 KB
testcase_16 AC 167 ms
5,248 KB
testcase_17 AC 174 ms
5,248 KB
testcase_18 AC 174 ms
5,248 KB
testcase_19 AC 175 ms
5,248 KB
testcase_20 AC 174 ms
5,248 KB
testcase_21 AC 175 ms
5,248 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;;
  }
  
};


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