提出 #41093939

---

ソースコード 拡げる

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

template<class T> inline bool chmin(T& a, T b){ if (a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b){ if (a < b){a = b; return true;} return false;}

using mint = modint998244353;
//using mint = modint1000000007;
//using mint = modint;  // mint::set_mod(p); later
//using mint = static_modint<1000000009>;

int N;
string s;

vector<vector<int>> lut (30, vector<int>(110, (int) 1e9));
mint dp[105][105];

// TT のうち、後半の T の先頭が s[x] であるような部分文字列の個数
// (ただし、同じアルファベットはより左から選ぶことで重複カウントを防ぐ）
mint solve(int x){
  char sx = s[x];

  int pos = lut[sx-'a'][0];
  if (pos >= x){ return 0; }

  for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) dp[i][j] = 0;

  dp[pos][x] = 1;

  for (int i = pos; i < x; i++){
    for (int j = 0; j < N; j++){
      for (char c = 'a'; c <= 'z'; c++){
	int ni = lut[c-'a'][i+1];
	int nj = lut[c-'a'][j+1];
	if (ni < x && nj < N){
	  dp[ni][nj] += dp[i][j];
	}
      }
    }
  }

  mint ans = 0;
  for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
      if (lut[sx-'a'][i+1] == x){
	ans += dp[i][j];
      }
    }
  }

  return ans;
}
  

int main()
{
  cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

  cin >> s;
  N = (int) s.length();

  // Look up table
  for (char c = 'a'; c <= 'z'; c++){
    int idx = (int)(1e9);
    for (int i = N - 1; i >= 0; i--){
      if (s[i] == c){
	idx = i;
      }
      lut[c - 'a'][i] = idx;
    }
  }
  
  mint ans = 0;

  for (int i = 1; i < N; i++){
    ans += solve(i);
  }
  
  cout << ans.val() << endl;
  return 0;
}

提出情報

ジャッジ結果