【国家集训队】calc

发表于 | 更新于
https://www.luogu.com.cn/problem/P4463

题目链接

【国家集训队】calc

做法

$ f_{i, j} $ 表示 递增 序列中前 i 个数，最后一个数为 $ \leq j $ 的权值和。 $ f_{i, j} = j \times f_{i - 1, j - 1} + f_{i, j - 1} $ 。
发现这样做复杂度 $ O(nA) $ ，过不去。
将 $ f_{i, j} $ 差分后得 $ g_{i, j} $ ，可以用关于 j 的多项式表示。考虑转移过程，即求前缀和在乘上 j，次数 +2 。
由此得证 $ f_{i, j} $ 可以被表示成 2n 次多项式。
拉格朗日插值即可，复杂度 $ O(n^2) $ 。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 1010;
int mx, n, p, ans = 1, sum = 0;
int f[N][N];
int X[N], Y[N];

int ksm(int x, int y = p - 2) {
	int w = 1; for(; y; y >>= 1, x = 1ll * x * x % p) if(y & 1) w = 1ll * w * x % p; return w;
}
int main() {
	scanf("%d%d%d", &mx, &n, &p);
	rep(i, 1, n) ans = 1ll * ans * i % p;
	rep(i, 0, n + n + 1) f[0][i] = 1;
	rep(i, 1, n) {
		rep(j, 1, n + n + 1) f[i][j] = 1ll * f[i - 1][j - 1] * j % p;
		rep(j, 1, n + n + 1) f[i][j] = (f[i][j - 1] + f[i][j]) % p;
	}
	rep(i, 1, n + n + 1) X[i] = i, Y[i] = f[n][i];
	rep(i, 1, n + n + 1) {
		int sum1 = Y[i], sum2 = 1;
		rep(j, 1, n + n + 1) if(i != j) {
			sum1 = 1ll * sum1 * (mx - X[j] + p) % p;
			sum2 = 1ll * sum2 * (X[i] - X[j] + p) % p;
		}
		sum = (sum + 1ll * sum1 * ksm(sum2) % p) % p;
	}
	printf("%lld\n", 1ll * ans * sum % p);
	return 0;
}