这是一道在 2019 暑期集训做到的题。

链接:https://vjudge.net/contest/312000#problem/G

这个题意是给定 $k$ 和 $p$,要求 $\varphi(x)$ 之和,$x$ 的质因数分解有 $k$ 个质数并且包含且只包含质数表前 $p$ 个(下称“前 $p$ 种”)质数。$k, p \leq 500$。

当时做这个题的时候,直接就交了一个 $O(n^3)$ 的 DP 上去,就 T 掉了。还以为是被卡常了,结果发现标程是 $O(n^2)$ 的。(LightOJ 真是慢,n = 500 O(n^3) 都过不了,别人 CodeForces n=10000 O(n^2) 就能卡过去

转换以后,我认为题意是要从前 $p$ 种质数中枚举 $k-p$ 个数(可重复),然后相乘求和,类似于 $n$ 球放进 $m$ 盒问题,每一个 dp[m][n] 都是由 dp[m-1][t] $0 \leq t \leq n$ 得到的,就写了一个 $O(n^3)$ 的算法。

但实际上这个题,每个 dp[m][n] 可以由 dp[m-1][n-1]dp[m][n-1] 得到。因为这是数学问题(指涉及到了一堆乘法和加法)。

看到别人的 dp 转移方程我是懵逼的,但是我尝试者打表举例来说:

同样是按照我的定义来说吧:从前 $n$ 种质数中取 $m$ 个数(可重复)。dp[0][0] = 1。

dp[n][m] n=1 n=2 n=3 n=4
m=1 dp[1][1]
=2
dp[2][1]=
2+3
dp[3][1]=
2+3+5
dp[4][1]=
2+3+5+7
m=2 dp[2][1]
=2*2
dp[2][2]=
2*2+2*3
+3*3
dp[3][2]=
2*2+2*3+3*3
+2*5+3*5+5*5
dp[4][2]=2*2+2*3+3*3+2*5+3*5+5*5
+2*7+3*7+5*7+7*7
m=3 dp[3][1]
=2*2*2
dp[3][2]=2*2*2+dp[2][2]*3 dp[3][3]=
2*2*2+2*2*3+2*3*3+3*3*3
+dp[3][2]*5
数据过长,略

写完 $m=2$,貌似已经可以看到一点规律了:

1
2
dp[n][m] = dp[n-1][m] + dp[n][m-1]*prime[n]
(dp[0][i] = 1)

用人话举例来说,就是 dp[3][2](前两种质数中取三个)的情况是以下两种情况的求和:一是不取第三种质数,该情况等于 dp[2][2];二是取至少一个第三种质数,该情况的值又正好等于 dp[3][1] 的值乘以第三个质数。

这题的分析就很明了了。

其实这样一手动打表,转移方程具体该谁乘谁加谁就很明了了,并不需要O(n),只需要O(1)。这大概就是这题的教训了吧。

另外 Light OJ 上把 %lld 改成 I64d,就从 9ms 卡到 3000ms 了。心态爆炸。以后还是用 iostream 吧。

最后放一下 AC 代码:

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
#include<bits/stdc++.h>
//#define _CRT_SECURE_NO_WARNINGS
#define ld long double
#define ll long long
#define int ll
#define eps 1e-11
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef pair<int, int> P;
const int maxn = 1e4 + 5, mod = 1e9 + 7;

bool vis[maxn] = { 0 };
int prime[maxn], cnt = 0;
void euler(int n)
{
for (int i = 2; i < n; i++)
{
if (!vis[i]) prime[cnt++] = i, vis[i] = 1;
for (int j = 0; j < cnt && i * prime[j] < n; j++)
{
vis[i*prime[j]] = 1;
if (i%prime[j] == 0)
break;
}
}
}

int dp[505][505] = { 0 }, base[505];

signed main()
{
//ofstream fout("out.txt");
fastio;
euler(maxn);
for (int n = 1; n <= 501; n++)
{
dp[n][0] = 1;
for (int m = 1; m <= 501; m++)
{
dp[n][m] = dp[n - 1][m] + dp[n][m - 1] * prime[n - 1];
dp[n][m] %= mod;
}
}
base[0] = 1;
for (int i = 1; i <= 500; i++)
{
base[i] = base[i - 1] * (prime[i - 1] - 1);
base[i] %= mod;
}
int T;
scanf("%I64d", &T);

for (int kase = 1; kase <= T; kase++)
{
int k, p;
scanf("%I64d%I64d", &k, &p);

printf("Case %I64d: %I64d\n", kase, dp[p][k - p] * base[p] % mod);
}
}