自动搬运

查看原文

来自洛谷，原作者为

	OldDriverTree 人間になりたい

搬运于2025-08-24 22:59:39，当前版本为作者最后更新于2024-08-22 17:28:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

划分数的根号分治 + 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;
}