题解：P13541 [OOI 2022] Good arrays
ChenZaiZe001
·
·
题解
题意描述
一个正整数数组是好数组，当且仅当每个数都是上一个数的因数。
求长度为 n 且每个数都不超过 c 的好数组个数。
## 动态规划
考虑不断向好数组的末尾添加新数。设 $f_{i,j}$ 表示长度为 $i$，且最小数（即末尾）为 $j$ 的好数组个数。则转移方程：
$$f_{i-1,j\times k}\to f_{i,j}\quad(j\times k\le c)$$
时间复杂度 $O(nc\log c)$，可以获得 $41$ 分。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,c;
ll f[5010][5010],ans;
const ll P=998244353;
int main(){
scanf("%d%d",&n,&c);
for(int i=1;i<=c;i++) f[1][i]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<=c;j++)
for(int k=1;j*k<=c;k++)
(f[i][j]+=f[i-1][j*k])%=P;
for(int i=1;i<=c;i++) (ans+=f[n][i])%=P;
printf("%lld",ans);
}
```
### 拉格朗日插值
考场上想到的神秘优化。每一轮更新时每个 $f_j$ 都从特定节点转移而来。转移深度每加一层，关于 $i$ 的多项式 $h(i)=f_{i,j}$ 就会加一次。
由于转移最多 $O(\log c)$ 层，题目所求的 $g(i)=\sum\limits_{j=1}^cf_{i,j}$ 为 $\lfloor\log c\rfloor$ 次多项式，所以拉格朗日插值大力求出 $g(n)$ 即可。
时间复杂度 $O(c\log^2c)$，可以获得 $57$ 分。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,c,b;
ll f[20][100010],g[20],ans;
const ll P=998244353;
ll qpw(ll a,ll b){
ll res=1;
while(b){
if(b&1) (res*=a)%=P;
(a*=a)%=P;
b>>=1;
}
return res;
}
int main(){
scanf("%d%d",&n,&c);
b=__lg(c)+1;
for(int i=1;i<=c;i++) f[1][i]=1;
g[1]=c;
for(int i=2;i<=b;i++)
for(int j=1;j<=c;j++){
for(int k=1;j*k<=c;k++)
(f[i][j]+=f[i-1][j*k])%=P;
(g[i]+=f[i][j])%=P;
}
for(int i=1;i<=b;i++){
ll res=g[i];
for(int j=1;j<=b;j++)
if(i!=j)
res=res*(n-j+P)%P*qpw(i-j+P,P-2)%P;
(ans+=res)%=P;
}
printf("%lld",ans);
}
```
## 组合数学
DP 没什么前途，开始推式子。
设长度为 $n$ 的好数组为 $a$，“差分数组”为 $b_i=\frac{a_i}{a_{i+1}}\,(1\le i<n)$。一个 $a_1$ 和差分数组唯一对应一个好数组。因此我们只需求出差分数组的个数即可。我们发现 $\prod\limits_{i=1}^{n-1}b_i=\frac{a_1}{a_n}$。所以设 $f(x)$ 为 $x=\frac{a_1}{a_n}$ 时差分数组的个数，即把 $x$ 分解成有序的 $n-1$ 个数之积的方案数。
设 $x=\prod p_i^{\alpha_i}$（$p_i$ 是质数），则每个质因子都能分到 $n-1$ 个数中，插板法 $+$ 乘法原理可得 $f(x)=\prod\binom{\alpha_i+n-2}{n-2}$。
答案为 $\sum\limits_{i=1}^c\sum\limits_{i\times j\le c} f(i)=\sum\limits_{i=1}^c\lfloor\frac{c}{i}\rfloor f(i)$。
时间复杂度 $O(c\sqrt c)$，可以获得 $57$ 分。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100020
int n,c;
ll fac[N][2],f[N],ans;
const ll P=998244353;
ll qpw(ll a,ll b){
ll res=1;
while(b){
if(b&1) (res*=a)%=P;
(a*=a)%=P;
b>>=1;
}
return res;
}
ll C(ll n,ll m){
return fac[n][0]*fac[m][1]%P*fac[n-m][1]%P;
}
ll calc(int x){
ll res=1;
for(int i=2;i*i<=x;i++){
int cnt=0;
while(x%i==0){
cnt++;
x/=i;
}
(res*=C(cnt+n-2,n-2))%=P;
}
if(x!=1) (res*=C(1+n-2,n-2))%=P;
return res;
}
int main(){
fac[0][0]=1;
for(int i=1;i<N;i++) fac[i][0]=fac[i-1][0]*i%P;
fac[N-1][1]=qpw(fac[N-1][0],P-2);
for(int i=N-1;i>=1;i--) fac[i-1][1]=fac[i][1]*i%P;
scanf("%d%d",&n,&c);
for(int i=1;i<=c;i++){
f[i]=calc(i);
(ans+=c/i*f[i]%P)%=P;
}
printf("%lld",ans);
}
```
### 欧拉筛优化
我们发现瓶颈在于枚举质因子，考虑一边线性筛一边转移。
我们知道，线性筛中每个合数 $k$ 会被 $i\times p_j$ 筛掉，其中 $p_j$ 是 $k$ 的最小质因子。由于我们要计算的 $\binom{\alpha_i+n-2}{n-2}$ 内含有 $\alpha_i$，所以我们记录 $g_k$ 表示 $k$ 的最小质因子的指数。
显然若 $i$ 为质数，$f_i=\binom{1+n-2}{n-2}$。考虑转移。
1. $i\bmod p_j=0$：这说明 $i$ 中已经含有质因子 $p_j$，现在又加一次。
$$f_i\times\frac{\binom{g_i+1+n-2}{n-2}}{\binom{g_i+n-2}{n-2}}\to f_k$$
$$g_i+1\to g_k$$
2. $i\bmod p_j\neq0$：这说明 $k$ 中含有 $i$ 所不含的更小的质因子 $p_j$。
$$f_i\times\binom{1+n-2}{n-2}\to f_k$$
$$1\to g_k$$
特别地，$f_1=1$。
时间复杂度 $O(n+c)$，可以得到 $100$……补兑！怎么 MLE/TLE 了？
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 50000030
int n,c,prime[N/10],cnt,g[N];
bool flag[N];
ll fac[N][2],f[N],ans;
const ll P=998244353;
ll qpw(ll a,ll b){
ll res=1;
while(b){
if(b&1) (res*=a)%=P;
(a*=a)%=P;
b>>=1;
}
return res;
}
ll C(ll n,ll m){
return fac[n][0]*fac[m][1]%P*fac[n-m][1]%P;
}
ll invC(ll n,ll m){
return fac[n][1]*fac[m][0]%P*fac[n-m][0]%P;
}
int main(){
fac[0][0]=1;
for(int i=1;i<N;i++) fac[i][0]=fac[i-1][0]*i%P;
fac[N-1][1]=qpw(fac[N-1][0],P-2);
for(int i=N-1;i>=1;i--) fac[i-1][1]=fac[i][1]*i%P;
scanf("%d%d",&n,&c);
f[1]=1;
for(int i=2;i<=c;i++){
if(!flag[i]){
prime[++cnt]=i;
f[i]=C(1+n-2,n-2);
g[i]=1;
}
for(int j=1;j<=cnt&&i*prime[j]<=c;j++){
int k=i*prime[j];
flag[k]=1;
if(i%prime[j]==0){
f[k]=f[i]*invC(g[i]+n-2,n-2)%P*C(g[i]+1+n-2,n-2)%P;
g[k]=g[i]+1;
break;
}else{
f[k]=f[i]*C(1+n-2,n-2)%P;
g[k]=1;
}
}
}
for(int i=1;i<=c;i++) (ans+=c/i*f[i]%P)%=P;
printf("%lld",ans);
}
```
### 卡常
针对 MLE：
* 变量/数组定义为 `int`，需要运算时临时转换为 `long long`。
针对 TLE：
* 把全局变量/数组定义在 `main()` 内，因为栈空间读写速度比堆空间快。
* 预处理 $h(x)=\binom{x+n-2}{n-2},invh(x)=\frac{1}{h(x)}$。
现在可以获得 $100$ 分。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 50000030
const int P=998244353;
int qpw(int a,int b){
int res=1;
while(b){
if(b&1) res=1ll*res*a%P;
a=1ll*a*a%P;
b>>=1;
}
return res;
}
int C(int fac[][2],int n,int m){
return 1ll*fac[n][0]*fac[m][1]%P*fac[n-m][1]%P;
}
int invC(int fac[][2],int n,int m){
return 1ll*fac[n][1]*fac[m][0]%P*fac[n-m][0]%P;
}
int main(){
int n,c,prime[N/10],cnt=0,fac[N][2],f[N],g[N],h[30],invh[30],ans=0;
bool flag[N];
fac[0][0]=1;
for(int i=1;i<N;i++) fac[i][0]=1ll*fac[i-1][0]*i%P;
fac[N-1][1]=qpw(fac[N-1][0],P-2);
for(int i=N-1;i>=1;i--) fac[i-1][1]=1ll*fac[i][1]*i%P;
memset(flag,0,sizeof(flag));
scanf("%d%d",&n,&c);
for(int i=1;i<30;i++){
h[i]=C(fac,i+n-2,n-2);
invh[i]=invC(fac,i+n-2,n-2);
}
f[1]=1;
for(int i=2;i<=c;i++){
if(!flag[i]){
prime[++cnt]=i;
f[i]=h[1];
g[i]=1;
}
for(int j=1;j<=cnt&&i*prime[j]<=c;j++){
int k=i*prime[j];
flag[k]=1;
if(i%prime[j]==0){
f[k]=1ll*f[i]*invh[g[i]]%P*h[g[i]+1]%P;
g[k]=g[i]+1;
break;
}else{
f[k]=1ll*f[i]*h[1]%P;
g[k]=1;
}
}
}
for(int i=1;i<=c;i++) ans=(ans+1ll*c/i*f[i])%P;
printf("%d",ans);
}
```