0%

1.24 考试

T1 Power

image-20210129190609220

我们可以近似地将这个序列看作一个每个元素在$[1,P-1]$之间随机的序列。

那么我们可以发现$k$个随机数的最大值的期望为$\frac{k(P-1)}{k+1}$,也就是说,如果我们暴力求出这个序列的前$10^6$项,那么此时的最大值大概就在$P-10^3$左右。

也就是说,现在我们需要解决这样一个问题:给定$a$,求出最小的$t$使得$x^t\equiv a\pmod p$。

如果直接上BSGS的话,由于此题有多组数据,每组数据还要跑$10^3$次BSGS,绝对$T$飞。

由于模数是固定的,所以我们可以考虑对它进行一些操作。

求出$P$的原根$g$,对$P-7\times10^3\sim P-1$依次做BSGS求出对数。

假设现在给定底数$a$,需要求出$x$的离散对数。此时我们可以先求出$a$以$g$为底时模$P$的离散对数,假设为$a’$。

那么问题转化为给定$t$,求出最小的$y$满足$a’y\equiv t\pmod {P-1}$,这里$t$是$x$以$g$为底时模$P$的离散对数。

此时我们就将若干次BSGS转化为了exgcd

另外,由于$a’,P-1$都是固定的,所以每次询问我们甚至只需要做一遍exgcd

由于做$7\times 10^3$次BSGS还是很慢,为了平衡复杂度,我们可以将BSGS的块大小设为$P^{\frac{2}{3}}$左右。

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

typedef long long LL;
typedef pair<int, int> P;

int mod;

int Pow(int x, int y, int mod = ::mod) {
int res = 1;
for (; y; y >>= 1, x = (LL)x * x % mod) if (y & 1) res = (LL)res * x % mod;
return res;
}

int G(int x) {
if (x == 2) return 1;
for (int i = 2, flg = 1; i; i++, flg = 1) {
for (int j = 2; j * j < x; j++)
if ((x - 1) % j == 0 && Pow(i, (x - 1) / j, x) == 1) { flg = 0; break; }
if (flg) return i;
}
}

int g, m, step, fuck;

vector<P> buff[65536];

void insert(int x, int y) {
int t = x & 65535;
buff[t].push_back(P(x, y));
}

int query(int x) {
int t = x & 65535;
for (auto v : buff[t]) if (v.first == x) return v.second;
return -1;
}

void init() {
g = G(mod), m = pow(mod, 0.66) + 1, fuck = mod / m + 1;
int nw = 1;
for (int i = 1; i <= m; i++)
nw = (LL)nw * g % mod, insert(nw, i);
step = nw;
}

int x, y;

int exgcd(int a, int b) {
if (!b) return x = 1, y = 0, a;
int g = exgcd(b, a % b);
int t = x; x = y, y = t - a / b * y;
return g;
}

int solve(int x) {
x = Pow(x, mod - 2);
for (int i = 1, nw = x; i <= fuck; i++) {
nw = (LL)nw * step % mod;
int res = query(nw);
if (res != -1) return i * m - res;
}
assert(0);
}

int wkr[7010];

int main() {
int T; scanf("%d%d", &mod, &T), init();
for (int i = max(1, mod - 7000), step = 1; i < mod; i++, step++)
wkr[step] = solve(i);
while (T--) {
int a; scanf("%d", &a);
if (a == 1) { printf("%d\n", mod); continue; }
vector<P> res;
int lim = min(1000000, mod - 1), mx = 0;
for (int i = 0, nw = 1; i <= lim; i++) {
if (nw > mx) res.push_back(P(i, nw)), mx = nw;
if (mx >= mod - 7000) break;
nw = (LL)nw * a % mod;
}
int step = solve(a), g = exgcd(step, mod - 1), hh = (mod - 1) / g;
for (int i = max(1, mod - 7000), fuck = 1; i < mod; i++, fuck++) {
int p = wkr[fuck];
if (p % g) continue;
int tx = ((LL)x * (p / g) % hh + hh) % hh;
res.push_back(P(tx, i));
}
sort(res.begin(), res.end()), res.push_back(P(mod, mod + 1));
LL ans = 0;
for (int i = 0; i + 1 < res.size(); i++) {
int j = i;
while (j + 1 < res.size() && res[j + 1].second <= res[i].second) j++;
ans += (LL)(res[j + 1].first - res[i].first) * res[i].second;
i = j;
}
printf("%lld\n", ans);
}
}

T2 match

image-20210129191939316

先考虑$60$分怎么做。

设$f[i]$表示$s$的前$i$个字符最多能匹配上多少次$t$。

对于$s$的每个位置$i$,如果存在一种替换问号的方式,使得$s[i-|t|+1\cdots i]$能匹配上$t$,那么显然有转移$f[i]=\max(f[i],f[i-|t|]+1)$。

