字符串数数——考虑循环节：1108T3

http://47.92.197.167:5283/contest/428/problem/3

一个字符串的最小表示法每个位置的概率只和其最短循环节有关。

假设循环节长为 $d$，则前面每个位置是开头的概率为 $\frac{1}{d}$

我们可以先预处理一个 $g_i$，表示长为 $i$ 的字符串没有循环节的方案数。

然后对于每个串，我们枚举其约数 $j$，表示循环节长度为 $j$。前面 $j$ 个位置都有 $\frac{1}{j}\times \frac{g_j}{26^{a_i}}$ 的期望。

对于询问两个相邻的串，我们在其所有约数中two-pointers即可。

#include
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//srand(time(0));
#define N 100010
//#define M
#define mo 998244353
int pw(int a, int b) {
	int ans=1; 
	while(b) {
		if(b&1) ans*=a; 
		a*=a; b>>=1; 
		ans%=mo; a%=mo; 
	}
	return ans; 
}
void Mod(int &a) { if(a>=mo || a<=-mo) a%=mo; if(a<0) a+=mo; }
void Add(int &a, int b) { a+=b; Mod(a); }
void Mul(int &a, int b) { Mod(b); a*=b; Mod(a); } 
int g[N]; 
int fac[N], inv[N], ifac[N]; 
void init() {
	g[1]=26; 
	for(int i=2; i<N; ++i) {
		g[i]=pw(26, i); 
		for(int j=1; j*j<=i; ++j) 
			if(i%j==0) {
				Add(g[i], -g[j]); 
				if(j!=1 && j*j!=i) Add(g[i], -g[i/j]); 
			}
	}
	int i; 
	for(i=fac[0]=1; i<N; ++i) fac[i]=fac[i-1]*i%mo; 
	ifac[N-1]=pw(fac[N-1], mo-2); 
	for(i=N-2; i>=0; --i) ifac[i]=ifac[i+1]*(i+1)%mo; 
    for(i=1; i<N; ++i) inv[i]=ifac[i]*fac[i-1]%mo; 
}
int n, m, i, j, k, T;
int a[N], sum, ans, len, now, lst, l, r; 
vector<pair<int, int> >s[N]; 
vector<int>v; 

signed main()
{
	freopen("sagiri.in", "r", stdin);
	freopen("sagiri.out", "w", stdout);
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
	T=read(); init(); 
	n=read(); ans=sum=0; 
	if(n==1) { printf("1\n"); return 0; }
	for(i=1; i<=n; ++i) {
		a[i]=k=read(); sum+=a[i]; 
		s[i].pb({0, 0}); 
		vector<int>v; 
		for(j=1; j*j<=a[i]; ++j) if(a[i]%j==0) {
			s[i].pb({j, g[j]*inv[j]%mo}); 
			if(j*j!=a[i]) v.pb(a[i]/j); 
		}
//		debug("> %lld\n", v.size()); 
		if(v.size()) {
			
			for(j=v.size()-1; j>=0; --j)  k=g[v[j]]*inv[v[j]]%mo, s[i].pb({v[j], k}); 
		}
		int k=pw(26, a[i]) ; k=pw(k, mo-2); 
		for(auto &t : s[i]) Mul(t.se, k); 
		for(j=s[i].size()-2; j>=0; --j) Add(s[i][j].se, s[i][j+1].se);
//		for(auto t : s[i]) debug("%lld %lld\n", t.fi, t.se); debug("\n"); 
	}
	sum=pw(pw(26, sum), mo-2); 
	for(i=1; i<=n; ++i) {
		j=i%n+1; l=0; r=0; len=min(a[i], a[j]); lst=0; 
		while(lst<len) {
			if(s[i][l+1].fi==s[j][r+1].fi) ++l, ++r; 
			else if(s[i][l+1].fi<s[j][r+1].fi) ++l; 
			else ++r; 
			now=max(s[i][l].fi, s[j][r].fi); 
			int s1=(s[i][l].fi==now ? s[i][l].se : s[i][l+1].se); 
			int s2=(s[j][r].fi==now ? s[j][r].se : s[j][r+1].se); 
			Add(ans, s1*s2%mo*(now-lst)%mo); 
			lst=now; 
		}
	}
	printf("%lld\n", ans); 


	return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104