USACO 2020 US Open Solution

双被吊打了.jpg

T1 Sprinklers 2: Return of the Alfalfa

Description

link

Solution

观察题目性质可以发现,如果只看那些覆盖左下角的点,他们的并形成了一个递减轮廓线,并且覆盖右上角的那些点一定位于轮廓线的折处的右上角。

所以相当于是要 DP 出有多少个合法的轮廓线。

实际上还有一个问题,就是除了轮廓线上的点以外,其他的可以种洒水器的点都会有两种选择。这些点带来的方案数在 DP 中乘出来是不太现实的,转移方程会因此变得极其复杂,所以一个比较好的解决方案是把所有状态的值全部除掉一个 $2 ^{折点数量}$,最后再乘上 $2 ^{可以种洒水器的点的总数量}$ 即可。

设 $f(i, j)$ 表示已经考虑好了前 $j$ 列的轮廓线,第 $j$ 列的覆盖左下角的那个点在第 $i$ 行。(注意这里的 $i$ 可以到 $n + 1$)

转移时枚举 $k$ 表示 $[k, j]$ 这一块被当前轮廓线覆盖,可以得到转移方程:

$$
f(i, j) = \frac {\sum _{k = 1} ^j \sum _{l = 1} ^{i - 1} [(i - 1, k) \text{ is coverable}] f(l, k - 1)} 4
$$

因为这里增加了两个折点,所以除个 $4$。注意第一行和第 $n + 1$ 行考虑时只用除 $2$。

前缀优化一下就是 $O(n ^2)$ 的了。

Code

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
#include <cstdio>
#include <iostream>

#define Dec(x) (x >= mod ? x -= mod : 0)

using namespace std;

typedef long long LL;

const int maxN = 2e3 + 5;
const int mod = 1e9 + 7;
const int inv4 = 250000002;

int n;
char g[maxN][maxN];
int sum[maxN];
int f[maxN][maxN];

int FPM(int bas, int ind)
{
int res = 1;
while (ind)
{
if (ind & 1)
res = (LL)res * bas % mod;
bas = (LL)bas * bas % mod;
ind >>= 1;
}
return res;
}

int main()
{
ios::sync_with_stdio(false);
cin >> n;
int s = 0;
for (int i = 1; i <= n; ++i)
cin >> (g[i] + 1);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
s += g[i][j] == '.';
f[1][0] = sum[0] = 1;
for (int j = 1; j <= n; ++j) if (g[1][j] == '.')
f[1][j] = sum[j] = (mod + 1) >> 1;
for (int i = 1; i <= n; ++i)
{
if (i != 1)
{
for (int j = 1; j <= n; ++j)
f[i][j] += f[i][j - 1], Dec(f[i][j]);
f[i][0] = 1;
for (int j = 1; j <= n; ++j)
{
if (g[i][j] == 'W')
f[i][j] = 0;
f[i][j] = (LL)f[i][j] * inv4 % mod;
sum[j] += f[i][j], Dec(sum[j]);
}
}
for (int j = 1; j <= n; ++j)
if (g[i][j] == '.')
f[i + 1][j] += sum[j - 1], Dec(f[i + 1][j]);
}
for (int j = 1; j <= n; ++j)
f[n + 1][j] += f[n + 1][j - 1], Dec(f[n + 1][j]);
f[n + 1][0] = 1;
for (int j = 1; j <= n; ++j)
f[n + 1][j] = f[n + 1][j] * LL(mod / 2 + 1) % mod;
sum[n] += f[n + 1][n], Dec(sum[n]);
cout << (LL)sum[n] * FPM(2, s) % mod << endl;

return 0;
}

T2 Exercise

Description

link

Solution

容易发现,设 $F(x)$ 表示有多少个排列得到的置换的 lcm 是 $x$ 的倍数,那么答案就是 $\prod p ^{F(p ^c)}$,其中 $p$ 是一个质数。

注意这里的 $F(x)$ 是指数,所以只能对 $mod - 1$ 取模,这是一个合数,比较麻烦。

下面的过程是求出 $F(p ^c)$ 的过程,令 $x = p ^c$。

称一个环是合法的当且仅当其环长为 $x$ 的倍数。现在相当于是要求出有多少个排列满足其对应的置换至少有一个合法环。

