这是一道在 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 | dp[n][m] = dp[n-1][m] + dp[n][m-1]*prime[n] |
用人话举例来说,就是 dp[3][2]
(前两种质数中取三个)的情况是以下两种情况的求和:一是不取第三种质数,该情况等于 dp[2][2]
;二是取至少一个第三种质数,该情况的值又正好等于 dp[3][1]
的值乘以第三个质数。
这题的分析就很明了了。
**其实这样一手动打表,转移方程具体该谁乘谁加谁就很明了了,并不需要O(n),只需要O(1)**。这大概就是这题的教训了吧。
另外 Light OJ 上把 %lld
改成 I64d
,就从 9ms
卡到 3000ms
了。心态爆炸。以后还是用 iostream
吧。
最后放一下 AC 代码:
1 |
|