UOJ450 复读机

Vexoben

Mar 12, 2019

It takes 6 minutes to read this article.

（刷新以获取数学公式）

##　题意

群里有 $k$ 个不同的复读机。为了庆祝平安夜的到来，在接下来的 $n$ 秒内，它们每秒钟都会选出一位优秀的复读机进行复读。非常滑稽的是，一个复读机只有总共复读了 $d$ 的倍数次才会感到快乐。问有多少种不同的安排方式使得所有的复读机都感到快乐。

数据范围： $d≤3,n≤1e9$ 　 $d=1,2$ 时 $k≤500000$ 　 $d=3$ 时 $k≤1000$

题解

显然答案就是 $n! \sum_{k≥0} \frac{x^{kd}}{(kd)!}[x^n]$

cly_none说这可以单位根反演一下。

$\frac{1}{n} \sum_{i=0}^{n-1} \omega_{n}^{ki} = [n|k] $

（这个式子在FFT的时候用到过）所以原式就变成

$\sum_{k≥0} \frac{x^k}{k!} (\frac{1}{d} \sum_{i=0}^{d-1}\omega_{d}^{ki} )$

大力化简一下就是

$n!(\frac{1}{d} \sum_{i-0}^{d-1} e^{\omega_{d}^{i}x})^k[x^n]$

然后人工智慧对 $d$ 分讨：

$d=1$ ，答案就是 $k^n$

$d=2$ ，答案是 $n! (\frac{e^x+e^{-x}}{2})^k[x^n]$ ，二项式展开计算一下就是 $\frac{n!}{2^k} \sum_{i=0}^{k}\frac{(2i-k)^n}{n!}\dbinom{k}{i}$ 。

$d=3$ ，答案是 $\frac{n!}{3^k} (\sum_{i=0}^{k}\sum_{j=0}^{k-i} e^{x(\omega_{3}^{0}i+\omega_{3}^{1}j+\omega_{3}^{2}(k-i-j))}) \frac{k!}{i!j!(k-i-j)!}$ ，多项式定理大力展开计算。

#include<bits/stdc++.h>
#define fi first
#define se second
#define R register
#define mp make_pair
#define pb push_back
#define LL long long
#define Ldb long double
#define pii pair<int, int>
using namespace std;
const int mod = 19491001;

template <typename T> void read(T &x) {
	int f = 0;
	R char c = getchar();
	while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
	for (x = 0; c >= '0' && c <= '9'; c = getchar())
		x = x * 10 - '0' + c;
	if (f) x = -x;
}

int Qpow(int x, int p) {
	if (x < 0) x += mod;
	int ans = 1;
	while (p) {
		if (p & 1) ans = 1LL * ans * x % mod;
		x = 1LL * x * x % mod;
		p >>= 1;
	}
	return ans;
}

int Inv(int x) {
	return Qpow(x, mod - 2);
}

// --------------------------------------------

int n, k, d;
int fac[mod], inv[mod], fav[mod];

void init() {
	fac[0] = fav[0] = 1;
	inv[1] = fac[1] = fav[1] = 1;
	for (int i = 2; i < mod; ++i) {
		inv[i] = 1LL * -mod / i * inv[mod % i] % mod + mod;
		fac[i] = 1LL * fac[i - 1] * i % mod;
		fav[i] = 1LL * fav[i - 1] * inv[i] % mod;
	}
}

int C(int x, int y) {
	return 1LL * fac[x] * fav[y] % mod * fav[x - y] % mod;
}

void Solver1() {
	int ans = 0;
	for (int i = 0; i <= k; ++i) {
		LL tmp = 1LL * Qpow(2 * i - k, n) * C(k, i) % mod;
		if (tmp < 0) tmp += mod;
		ans = (ans + tmp) % mod;
	}
	ans = 1LL * ans * Qpow(inv[2], k) % mod;
	cout << ans << endl;
}

void Solver2() {
	int omega = Qpow(7, (mod - 1) / 3), ans = 0;
	for (int i = 0; i <= k; ++i) {
		for (int j = 0; i + j <= k; ++j) {
			LL x = (i + 1LL * j * omega + 1LL * (k - i - j) * omega * omega) % mod;
			LL c = 1LL * fac[k] * fav[i] % mod *
				fav[j] % mod * fav[k - i - j] % mod;
			LL tmp = 1LL * Qpow(x, n) * c % mod;
			ans = (ans + tmp) % mod;
		}
	}
	ans = 1LL * ans * Qpow(inv[3], k) % mod;
	cout << ans << endl;
}

int main() {
	read(n); read(k); read(d);
	init();
	if (d == 1) printf("%d\n", Qpow(k, n));
	if (d == 2) Solver1();
	if (d == 3) Solver2();
	return 0;
}