考虑 DP,设 $f _i$ 表示所有大小为 $i$ 的排列中,满足「该排列所对应的置换中,没有任意一个环合法」的排列数,$g _i$ 反过来表示全部环均合法的排列数。

简单容斥,用任意排列数减去至少有一个环合法的排列数。枚举这些合法的环的环长总和为 $j$:

$$
f _i = i! - \sum _{x|j, j \le i} {i \choose j} g _j f _{i - j}
$$

现在考虑如何求出 $g _i$。

先来思考一个其他的问题:如果已经给出了一个 $n$ 的有序划分,如何求出其对应的排列数?

一种可行思路是从前往后考虑所有的环,每个环都一定会选当前剩下的最小编号,然后其他的任选。

比如第一个环大小为 $i$,那么钦定其一定会选到 $1$,其他的任选的方案数即为 ${n - 1 \choose i - 1}$,再乘上 $(i - 1)!$ 考虑圆排列。

可以发现这样操作剩下的 $n - i$ 会变成一个子问题。所以可以对 $g _i$ 这样转移:

$$
g _i = \sum _{x|j, j \le i} {i - 1 \choose j - 1} (j - 1)! g _{i - j}
$$

还有一些优化。可以发现对 $f _n$ 能产生贡献的 $f, g$ 是 $O(\lfloor \frac n x \rfloor)$ 级别的(观察转移方程,有值的 $f_i$ 总可以表示成 $(n \bmod x) + kx(k \in \mathbb{N})$ 的形式),总复杂度为 $\sum \limits _{x = 1} ^n \frac {n^2} {x ^2} = n ^2 \sum \limits _{x = 1} ^n x ^{-2} = n ^2 \frac {\pi ^2} 6 \le n ^2$。

Code

代码里用到了快速取模。

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 <cstdio>
#include <iostream>

#define Dec(x, mod) (x >= (mod) ? x -= (mod) : 0)

using namespace std;

typedef unsigned long long ULL;

const int maxN = 7505;

int n, mod;
int f[maxN], g[maxN], fac[maxN];
bool vis[maxN];
int C[maxN][maxN];

namespace Mod
{
ULL b, m;

inline void Init(int x)
{ b = x, m = ULL((__int128(1) << 64) / b); }

inline ULL Reduce(ULL a)
{
ULL q = (ULL)((__int128(m) * a) >> 64);
ULL r = a - q * b; // can be proven that 0 <= r < 2*b
return r >= b ? r - b : r;
}
} using Mod::Reduce;

int FPM(int bas, int ind)
{
int res = 1;
while (ind)
{
if (ind & 1)
res = (ULL)res * bas % mod;
bas = (ULL)bas * bas % mod;
ind >>= 1;
}
return res;
}

void Init()
{
cin >> n >> mod;
Mod::Init(mod - 1);
C[0][0] = 1;
for (int i = 1; i <= n; ++i)
{
C[i][0] = C[i][i] = 1;
for (int j = 1; j <= n; ++j)
C[i][j] = C[i - 1][j - 1] + C[i - 1][j], Dec(C[i][j], mod - 1);
}
fac[0] = 1;
for (int i = 1; i <= n; ++i)
fac[i] = Reduce((ULL)fac[i - 1] * i);
}

int DP(int x)
{
g[0] = 1;
for (int i = x; i <= n; i += x)
{
g[i] = 0;
for (int j = x; j <= i; j += x)
g[i] = Reduce(g[i] + Reduce((ULL)g[i - j] * C[i - 1][j - 1]) * fac[j - 1]);
}
f[0] = 1;
for (int i = n % x; i <= n; i += x)
{
f[i] = fac[i];
for (int v = 1; v * x <= i; ++v)
{
int j = v * x;
f[i] = Reduce(f[i] + mod - 1 - Reduce(Reduce((ULL)C[i][j] * g[j]) * f[i - j]));
}
}
return Reduce(fac[n] - f[n] + mod - 1);
}

int main()
{
ios::sync_with_stdio(false);
Init();

int ans = 1;
for (int i = 2; i <= n; ++i) if (!vis[i])
{
for (int j = i; j <= n; j += i)
vis[j] = true;
for (int j = i; j <= n; j *= i)
ans = (ULL)ans * FPM(i, DP(j)) % mod;
}
cout << ans << endl;

return 0;
}

T3

咕咕咕