# Untitled

unknown
plain_text
10 days ago
5.6 kB
1
Indexable
Never
```#include<bits/stdc++.h>

#define ll long long
#define pp push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define ld long double
#define PI acos(-1)
#define sin(a) sin((a)*PI/180)
#define cos(a) cos((a)*PI/180)
#define ones(x) __builtin_popcountll(x)
//#define int ll

using namespace std;

void Drakon() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef Clion
freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
}

unsigned long long inf = 1e10;
const double EPS = 1e-6;
const int MOD = 1000000007, N = 200005, LOG = 25;

ll mul(const ll &a, const ll &b) {
return (a % MOD + MOD) * (b % MOD + MOD) % MOD;
}

ll add(const ll &a, const ll &b) {
return (a + b + 2 * MOD) % MOD;
}

int pw(ll x, ll y) {
ll ret = 1;
while (y > 0) {
if (y % 2 == 0) {
x = mul(x, x);
y = y / 2;
} else {
ret = mul(ret, x);
y = y - 1;
}
}
return ret;
}

#define vi vector<int>
#define rep(aa, bb, cc) for(int aa = bb; aa < cc;aa++)
#define sz(a) (int)a.size()
typedef complex<double> C;
typedef vector<double> vd;
void fft(vector<C>& a) {
int n = sz(a), L = 31 - __builtin_clz(n);
static vector<complex<long double>> R(2, 1);
static vector<C> rt(2, 1);  // (^ 10% faster if double)
for (static int k = 2; k < n; k *= 2) {
R.resize(n); rt.resize(n);
auto x = polar(1.0L, acos(-1.0L) / k);
rep(i,k,2*k) rt[i] = R[i] = i&1 ? R[i/2] * x : R[i/2];
}
vi rev(n);
rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int k = 1; k < n; k *= 2)
for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
// C z = rt[j+k] * a[i+j+k]; // (25% faster if hand-rolled)  /// include-line
auto x = (double *)&rt[j+k], y = (double *)&a[i+j+k];        /// exclude-line
C z(x[0]*y[0] - x[1]*y[1], x[0]*y[1] + x[1]*y[0]);           /// exclude-line
a[i + j + k] = a[i + j] - z;
a[i + j] += z;
}
}

template<int M> vi convMod(const vi &a, const vi &b) {
if (a.empty() || b.empty()) return {};
vi res(sz(a) + sz(b) - 1);
int B=32-__builtin_clz(sz(res)), n=1<<B, cut=int(sqrt(M));
vector<C> L(n), R(n), outs(n), outl(n);
rep(i,0,sz(a)) L[i] = C((int)a[i] / cut, (int)a[i] % cut);
rep(i,0,sz(b)) R[i] = C((int)b[i] / cut, (int)b[i] % cut);
fft(L), fft(R);
rep(i,0,n) {
int j = -i & (n - 1);
outl[j] = (L[i] + conj(L[j])) * R[i] / (2.0 * n);
outs[j] = (L[i] - conj(L[j])) * R[i] / (2.0 * n) / 1i;
}
fft(outl), fft(outs);
rep(i,0,sz(res)) {
ll av = (ll)(real(outl[i])+.5), cv = (ll)(imag(outs[i])+.5);
ll bv = (ll)(imag(outl[i])+.5) + (ll)(real(outs[i])+.5);
res[i] = ((av % M * cut + bv) % M * cut + cv) % M;
}
return res;
}

const int P1 = 31, P2 = 37;

int pw1[N], pw2[N], inv1[N], inv2[N];

void pre() {
pw1[0] = inv1[0] = pw2[0] = inv2[0] = 1;
int mulInv1 = pw(P1, MOD - 2);
int mulInv2 = pw(P2, MOD - 2);
for (int i = 1; i < N; i++) {
pw1[i] = mul(pw1[i - 1], P1);
pw2[i] = mul(pw2[i - 1], P2);
inv1[i] = mul(inv1[i - 1], mulInv1);
inv2[i] = mul(inv2[i - 1], mulInv2);
}
}

void solve() {
string s;
cin >> s;
map<pair<int, int>, int> freq;

pair<int, int> pre = {0, 0}, suf = {0, 0};
for (int i = 0; i < s.size(); ++i) {
suf.first = add(suf.first, mul(s[i] - 'a' + 1, pw1[i]));
suf.second = add(suf.second, mul(s[i] - 'a' + 1, pw2[i]));
}

for (int i = 0; i <= s.size(); ++i) {
for (int j = 1; j <= 26; ++j) {
pair<int, int> cur = pre;

cur.first = add(cur.first, mul(suf.first, pw1[i + 1]));
cur.second = add(cur.second, mul(suf.second, pw2[i + 1]));

freq[cur] ++;
}

if(i == s.size())break;

suf.first = add(suf.first, -(s[i] - 'a' + 1));
suf.second = add(suf.second, -(s[i] - 'a' + 1));
suf.first = mul(suf.first, inv1[1]);
suf.second = mul(suf.second, inv1[1]);

pre.first = add(pre.first, mul(s[i] - 'a' + 1, pw1[i]));
pre.second = add(pre.second, mul(s[i] - 'a' + 1, pw2[i]));
}

vector<vi> poly;
for(auto &f : freq) {
int prob = mul(pw(s.size() + 1, MOD - 2), pw(26, MOD - 2));
prob = mul(prob, f.second);
poly.push_back({1, prob});
}

while (poly.size() > 1) {
vector<vi> res;
for (int i = 0; i + 1 < poly.size(); i += 2) {
res.push_back(convMod<MOD>(poly[i], poly[i + 1]));
}
if(poly.size() & 1)res.push_back(poly.back());
swap(poly, res);
}

vector<int> p = poly[0];

int fac[p.size()];
fac[0] = 1;
for (int i = 1; i < p.size(); ++i) {
fac[i] = mul(fac[i - 1], i);
}
int ans = 0, prev = 0;
for (int i = 2; i < p.size(); ++i) {
int tmp = mul(p[i], fac[i]);
}

cout << ans;
}

signed main() {
Drakon();
pre();
int t = 1;
//cin >> t;
while (t--) {
solve();
}
}```