称一个长度为 nn，元素取值∈[1,D]\in[1,D]的整数序列是合法的，当且仅当其中能够选出至少 mm 对相同元素（不能重复选出元素）

问合法序列个数，答案对998244353998244353取模

n,m≤109,D≤105n, m\le 10^9, D\le 10^5

LOJ 3120

Solution

打ACM的时候做到一道这道题的弱化版本，就干脆把这道题搞了

首先，因为DD范围比较小，考虑和DD（即颜色种类）相关的做法

题目要求的东西并不好直接算，因为一种颜色可能有多次贡献，于是考虑统计奇数的方案数

设颜色为ii的数量为cic_i，那么一种方案合法，当且仅当

也就是满足 的颜色种数不能超过n−2mn-2m

先特判 n−2m≥Dn-2m \ge D 和 n−2m<0n-2m < 0的情况，答案分别为 DnD^n和 00

设fif_i为满足 的颜色种数恰好为ii的方案数，那么

ans=∑i=0n−2mfi ans = \sum_{i=0}^{n-2m}f_i

考虑求ff

最直观的方案是直接算

fi=(Di)n![xn](ex−e−x2)i⋅(ex+e−x2)D−i f_i = \binom{D}{i} n![x^n]\Big(\frac{e^x-e^{-x}}{2}\Big)^i\cdot \Big(\frac{e^x+e^{-x}}{2}\Big)^{D-i}

后面那一堆生成函数，就是有ii个只能选奇数个数的物品，和D−iD-i个只能选偶数个数的物品，把它们排列起来的方案数

乘(Di)\binom{D}{i}是因为要确定这ii个只能选奇数个的物品到底是哪ii个（后面那一堆生成函数中并没有考虑这个问题！但一旦确定下来，就不需要考虑这ii个的顺序了，顺序会在生成函数中被考虑到）

但是这里有两个(ex−e−x2)i(\frac{e^x-e^{-x}}{2})^i这样的东西，需要用二项式定理展开两次，不好算，于是考虑容斥，把其中一个变成更简洁的形式

根据广义容斥原理，设gig_i为满足 的颜色种数至少为ii的方案数

fi=∑j=iD(−1)j−i(ji)gj=1i!×∑j=iD(−1)j−i(j−i)!×j!⋅gj=1i!×∑k=0D−i(−1)k−(k)!×(k+i)!⋅gk+i \begin{aligned} f_i &= \sum_{j=i}^{D}(-1)^{j-i}\binom{j}{i}g_j\\ &= \frac{1}{i!}\times \sum_{j=i}^{D}\frac{(-1)^{j-i}}{(j-i)!}\times j!\cdot g_j\\ &= \frac{1}{i!}\times \sum_{k=0}^{D-i}\frac{(-1)^{k}}{-(k)!}\times (k+i)!\cdot g_{k+i}\\ \end{aligned}

把后面那部分翻转

=1i!×∑k=0D−i(−1)k−(k)!×(D−k−i)!⋅gD−k−i \begin{aligned} &= \frac{1}{i!}\times \sum_{k=0}^{D-i}\frac{(-1)^{k}}{-(k)!}\times (D-k-i)!\cdot g_{D-k-i}\\ \end{aligned}

显然可以卷积，考虑求gg

gi=(Di)n![xn](ex−e−x2)i(ex)D−i g_i = \binom{D}{i} n![x^n]\Big(\frac{e^x-e^{-x}}{2}\Big)^i(e^x)^{D-i}

原理和上面相同

这样就只需要进行一次二项式展开了

gi=(Di)n!2i[xn](ex−e−x)i(ex)D−i=(Di)n!2i[xn]∑j=0i(ij)(ex)j(−e−x)i−j⋅(ex)D−i=(Di)n!2i[xn]∑j=0i(ij)(−1)i−je(D−2(i−j))x \begin{aligned} g_i &= \binom{D}{i}\frac{n!}{2^i}[x^n]\Big(e^x-e^{-x}\Big)^i(e^x)^{D-i}\\ &= \binom{D}{i}\frac{n!}{2^i}[x^n]\sum_{j=0}^{i}\binom{i}{j}(e^x)^j(-e^{-x})^{i-j}\cdot (e^x)^{D-i}\\ &= \binom{D}{i}\frac{n!}{2^i}[x^n]\sum_{j=0}^{i}\binom{i}{j}(-1)^{i-j}e^{(D-2(i-j))x}\\ \end{aligned}

根据泰勒展开，有[xn]eax=ann!\displaystyle [x^n]e^{ax} = \frac{a^n}{n!}

