自动搬运

查看原文

来自洛谷，原作者为

	iostream Think three times, code twice and take the first place.

搬运于2025-08-24 22:14:57，当前版本为作者最后更新于2020-02-04 20:03:11，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

出题人来补上题解 qwq Latex 已重写。

公式可能显示有锅，建议到博客中查看。

首先注意到题目中 $a$ 数组是有序的，那我们只用算有序的方案乘上 $n!$ 即可。

而此时的答案显然

$$Ans=[x^n](1+x)(1+2x)\dots (1+Ax)=\prod_{i=1}^A(1+ix) $$

取对数把乘法变加法，即

$$\prod_{i=1}^A(1+ix)=\exp(\sum_{i=1}^A\ln(1+ix))$$

这里有 $\ln$ 的展开式

$$-\ln(1-x)=\sum_{i=1}^\infty\frac{x^i}{i}$$

故有

$$\begin{aligned} &\ln(1+ix)\\ &=\ln(1-(-ix))\\ &=-\sum_{k=1}^\infty \frac{(-ix)^k}{k}\\ &=\sum_{k=1}^\infty \frac{(-1)^{k+1}i^k}{k}x^k \end{aligned} $$

则

$$\begin{aligned} &\sum_{i=1}^A \ln(1+ix)\\ &=\sum_{k=1}^\infty \frac{(-1)^{k+1}\sum_{i=1}^Ai^k}{k}x^k \end{aligned} $$

自然数幂和可以用某种方法（插值、伯努利数之类）算出来。

最后还要多项式 exp，直接 $O(n^2)$ 算。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 505;

int n, M, P, inv[N], Bo[N], C[N][N], a[N], b[N];

typedef vector<int> poly;

poly F[N];

int calc(const poly&a, int x)
{
	int y = 0;
	for(int i = a.size() - 1; i >= 0; i --)
		y = (1LL * y * x + a[i]) % P;
	return y;
}

int main()
{
	scanf("%d%d%d",&M,&n,&P);
	for(int i = 0; i <= n + 1; i ++)
	{
		C[i][0] = 1;
		for(int j = 1; j <= i; j ++)
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
	}
	inv[1] = 1;
	for(int i = 2; i <= n + 1; i ++)
		inv[i] = (ll) inv[P % i] * (P - P / i) % P;
	Bo[0] = 1;
	for(int i = 1; i <= n; i ++)
	{
		int t = 0;
		for(int j = 0; j < i; j ++)
			t = (t + (ll)Bo[j] * C[i + 1][j]) % P;
		Bo[i] = (ll)(P - inv[i + 1]) * t % P;
	}
	F[0] = poly{0, 1};
	for(int i = 1; i <= n; i ++)
	{
		F[i].resize(i + 2);
		for(int j = 1; j <= i + 1; j ++)
		{
			F[i][j] = (ll) Bo[i + 1 - j] * C[i + 1][j] % P * inv[i + 1] % P;
			if((i + 1 - j) & 1)
				F[i][j] = (P - F[i][j]) % P;
		}
	}
	for(int i = 1; i <= n; i ++)
	{
		a[i] = (ll)inv[i] * calc(F[i], M) % P;
		if(~i&1) a[i] = (P - a[i]) % P;
	}
	for(int i = 1; i <= n; i ++)
		a[i - 1] = (ll)i * a[i] % P;
	b[0] = 1;
	for(int i = 1; i <= n; i ++)
	{
		for(int j = 0; j < i; j ++)
			b[i] = (b[i] + (ll)b[j] * a[i - j - 1]) % P;
		b[i] = (ll)b[i] * inv[i] % P;
	}
	int ans = b[n];
	for(int i = 2; i <= n; i ++) ans = (ll)ans * i % P;
	printf("%d", ans);
	return 0;
}

注意到复杂度瓶颈在于对所有 $k\in [1,n]$ 预处理自然数幂和。 这东西的EGF

$$\begin{aligned} &\sum_{k=0}^\infty \sum_{i=0}^A i^k \frac{x^k}{k!}\\ &=\sum_{i=0}^A \sum_{k=0}^\infty \frac{(ix)^k}{k!}\\ &= \sum_{i=0}^A e^{ix}\\ &= \frac{e^{(A+1)x}-1}{e^x-1} \end{aligned} $$

多项式求逆即可，整个复杂度也是 $O(n\log n)$。

代码需要把上面代码的暴力改成多项式全家桶。