https://ac.nowcoder.com/acm/contest/11191

D - NIT的字符串

 

题意:给定一个长度为 n 的字符串,求这个字符串在满足要求的长度为 m 的小写字符串中的期望出现次数。有 k 个要求,两种:要求第 x 个字符不为 c;要求第 x 个字符必须为 c。注意 aaa 中 aa 出现了 2 次。

KMP自动机+矩阵快速幂

先求出出现次数,除以方案数就是答案。

记给定的长度为 n 的字符串为 ss 串,未给定的长度为 m 的字符串为 tt 串。

首先考虑暴力且无要求,dp[i][j]dp[i][j] 表示满足 t[ji+1,,j]=s[1,,i]t[j-i+1,\cdots,j]=s[1,\cdots,i]tt 串个数。

通过 KMP自动机的 trans 数组求解,trans[i][c]trans[i][c] 表示当前匹配到第 ii 位,再读入字符 c,最长能匹配到的长度。

则转移方程 dp[i+1][trans[i][s[i]]]+=dp[i][j]dp[i+1][trans[i][s[i]]]+=dp[i][j].

取向量 (dp[i][1],dp[i][2],,dp[i][n],S)(dp[i][1], dp[i][2],\cdots,dp[i][n],S),其中 SS 表示 tt 串到第 ii 位时 ss 串的出现次数。写出转移矩阵,再用快速幂求解。

有要求的位置把 m 分成几段,分阶段求解。

对于在同一个位置上的要求,一起处理,枚举该位置上能出现的字符 c,用 trans[c] 更新转移矩阵。此时不用快速幂,而是一次矩阵乘法。

对于没有要求的位置,一起乘,即用快速幂求解。

此题卡常非常严重。

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>

#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 1e2 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const ll inv2 = (mod + 1) / 2;
typedef pair<int, int> pii;

int n, m, q;

int Pow(int a, int b) {
int res = 1;
while (b) {
if (b & 1)res = 1ll * res * a % mod;
b >>= 1;
a = 1ll * a * a % mod;
}
return res;
}

char s[N];

struct Q {
int op, p;
char c;

bool operator<(const Q &b) const {
return p == b.p ? op < b.op : p < b.p;
}
} qq[510];

struct Mat {
int a[N][N];
int r, c;

Mat(int _r = N, int _c = N) {
r = _r, c = _c;
for (int i = 0; i < r; i++)for (int j = 0; j < c; j++)a[i][j] = 0;
}

Mat operator*(Mat b) const {
Mat ans(r, b.c);
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
if (a[i][j])
for (int k = 0; k < b.c; ++k)ans.a[i][k] = (ans.a[i][k] + 1ll * a[i][j] * b.a[j][k]) % mod;
return ans;
}
} A, ans, B, pw[40];


int tot = 1, nw[40];

void pow(int n) {
for (int i = 0; i <= 30; i++) {
if (n >> i & 1)ans = ans * pw[i], tot = 1ll * tot * nw[i] % mod;
}
}

int fail[N], trans[N][30]; //fail即KMP中nxt,trans表示从第i位经过字符j转移到的位置

void build(char *s) {
int n = strlen(s + 1);
fail[0] = 0, fail[1] = 0;
trans[0][s[1] - 'a'] = 1, trans[1][s[2] - 'a'] = 2;
for (int i = 2, j = 0; i <= n; i++) {
while (j && s[j + 1] != s[i])j = fail[j];
fail[i] = j = (s[j + 1] == s[i] ? j + 1 : j);
if (i < n)trans[i][s[i + 1] - 'a'] = i + 1;
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j < 26; j++) {
if (!trans[i][j])trans[i][j] = trans[fail[i]][j];
}
}
}

int ck[30];

int main() {
scanf("%d%d%d", &n, &m, &q);
scanf("%s", s + 1);
build(s);
for (int i = 1; i <= q; i++) {
scanf("%d%d", &qq[i].op, &qq[i].p);
scanf(" %c", &qq[i].c);
}
ans = Mat(1, n + 2);
A = Mat(n + 2, n + 2);
sort(qq + 1, qq + q + 1);
ans.a[0][0] = 1;
for (int i = 0; i <= n; i++) {
for (int j = 0; j < 26; j++) {
A.a[i][trans[i][j]]++;
}
}
for (int i = 0; i <= n; i++)A.a[i][n + 1] = A.a[i][n];
A.a[n + 1][n + 1] = 26;
pw[0] = A;
for (int i = 1; i <= 30; i++)pw[i] = pw[i - 1] * pw[i - 1];
nw[0] = 26;
for (int i = 1; i <= 30; i++)nw[i] = 1ll * nw[i - 1] * nw[i - 1] % mod;
for (int i = 1, las = 0, r; i <= q; i = r) {
B = Mat(n + 2, n + 2);
int p = qq[i].p;
pow(p - las - 1);
las = p;
r = i;
for (int j = 0; j < 26; j++)ck[j] = 1;
while (r <= q && qq[r].p == qq[i].p) {
if (qq[r].op == 0)ck[qq[r].c - 'a'] = 0;
else {
for (int j = 0; j < 26; j++)if (j != qq[r].c - 'a')ck[j] = 0;
}
r++;
}
for (int j = 0; j <= n; j++) {
for (int k = 0; k < 26; k++) {
if (ck[k])B.a[j][trans[j][k]]++;
}
}
int cnt = 0;
for (int j = 0; j < 26; j++)if (ck[j])cnt++;
for (int j = 0; j <= n; j++)B.a[j][n + 1] = B.a[j][n];
B.a[n + 1][n + 1] = cnt;
ans = ans * B;
tot = 1ll * tot * cnt % mod;
}
pow(m - qq[q].p);
printf("%lld\n", 1ll * ans.a[0][n + 1] * Pow(tot, mod - 2) % mod);
return 0;
}

 