注意到上一次$t$匹配上的位置可能在$i-2|t|$之后,即与当前匹配有重叠部分。显然这个重叠长度一定是$t$的一个border,那么我们可以枚举$t$的所有border,另外记$g[i]$表示考虑$s$的前$i$个字符,其中$s[i-|t|+1\cdots i]$必须匹配上$t$的最大匹配次数,那么我们就可以通过$g$得到当前位的值。

由于暴力找$t$的所有border最坏$O(|t|)$,因此复杂度为$O(|s|\times |t|)$。

需要优化的部分是这个暴力跳border的过程。注意到border也有与最长回文后缀相似的结论:即一个串的所有border一定可以被划分为至多$\log$个等差数列。

单独考虑每个等差数列的转移,由于公差是确定的,如果当前位置为$i$,这个数列的公差为$d$,那么可能对$i$产生贡献的位置就只有$i-d,i-2d,\cdots$,这些位置模$d$的余数是确定的。

因此我们将所有下标按照$d$分类,每一类开个set维护当前能对$i$贡献的位置的$dp$值。如果这个等差数列的首项与末项分别为$[l,r]$,那么$i$能产生贡献的位置为$[i+l,i+r]$,我们就在处理$i+l$时将$i$的$dp$值加入set,处理$i+r+1$时从set去掉,那么处理$i$时set中最大的元素就是我们想要的$dp$值。这个步骤用单调队列同样可以实现。

另外,由于等差数列只有$\log $个,每个数列的set一共只会占用$O(n)$的空间,因此总空间为$O(n\log n)$。

最后一个问题是如何快速地求出$t$在$s$中所有可能匹配上的位置,这个可以直接用FFT做带通配符的字符串匹配。对于位置$i$,定义差异函数为

如果$s_{i+j}$为问号,那么记$s_{i+j}=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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;
const int N = 100010;

typedef long long LL;
typedef pair<int, int> P;

int Pow(int x, int y) {
int res = 1;
for (; y; y >>= 1, x = (LL)x * x % mod) if (y & 1) res = (LL)res * x % mod;
return res;
}

int r[N << 2];

void NTT(int a[], int len, int type) {
for (int i = 0; i < len; i++) if (i < r[i]) swap(a[i], a[r[i]]);
for (int mid = 2; mid <= len; mid <<= 1) {
int Wn = Pow(3, type ? (mod - 1) / mid : mod - 1 - (mod - 1) / mid);
for (int i = 0; i < len; i += mid)
for (int j = i, w = 1, t; j < i + (mid >> 1); j++, w = (LL)w * Wn % mod)
t = (LL)w * a[j + (mid >> 1)] % mod, a[j + (mid >> 1)] = (a[j] - t + mod) % mod, a[j] = (a[j] + t) % mod;
}
if (!type) for (int i = 0, inv = Pow(len, mod - 2); i < len; i++)
a[i] = (LL)a[i] * inv % mod;
}

char s[N], t[N]; int n, m, sum[N], ok[N];

void match() {
static int A[N << 2], B[N << 2], C[N << 2], D[N << 2];
for (int i = 1; i <= n; i++) {
int c = s[i] == '?' ? 0 : s[i] - 'a' + 1, c1 = t[i] - 'a' + 1;
sum[i] = (sum[i - 1] + c * c * c) % mod;
A[i] = (LL)(mod - 2) * c * c % mod, B[i] = c;
C[m - i] = c1, D[m - i] = c1 * c1;
}
int len = 1, l = 0;
while (len <= n + m) len <<= 1, l++;
for (int i = 0; i < len; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << l - 1);
NTT(A, len, 1), NTT(B, len, 1), NTT(C, len, 1), NTT(D, len, 1);
for (int i = 0; i < len; i++)
A[i] = ((LL)A[i] * C[i] + (LL)B[i] * D[i]) % mod;
NTT(A, len, 0);
for (int i = 0; i <= n - m; i++) {
int x = (sum[i + m] - sum[i] + mod) % mod;
x = (x + A[i + m]) % mod;
if (!x) ok[i + m] = 1;
}
}

int nxt[N];

void getnxt() {
for (int i = 2; i <= m; i++) {
int lst = nxt[i - 1];
while (lst && t[lst + 1] != t[i]) lst = nxt[lst];
nxt[i] = lst + (t[lst + 1] == t[i]);
}
}

multiset<P> S[21][N];
vector<tuple<int, int, P>> add[N], del[N];

P f[N], g[N];

void chkmax(P &a, P b) {
if (b.first > a.first) a = b;
}

