比赛链接
A. 菜
原题链接
这种题赛时能写假做法……有猪啊！
考虑维护一个栈，每次加入一颗菜，然后尝试和当前栈顶的菜合并。正确性显然。
其中如果暴力求 \(\operatorname{lcm}\) 会炸，所以考虑用 bitset 维护每个因子是否出现。
时间复杂度 \(O(\frac{nV}{\omega})\)，\(V\) 是值域。
代码
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
| #include <cstdio>
#include <algorithm>
#include <bitset>
#include <vector>
const int N = 1e5 + 5;
int n;
std::bitset<1000> a[N];
std::vector<std::bitset<1000>> stk;
int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
for(int j = 2; j <= 700; j++) if(x % j == 0) a[i][j] = 1;
}
for(int i = 1; i <= n; i++) {
stk.push_back(a[i]);
while(stk.size() >= 2 && (stk.back() & stk.end()[-2]).any()) {
auto x = stk.back(); stk.pop_back();
auto y = stk.back(); stk.pop_back();
stk.push_back(x | y);
}
}
puts(stk.size() > 1 ? "No" : "Yes");
return 0;
}
|
B. 狗
原题链接
发现 U/D 和 L/R 互不影响，所以拆成 \(2\cdot n\) 个括号序列。
容易发现每个括号序列互不影响，所以对于每个序列统计方案数和答案（所有方案中匹配上的括号数的和）然后直接算就好了。
代码
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
| #include <cstdio>
#include <algorithm>
#include <vector>
void read(int &x) {
char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
for(x = 0; '0' <= ch && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}
typedef long long LL;
const int N = 500 + 5;
const int MOD = 998244353;
int n;
int a[N][N];
char b[N][N];
std::vector<int> v[2 * N], w[2 * N];
int f[N][N], g[N][N], fv[2 * N], gv[2 * N];
void mod(int &x) { x >= MOD ? x -= MOD : 0; }
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
char ch = getchar();
while(ch < 'A' || ch > 'Z') ch = getchar();
for(int j = 1; j <= n; j++) b[i][j] = ch, ch = getchar();
}
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) read(a[i][j]);
for(int i = 1; i <= 2 * n; i++) v[i].push_back(0), w[i].push_back(0);
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++)
if(b[i][j] == 'L' || b[i][j] == 'R') v[i].push_back(b[i][j] == 'R' ? 1 : -1), w[i].push_back(a[i][j]);
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++)
if(b[j][i] == 'U' || b[j][i] == 'D') v[i + n].push_back(b[j][i] == 'D' ? 1 : -1), w[i + n].push_back(a[j][i]);
for(int k = 1; k <= 2 * n; k++) {
int sz = (int)v[k].size() - 1;
for(int i = 0; i <= sz; i++) for(int j = 0; j <= sz; j++) f[i][j] = 0, g[i][j] = -1;
f[0][0] = 1, g[0][0] = 0;
for(int i = 1; i <= sz; i++) for(int j = 0; j <= i; j++) {
mod(f[i][j] += f[i - 1][j]);
if(g[i - 1][j] >= 0) g[i][j] = g[i - 1][j];
if(0 <= j - v[k][i] && j - v[k][i] <= sz) {
LL extra = (v[k][i] == -1 ? j - v[k][i] : 1);
mod(f[i][j] += f[i - 1][j - v[k][i]] * extra % MOD);
if(g[i - 1][j - v[k][i]] >= 0) {
if(g[i][j] == -1) g[i][j] = 0;
mod(g[i][j] += (g[i - 1][j - v[k][i]] + (LL)f[i - 1][j - v[k][i]] * w[k][i] % MOD) * extra % MOD);
}
}
}
fv[k] = f[sz][0], gv[k] = g[sz][0];
}
int ans = 0;
for(int i = 1; i <= 2 * n; i++) {
LL ret = 1;
for(int j = 1; j <= 2 * n; j++) if(i != j) (ret *= fv[j]) %= MOD;
(ans += ret * gv[i] % MOD) %= MOD;
}
printf("%d\n", ans);
return 0;
}
|
C. 可
原题链接
做法 1（80 分）
首先显然题目就是求所有方案的 \(f\) 值的和。
如果 \(k=1\) 那么显然是数位 DP。
考虑如何拓展到 \(k>1\)。设 \(dp(i,j)\) 表示前 \(i\) 位，有 \(j\) 个卡上界，转移时需要再记一个 DP。总复杂度是 \(O(nk^4)\)。
做法 2（100 分）
设 \(g(s)\) 表示 \(\sum a_i = s\) 的方案数，那么就有一个经典的容斥：\(g(s) = \sum_{i=0}^i (-1)^i \binom{k}{i}\binom{s - i(x + 1) + k - 1}{k - 1}\)，其中 \(s - k(x + 1) + k - 1 < k - 1\) 时 \(\binom{s - k(x + 1) + k - 1}{k - 1}\) 定义为 \(0\)。
那么答案就是 \(\sum_{i=0}^kx f(i)g(i)\)。
推一下式子：
\[ \begin{aligned} &\sum_{i=0}^{kx} f(i)g(i)\\ =&\sum_{i=0}^{kx} f(i) \sum_{j=0}^k (-1)^j \binom{k}{j} \binom{i - j(x + 1) + k - 1}{k - 1}\\ =&\sum_{j=0}^k (-1)^j \binom{k}{j} \sum_{i=0}^{kx} f(i) \binom{i - j(x + 1) + k - 1}{k - 1} \end{aligned} \]
然后就很妙了。我们发现 \(\binom{i - j(x + 1) + k - 1}{k - 1} = \dfrac{\prod_{r = i - j(x + 1) + 1}^{i - j(x + 1) + k - 1} r}{(k - 1)!} = \prod_{r = 1}^{k - 1}\left(\dfrac{1}{(k - 1)!}i + \dfrac{-j(x + 1) + r}{(k - 1)!}\right)\)，这是一个关于 \(i\) 的 \(k - 1\) 次多项式。由于 \(k\) 很小，所以可以暴力乘出系数。我们设 \(l\) 次项的系数为 \(c(j, l)\)。但是上面我们说过当 \(s - k(x + 1) + k - 1 < k - 1\) 时 \(\binom{s - k(x + 1) + k - 1}{k - 1}\) 定义为 \(0\)，然而这里拆成多项式后就不对了。所以我们考虑将 \(\sum_{i=0}^{kx} f(i) \binom{i - j(x + 1) + k - 1}{k - 1}\) 中的 \(\sum_{i=0}^{kx}\) 改成 \(\sum_{i=j(x + 1)}^{kx}\)。
那么上式就等于
\[ \sum_{j=0}^k (-1)^j \binom{k}{j} \sum_{l=0}^{k - 1} c(j, l) \sum_{i=j(x + 1)}^{kx} f(i) i^l \]
所以现在的问题就转化成了求 \(\sum_{i=0}^{s} f(i)i^l\)（然后用 \(\left(\sum_{i=0}^{kx} f(i)i^l\right) - \left(\sum_{i=0}^{j(x + 1) - 1} f(i)i^l\right)\) 就好了）。
我们设 \(dp(i, j)\) 表示 \(\sum\limits_{t=0}^{s \bmod 10^i} f(t)t^j\)。然后我们来推式子：（没写范围的变量和上一行范围一样）
\[ \begin{aligned} &dp(i, j)\\ =&\sum_{y=0}^{s \bmod 10^i} f(y)y^j\\ =&\sum_{\substack{y\in [0, s \bmod 10^i]\\t = y \bmod 10^{i - 1}\\t' = y - t}} f(t + t') (t + t')^j\\ =&\sum_{t'} \sum_{t} f(t)f(t') \sum_{r=0}^j \binom{j}{r} t^r (t')^{j - r}\\ =&\sum_{t'} f(t') \sum_{r=0}^j \binom{j}{r} (t')^{j - r} \sum_{t} f(t)t^r\\ =&\sum_{r=0}^j \sum_{t'} f(t') \binom{j}{r} (t')^{j - r} dp(i - 1, r) \end{aligned} \]
所以单次 DP 的复杂度是 \(O(\log kx \cdot k^2) = O(k^2(\log k + \log x)) = O(k^2 \log x)\)，还带一个 \(10\) 的常数。
由于要跑 \(O(k)\) 次 DP，所以总复杂度是 \(O(k^3 \log x)\) 的。所以整道题的总复杂度也是 \(O(k^3\log x)\) 的。
是不是这样就过了呢？我们发现常熟太大，炸了。考虑优化掉 \(10\) 的常数：
\[ \begin{aligned} &\sum_{r=0}^j \sum_{t'} f(t') \binom{j}{r} (t')^{j - r} dp(i - 1, r)\\ =&\sum_{r=0}^j \left(\sum_{t'}f(t')(t')^{j-r}\right)\binom{j}{r} dp(i - 1, r) \end{aligned} \]
考虑预处理 \(sum(u, q) = \sum_{t'=0}^u f(t')(t')^q\)，就可以优化掉 \(10\) 的常数了。
最终复杂度 \(O(k^3 \log x)\)。
代码
No code yet.
D. 爱
No solution yet.