E - NIT的gcd

 

题意:求 i=1nj=1nk=1ngcd(i,j)gcd(i,k)gcd(j,k)\sum\limits_{i=1}^n\sum\limits_{j=1}^n\sum\limits_{k=1}^n\gcd(i,j)\gcd(i,k)\gcd(j,k)1n1051\le n\le 10^5,对 998244353998244353 取模。

因数个数 d(nm)=xnym[gcd(x,y)==1]d(nm)=\sum\limits_{x|n}\sum\limits_{y|m}[\gcd(x,y)==1].

证明:设 nm=p1x1+y1p2x2+y2pkxk+yknm=p_1^{x_1+y_1}\cdot p_2^{x_2+y_2}\cdots p_k^{x_k+y_k},且 n=p1x1p2x2pkxkn=p_1^{x_1}\cdot p_2^{x_2}\cdots p_k^{x_k}m=p1y1p2y2pkykm=p_1^{y_1}\cdot p_2^{y_2}\cdots p_k^{y_k},设 i,ji,j 分别是 n,mn,m 的因子,且 i=p1a1p2a2pkaki=p_1^{a_1}\cdot p_2^{a_2}\cdots p_k^{a_k}j=p1b1p2b2pkbkj=p_1^{b_1}\cdot p_2^{b_2}\cdots p_k^{b_k}. 要使得 gcd(i,j)=1\gcd(i,j)=1,必然有 a1=0a_1=0b1=0b_1=0 或都为 00,当 a1=0a_1=0 时,b1b_1y1+1y_1+1 种取值;当 b1=0b_1=0 时,a1a_1x1+1x_1+1 种取值。其中 (a1,b1)=(0,0)(a_1,b_1)=(0,0) 这种取值方式被重复计算了,所以去重后总共取值方式有 x1+y1+1x_1+y_1+1 种。对于所有 pip_i 也都同理,且由于不同 pp 时的取值方式不会互相影响,故由乘法原理可以得到,最终互质的因子个数为 (xi+yi+1)\prod(x_i+y_i+1),与约数定理的形式相同。

上文与本题无关。

三元环计数+欧拉反演

欧拉反演:n=dnφ(d)n=\sum\limits_{d|n}\varphi(d).

i=1nj=1nk=1ngcd(i,j)gcd(i,k)gcd(j,k)=i=1nj=1nk=1nd1gcd(i,j)φ(d1)d2gcd(i,k)φ(d2)d3gcd(j,k)φ(d3)=i=1nj=1nk=1nd1id1jφ(d1)d2id2kφ(d2)d3jd3kφ(d3)=d1=1nφ(d1)d2=1nφ(d2)d3=1nφ(d3)d1id2i1d1jd3j1d2kd3k1=d1=1nφ(d1)d2=1nφ(d2)d3=1nφ(d3)lcm(d1,d2)i1lcm(d1,d3)j1lcm(d2,d3)k1=d1=1nφ(d1)d2=1nφ(d2)d3=1nφ(d3)nlcm(d1,d2)nlcm(d1,d3)nlcm(d2,d3)\begin{align} &\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\gcd(i,j)\gcd(i,k)\gcd(j,k)\\ &=\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{d_1|\gcd(i,j)}\varphi(d_1)\sum_{d_2|\gcd(i,k)}\varphi(d_2)\sum_{d_3|\gcd(j,k)}\varphi(d_3)\\ &=\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{d_1|i\wedge d_1|j}\varphi(d_1)\sum_{d_2|i\wedge d_2|k}\varphi(d_2)\sum_{d_3|j\wedge d_3|k}\varphi(d_3)\\ &=\sum_{d_1=1}^n\varphi(d_1)\sum_{d_2=1}^n\varphi(d_2)\sum_{d_3=1}^n\varphi(d_3)\sum_{d_1|i\wedge d_2|i}1\sum_{d_1|j\wedge d_3|j}1\sum_{d_2|k\wedge d_3|k}1\\ &=\sum_{d_1=1}^n\varphi(d_1)\sum_{d_2=1}^n\varphi(d_2)\sum_{d_3=1}^n\varphi(d_3)\sum_{lcm(d_1,d_2)|i}1\sum_{lcm(d_1,d_3)|j}1\sum_{lcm(d_2,d_3)|k}1\\ &=\sum_{d_1=1}^n\varphi(d_1)\sum_{d_2=1}^n\varphi(d_2)\sum_{d_3=1}^n\varphi(d_3)\lfloor\frac{n}{lcm(d_1,d_2)}\rfloor\lfloor\frac{n}{lcm(d_1,d_3)}\rfloor\lfloor\frac{n}{lcm(d_2,d_3)}\rfloor \end{align}

