题解：P10613 [PA2008] Cliquers

· · 题解

前言

划分数的根号分治 + DP 板子题。

不太懂本题这个输出 m^x 是干什么的（

目前不知道这个东西用古代猪文那个 trick 后模数为质数有没有什么特殊做法。

Solution

首先注意到 x 就等于 n 的划分数个数。

有一个显然的 DP：设 f_{i,j} 表示用前 i 个数来划分 j 的方案数。

转移就是 f_{i,j}=f_{i-1,j}+f_{i,j-i}，这就是个完全背包的形式。

但是直接这样做时间复杂度是 O(n^2) 的，考虑根号分治，设一个阈值 B：对于小于 B 的数，直接做完全背包即可，这部分时间复杂度是 O(nB)。

对于大于等于 B 的数，考虑划分数问题的另一种形式：将 n 表示为 k(k\le n) 个正整数的和，形如 n=\sum\limits_{i=1}^k a_i，其中 a_1\ge a_2\ge a_3\ge\dots \ge a_k，n 的划分数就等于满足这个条件的 a 序列的方案数。

考虑对这个 a 序列进行计数，由于 a 序列是单调不增的，考虑费用提前计算，将 a 序列转化为多个前缀相加，例如序列 3,2,2,1 就可以表示为 1 个 [1,1] 前缀，1 个 [1,3] 前缀和 1 个 [1,4] 前缀相加，设 f_{i,j} 表示考虑长度为 i 的序列，和为 j 的方案数，转移就是 f_{i,j}=f_{i-1,j}+f_{i,j-i}（f_{i-1,j} 就是不放 [1,i] 这个前缀的方案数，f_{i,j-i} 就是多放一个 [1,i] 前缀的方案数），这也是完全背包的形式。注意这里要保证 a_k\ge B，所以将 x 划分为 y 个数的方案数实际上是 f_{y,x-yB}，由于所有数都大于等于 B，所以 k 不会超过 \dfrac nB，这部分的时间复杂度就为 O(\dfrac{n^2}B)。

最后由于求的是 m^x，注意到 10^9-401 是一个质数，求划分数时对 10^9-402 取模，最后跑快速幂即可。

总时间复杂度就为 O(nB+\dfrac{n^2}B)，B 取 \sqrt n 时能取到最优时间复杂度 O(n\sqrt n)。

Code

//when you use vector or deque,pay attention to the size of it.
//by OldDirverTree
#include<bits/stdc++.h>
//#include<atcoder/all>
#define P pair<int,int>
#define int long long
#define mid (l+r>>1)
using namespace std;
//using namespace atcoder;
const int N=2e5+1,mod=1e9-401;
int n,m,B,res,ans=1,f[N],g[N];

int read() {
    int x=0; bool f=true; char c=0;
    while (!isdigit(c) ) f&=(c!='-'),c=getchar();
    while (isdigit(c) ) x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return f?x:-x;
}
main()
{
    n=read(),m=read(),B=sqrt(n),f[0]=g[0]=1;
    for (int i=1;i<B;i++) for (int j=i;j<=n;j++)
    f[j]=(f[j]+f[j-i])%(mod-1); res=f[n];
    for (int i=1;i<=n/B;i++) {
        for (int j=i;j<=n;j++) g[j]=(g[j]+g[j-i])%(mod-1);
        for (int j=0;j<=n-i*B;j++) res=(res+f[j]*g[(n-j)-i*B]%(mod-1) )%(mod-1);
    }
    while (res) {
        if (res&1) ans=ans*m%mod;
        m=m*m%mod,res>>=1;
    }
    printf("%lld",ans);
    return 0;
}