gi=(Di)n!2i[xn]∑j=0i(ij)(−1)i−j(D−2(i−j))n=D!2i(D−i)!∑j=0i(−1)i−j⋅(D−2(i−j))n(i−j)!×1j! \begin{aligned} g_i &= \binom{D}{i}\frac{n!}{2^i}[x^n]\sum_{j=0}^{i}\binom{i}{j}(-1)^{i-j}\Big(D-2(i-j)\Big)^{n}\\ &=\frac{D!}{2^{i}(D-i)!}\sum_{j=0}^i \frac{(-1)^{i-j}\cdot \Big(D-2(i-j)\Big)^{n}}{(i-j)!}\times\frac{1}{j!} \end{aligned}

卷积即可

Code

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e6 + 100;
const int Mod = 998244353;

namespace MATH
{
	int fac[Maxn], ifac[Maxn];

	inline void Add (int &a, int b) { if ((a += b) >= Mod) a -= Mod; }

	inline int Pow (int a, int b)
	{
		int ans = 1;
		for (int i = b; i; i >>= 1, a = (LL) a * a % Mod) if (i & 1) ans = (LL) ans * a % Mod;
		return ans;
	}

	inline void init (int n = Maxn - 10)
	{
		fac[0] = 1;
		for (int i = 1; i <= n; ++i) fac[i] = (LL) fac[i - 1] * i % Mod;
		ifac[n] = Pow (fac[n], Mod - 2);
		for (int i = n - 1; i >= 0; --i) ifac[i] = (LL) ifac[i + 1] * (i + 1) % Mod;
	}

	inline int C (int n, int m) { if (n < m) return 0; return (LL) fac[n] * ifac[m] % Mod * ifac[n - m] % Mod; }
}

using namespace MATH;

namespace Poly
{
	const int g = 3;
	int n, rev[Maxn];

	inline void init (int N)
	{
		for (n = 1; n <= 2 * N; n <<= 1);
		for (int i = 0; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) + ((i & 1) ? (n >> 1) : 0);
	}

	inline void dft (int *A, int fl)
	{
		for (int i = 0; i < n; ++i) if (rev[i] < i) swap (A[i], A[rev[i]]);

		for (int mid = 1; mid < n; mid <<= 1)
		{
			int Wn = Pow (g, (Mod - 1) / (mid << 1));
			if (fl == -1) Wn = Pow (Wn, Mod - 2);
			for (int i = 0; i < n; i += mid << 1)
				for (int j = i, W = 1; j < i + mid; ++j, W = (LL) W * Wn % Mod)
				{
					int x = A[j], y = (LL) W * A[j + mid] % Mod;
					A[j] = (x + y) % Mod;
					A[j + mid] = (x - y + Mod) % Mod;
				}	
		}

		if (fl == -1) for (int i = 0, inv = Pow (n, Mod - 2); i < n; ++i) A[i] = (LL) A[i] * inv % Mod;
	}

	inline void mul (int *A, int *B, int *C, int N)
	{
		static int F[Maxn], G[Maxn];
		for (int i = 0; i < n; ++i) F[i] = (i <= N) ? A[i] : 0; 
		for (int i = 0; i < n; ++i) G[i] = (i <= N) ? B[i] : 0; 

		dft (F, 1), dft (G, 1);
		for (int i = 0; i < n; ++i) F[i] = (LL) F[i] * G[i] % Mod;
		dft (F, -1);
		for (int i = 0; i <= 2 * N; ++i) C[i] = F[i];
	}	
}

int N, M, D;
int F[Maxn], G[Maxn];
int A[Maxn], B[Maxn];

inline void Solve ()
{
	if ((LL) N - 2ll * M >= D) return void (printf("%d\n", Pow (D, N)));
	if ((LL) N - 2ll * M <  0) return void (puts("0"));

	Poly :: init (D);

	for (int i = 0; i <= D; ++i) A[i] = (LL) Pow (Mod - 1, i) * Pow (D - 2 * i + Mod, N) % Mod * Pow (fac[i], Mod - 2) % Mod;
	for (int i = 0; i <= D; ++i) B[i] = Pow (fac[i], Mod - 2);
	Poly :: mul (A, B, G, D);
	for (int i = 0; i <= D; ++i) G[i] = (LL) G[i] * fac[D] % Mod * Pow ((LL) Pow (2, i) * fac[D - i] % Mod, Mod - 2) % Mod;

	for (int i = 0; i <= D; ++i) A[i] = (LL) Pow (Mod - 1, i) * Pow (fac[i], Mod - 2) % Mod;
	for (int i = 0; i <= D; ++i) B[i] = (LL) fac[i] * G[i] % Mod;
	reverse (B, B + D + 1);
	Poly :: mul (A, B, F, D);
	reverse (F, F + D + 1);
	for (int i = 0; i <= D; ++i) F[i] = (LL) F[i] * ifac[i] % Mod;

	int ans = 0;
	for (int i = 0; i <= N - 2 * M; ++i) Add (ans, F[i]);
	cout << ans << endl;
}

inline void Input ()
{
	D = read<int>(), N = read<int>(), M = read<int>();
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif

	MATH :: init ();
	Input ();
	Solve ();

	return 0;
}