int main() {
scanf("%s%s", s + 1, t + 1);
n = strlen(s + 1), m = strlen(t + 1), match(), getnxt();
vector<int> wkr;
for (int nw = nxt[m]; nw; nw = nxt[nw])
wkr.push_back(m - nw);
vector<int> diff, pos; vector<P> seg;
for (int l = 0; l < wkr.size(); l++) {
int r = l;
while (r + 1 < wkr.size() && wkr[r + 1] - wkr[r] == wkr[l + 1] - wkr[l]) r++;
if (l == r) pos.push_back(wkr[l]);
else diff.push_back(wkr[l + 1] - wkr[l]), seg.push_back(P(wkr[l], wkr[r]));
l = r;
}
for (int i = m; i <= n; i++) {
for (auto t : add[i]) S[get<0>(t)][get<1>(t)].insert(get<2>(t));
for (auto t : del[i]) {
int a = get<0>(t), b = get<1>(t);
S[a][b].erase(S[a][b].find(get<2>(t)));
}
if (ok[i]) {
P tmp = f[i - m];
for (auto t : pos) chkmax(tmp, P(g[i - t].first, i - t));
for (int j = 0; j < diff.size(); j++) {
int at = (i - seg[j].first) % diff[j];
if (S[j][at].size()) tmp = max(tmp, *S[j][at].rbegin());
}
g[i] = tmp, g[i].first++;
for (int j = 0; j < diff.size(); j++) {
int l = i + seg[j].first, r = i + seg[j].second;
if (l <= n) add[l].push_back(make_tuple(j, i % diff[j], P(g[i].first, i)));
if (r < n) del[r + 1].push_back(make_tuple(j, i % diff[j], P(g[i].first, i)));
}
}
f[i] = max(f[i - 1], P(g[i].first, i));
}
printf("%d\n", f[n].first);
int nw = f[n].second, lst = n + 1;
while (nw) {
for (int i = nw - m + 1; i <= nw && i < lst; i++)
if (s[i] == '?') s[i] = t[i - (nw - m)];
lst = nw - m + 1, nw = g[nw].second;
}
for (int i = 1; i <= n; i++) if (s[i] == '?') s[i] = 'a';
puts(s + 1);
}

T3 Tile

image-20210129193538449

非常有意思的一道题。

考虑这样一个暴力:从左上角到右下角依次塞俄罗斯方块,同时我们需要保证当一个块被填进去的时候轮廓线必须是凸的,此时就等价于分配编号的过程。

实际上轮廓线的变化有如下几种情况:

image-20210129195318996

考虑用一个$01$串来描述轮廓线的状态:从左下开始,如果下一步往右,那么写下一个$0$,否则写下一个$1$。

第一种情况:1110 -> 0111

第二种情况:1000 -> 0001

第三种情况:1100 -> 0101

第四种情况:1010 -> 0011

注意到四种变化中,轮廓线的第$2,3$位都没有变化,只有第一位和第四位交换了,并且第$2,3$位的状态没有影响。

那么我们可以将整个序列按照下标模$3$分类,对于每一类分开考虑,最后再将它们的方案数乘起来。

分类之后等价于这样一个问题:一个$n’\times m’$的矩阵,每次可以选择一个格子填上,要求这个格子左上方的所有格子都已经填好了。

可以发现这相当于一个$n’\times m’$的杨表,我们需要求出给杨表填数的方案数。

这个可以通过钩子定理直接计算。第$i$行$j$的列的格子的钩子等于$n-i+m-j+1$。方案数等于$(n’\times m’)!$除以所有格子的钩子数的乘积。

一条对角线上的格子的钩子数是一样的,因此我们可以每条对角线分别计算钩子数。

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

const int mod = 1e9 + 7;

typedef long long LL;

int Pow(int x, int y) {
int res = 1;
for (; y; y >>= 1, x = (LL)x * x % mod) if (y & 1) res = (LL)res * x % mod;
return res;
}

int fuck = 0;

int calc(int n, int m) {
if (n > m) swap(n, m);
int all = 1, lim = n * m; fuck += lim;
for (int i = 1; i <= n + m - 1; i++) {
int cnt = min(min(i, n + m - i), n);
all = (LL)all * Pow(n + m - i, mod - 1 - cnt) % mod;
}
return all;
}

int main() {
int T; scanf("%d", &T);
while (T--) {
int n, m; scanf("%d%d", &n, &m);
if (n * m % 3) { puts("0"); continue; }
fuck = 0;
int res = (LL)calc(n / 3, m / 3) * calc((n + 1) / 3, (m + 1) / 3) % mod * calc((n + 2) / 3, (m + 2) / 3) % mod;
for (int i = 1; i <= fuck; i++) res = (LL)res * i % mod;
printf("%d\n", res);
}
}