显然不能三重循环枚举。可以发现有很多为零的情况。

仅当 φ(d1)>0,φ(d2)>0,φ(d3)>0\varphi(d_1)>0,\varphi(d_2)>0,\varphi(d_3)>0,且 lcm(d1,d2)n,lcm(d1,d3)n,lcm(d2,d3)nlcm(d_1,d_2)\le n,lcm(d_1,d_3)\le n,lcm(d_2,d_3)\le n 时,(d1,d2,d3)(d_1,d_2,d_3) 是合法的。

[SDOI2018]旧试题 的套路。

建图,图上所有点都是合法的 dd,边权为两端点的 lcmlcm,且所有边权都小于等于 nn.

如果能建好图,图上的所有三元环就是答案。只要枚举所有三元环,就能计算答案。而枚举三元环的复杂度为 O(mm)\mathcal{O}(m\sqrt{m}),可以接受。

枚举边权建图。枚举 g=gcd(u,v)[1,n]g=\gcd(u,v)\in[1,n],再枚举 x=ugx=\frac{u}{g},再枚举 y=vgy=\frac{v}{g}。则有 xyg=lcm(u,v)nxyg=lcm(u,v)\le n,所以 gn,xng,ynxgg\le n,x\le \frac{n}{g},y\le\frac{n}{xg},则枚举的复杂度为 O(nlog2n)\mathcal{O}(n\log^2n),为了避免重复,需要判断当 gcd(x,y)=1\gcd(x,y)=1 时才加边。则总共为 O(nlog3n)\mathcal{O}(n\log^3n)

枚举三元环时需要计算LCM,但复杂度不够,所以需要在加边时同时计算出边权。

由于枚举三元环时没有包括 d1=d2=d3d_1=d_2=d_3d1=d2d_1=d_2 的情况,所以需要单独计算。

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
#include <bits/stdc++.h>

#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const ll inv2 = (mod + 1) / 2;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;

int phi[N], prime[N], tot; ll d;
bool vis[N];

void get_phi(int n) {
phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (!vis[i]) {
prime[tot++] = i;
phi[i] = i - 1;
}
for (int j = 0; j < tot && (d = 1ll * i * prime[j]) <= n; j++) {
vis[d] = 1;
if (i % prime[j] == 0) {
phi[d] = phi[i] * prime[j];
break;
} else phi[d] = phi[i] * (prime[j] - 1);
}
}
}

int n;
vector<pil> G[N];
vector<pii> es;
int deg[N];

int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}

ll LCM(int a, int b) {
return 1ll * a * b / gcd(a, b);
}

int vvis[N],lc[N];
ll ans;

int main() {
scanf("%d", &n);
get_phi(n);
for (int i = 1; i <= n; i++)ans = (ans + 1ll * phi[i] * phi[i] * phi[i] * (n / i) * (n / i) * (n / i)) % mod;
for (int g = 1; g <= n; g++) {
for (int x = 1; x <= n / g; x++) {
for (int y = x + 1; y <= n / g / x; y++) {
if (gcd(x, y) == 1) {
int u = x * g, v = y * g;
es.push_back({u, v});
deg[u]++;
deg[v]++;
}
}
}
}
for (pii e:es) {
int u = e.first, v = e.second;
ll lcm = n / LCM(u, v);
ans = (ans + 3ll * phi[u] * phi[u] * phi[v] * (n / u) * lcm * lcm) % mod;
ans = (ans + 3ll * phi[v] * phi[v] * phi[u] * (n / v) * lcm * lcm) % mod;
if (deg[u] < deg[v] || (deg[u] == deg[v] && u > v))swap(u, v);
G[u].push_back({v, LCM(u, v)});
}
for (int i = 1; i <= n; i++) {
for (pil j:G[i])vvis[j.first] = i, lc[j.first] = LCM(i, j.first);
for (pil j:G[i])
for (pil k:G[j.first])
if (vvis[k.first] == i) {
ans = (ans + 6ll * phi[i] * phi[j.first] * phi[k.first] * (n / j.second) * (n / k.second) * (n / lc[k.first])) % mod;
}
}
printf("%lld\n", ans);
return 0;
}