251105B. 換來換去/card

計數(shù)將 \(n\) 個區(qū)分的物品劃入任意個大小 \(\ge 2\) 的不區(qū)分集合的方案數(shù)。

\[n\le 10^7 \]

首先，這個問題看起來很像貝爾數(shù)：

計數(shù)將 \(n\) 個區(qū)分的物品劃入任意個不區(qū)分集合的方案數(shù)。

這個描述中實際上隱含了集合大小 \(\ge 1\) 的條件。

考慮貝爾數(shù)的 EGF：\(\exp(\exp(x)-1)\)，這里內(nèi)層的 \(-1\) 減去了集合為空的情況。

類似地，考慮回原問題，由于集合大小 \(\ge 2\)。我們減去集合大小為 \(0\) 或 \(1\) 的情況。

所以答案的 EGF 應為 \(\exp(\exp(x)-x-1)\)。

展開：

\[\begin{align*} &e^{e^x-x-1} \\=&e^{-x}e^{e^x-1} \\=&e^{-x}\sum_k\frac 1{k!}(e^x-1)^k \\=&e^{-x}\sum_k\frac 1{k!}\sum_{j=0}^k\binom kje^{jx}(-1)^{k-j} \\=&e^{-x}\sum_k\frac 1{k!}\sum_{j=0}^k\frac{k!}{i!j!}e^{jx}(-1)^i \\=&\sum_{i+j\le n}\frac 1{i!j!}e^{(j-1)x}(-1)^i \end{align*} \]

提出第 \(n\) 項系數(shù)：

\[\begin{align*} &[{x^n}/{n!}]e^{e^x-x-1} \\=&\sum_{i+j\le n}\frac 1{i!j!}([{x^n}/{n!}]e^{(j-1)x})(-1)^i \\=&\sum_{i+j\le n}\frac 1{i!j!}(j-1)^n(-1)^i \\=&\sum_{j=0}^n\frac {(j-1)^n}{j!}\sum_{i=0}^{n-j}\frac{(-1)^i}{i!} \end{align*} \]

后半部分是一個與 \(j\) 無關的前綴和。前半部分可以通過線性篩線性求。分別預處理即可。

同樣的，我們也可以線性求單項貝爾數(shù)，按照類似的方法有：

\[ \begin{align*} &[x^n/n!]e^{e^x-1} \\=&\sum_{i+j\le n}\frac 1{i!j!}[x^n/n!]e^{jx}(-1)^i \\=&\sum_{j=0}^n\frac {j^n}{j!}\sum_{i=0}^{n-j}\frac{(-1)^i}{i!} \end{align*} \]

code

#include <iostream>
#include <algorithm>
#include <bitset>

const int N = 1e7 + 7;
typedef long long i64;

namespace # {
int n, MOD;

i64 fpow(i64 x, i64 k) {
	i64 res = 1;
	for(; k; k >>= 1, x = x * x %MOD)
		if(k & 1) res = res * x %MOD;
	return res;
}
#define inv(x) fpow((x), MOD-2)

std::bitset<N> ip;
std::basic_string<int> pr;
int pown[N];
void prime() {
	pr.clear();
	for(int i = 2; i <= n; ++i) {
		if(!ip[i]) pr += i, pown[i] = fpow(i, n);
		else ip[i] = 0;
		for(int& p: pr) {
			if(i * p > n) break;
			ip[i * p] = 1;
			pown[i * p] = 1ll * pown[i] * pown[p] %MOD;
			if(i % p == 0) break;
		}
	}
}

inline int getpow(int x) { return x == -1 ? n & 1 ? -1 : 1 : x <= 1 ? x : pown[x]; }
inline int gmod(i64 x) { return x - (x >= MOD) * MOD; }

int frac[N], ifac[N], pre[N];
inline void main() {
	std::cin >> n >> MOD;
	ifac[0] = frac[0] = 1;
	for(int i = 1; i <= n; ++i) {
		frac[i] = 1ll * frac[i-1] * i %MOD;
	}
	ifac[n] = inv(frac[n]);
	for(int i = n; i >= 1; --i) {
		ifac[i-1] = 1ll * ifac[i] * i %MOD;
	}
	pre[0] = 1;
	for(int i = 1; i <= n; ++i) {
		if(i & 1) pre[i] = gmod(pre[i-1] + MOD - ifac[i]);
		else pre[i] = gmod(pre[i-1] + ifac[i]);
	}
	prime();
	int ans = 0;
	for(int k = 0; k <= n; ++k) {
		int res = 1ll * ifac[k] * getpow(k-1) %MOD * pre[n-k] %MOD;
		ans = gmod(ans + res);
	}
	std::cout << ans << "\n";
}

};

int main() {
	freopen("card.in", "r", stdin), freopen("card.out", "w", stdout);
	std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
	int t; std::cin >> t;
	while(t--) #::main();
}

posted @ 2025-11-05 15:55 CuteNess 閱讀(33) 評論(0) 收藏舉報

刷新頁面返回頂部

CuteNess

251105B. 換來換去/card

251105B. 換來換去/card

公告