提出 #25065595

---

ソースコード 拡げる

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define ld long double
#define ull unsigned long long
#define ll long long
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fast_io cout.tie(0), cin.tie(0), ios_base::sync_with_stdio(0)

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3")

using namespace std;
//using namespace __gnu_pbds;
//typedef tree<ll, null_type, less_equal<>, rb_tree_tag,
//    tree_order_statistics_node_update> ordered_set;

ld eps = (ld) 1 / 1e6;
ll inf_ll = 1e18 + 100, mod1 = 1e9 + 7, mod2 = 998244353;
ll mersen_mod = 2305843009213693951;

ll sqr(ll a) { return a * a; }
ll qb(ll a) { return a * a * a; }
ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
ll add(ll a, ll b, ll mod) {
  a += b;
  if (a >= mod) a -= mod;
  return a;
}
ll sub(ll a, ll b, ll mod) {
  a -= b;
  if (a < 0) a += mod;
  return a;
}
ll binpow(ll a, ll b, ll mod) {
  return b ? (b % 2 ? (a * (sqr(binpow(a, b / 2, mod)) % mod)) % mod :
              sqr(binpow(a, b / 2, mod)) % mod) : 1;
}
ll binmult(ll a, ll b, ll mod) {
  return b ? (b % 2 ? (2 * binmult(a, b / 2, mod) + a) % mod :
              (2 * binmult(a, b / 2, mod)) % mod) : 0;
}

/// Code here
ll dp[200001];

int main() {
  fast_io;
  string a;
  ll i, j, n, ans;
  cin >> a;
  n = a.size();
  a = '0' + a;
  dp[1] = 1, ans = 1;
  for (i = 2; i <= n; i++) {
    if (a[i] == a[i - 1]) dp[i] = dp[i - 2];
    else {
      for (j = i - 2; j > 0 && a[i] != a[j]; j--) dp[i] = add(dp[i], dp[j], mod1);
      dp[i] = add(dp[i], dp[j], mod1);
      if (!j) dp[i] = add(dp[i], 1, mod1);
      else dp[i] = add(dp[i], dp[j - 1], mod1);
    }
    ans = add(ans, dp[i], mod1);
  }
  cout << ans;
  //cerr << '\n' << "Time execute: " << clock() / (double)CLOCKS_PER_SEC << " sec" << '\n';
  return 0;
}

提出情報

ジャッジ結果