[ZOJ3899]State Reversing

试题描述

Yakumo Yukari is with no doubt one of the most powerful youkai in Gensokyo. Her ability is manipulating boundaries. She has \(N\) unknown creatures called "sinsack" or "the crime bag" which live in the basement of Yukari's house. Sinsacks are numbered from \(1\) to \(N\). There are \(M\) rooms with infinite capacity in the basement and each room has two states: available or unavailable. Yukari will reverse the state of consecutive rooms every day. Sinsacks can only live in available rooms. And each available room should contain at least one sinsack.

As a 17-year-old girl, recently Yukari is interested in how many different ways to arrange sinsacks in rooms. At the beginning, all rooms are available. In the following \(D\) days, Yukari will ask you the number of ways after reversing. Two ways \(A\) and \(B\) are regarded as the same if for any room in \(A\), there exists a room in \(B\) that the sinsacks in these two rooms have the same set of numbers. In other words, rooms are indistinguishable.

现有 \(N\) 只不同的怪兽，和 \(M\) 个相同的从 \(1\) 到 \(M\) 编号的房间，每个房间有空闲和不空闲两种状态，怪兽只能住进处于空闲状态的房间，房间容量无穷。现在给出 \(D\) 个操作，每次操作翻转一个区间 \([l_i, r_i]\) 内的房间的状态，求每次操作后分配怪兽的方案数（注意房间相同的意思是交换一个分配方案中的两个房间不算产生一个新的方案）。

所有答案均要对 \(880803841\) 取模。

输入

The first line of the input contains an integer \(T\) (\(T \le 10\)), indicating the number of cases. For each test case:

The first line contains three integers \(N\), \(M\) and \(D\) (\(1 \le M \le N\), \(D \le 100000\)). Their meanings are described above.

The following \(D\) lines each contain two integers \(l\) and \(r\) (\(1 \le l \le r \le M\)) denoting the consecutive rooms \(l, l + 1, \cdots , r\) which are reversed by Yukari on that day.

输出

For each query, output the number of different ways to arrange sinsacks. The answer should modulo \(880803841\) for it can be very large.

输入示例

输出示例

数据规模及约定

见“输入”

题解

这就是一个裸的第二类斯特林数，然后再强行加一个线段树。

第二类斯特林数 \(S(n, m)\) 表示将 \(n\) 个物品分成 \(m\) 个集合的方案数。如果暴力 \(O(n^2)\) dp 显然有 \(S(n, m) = S(n-1, m-1) + S(n-1, m) \cdot m\)，但是要想快速求 \(S(n, 1) \sim S(n, n)\)，就用不上这个 dp 了。

考虑 \(S(n, m)\) 的组合意义有

\[k^n = \sum_{m=0}^k {k \choose m} \cdot m! \cdot S(n, m)
\]

翻译一下就是将 \(n\) 个不同的物品放入 \(k\) 个不同的篮子中，可以有篮子是空的。那么这个东西其实可以先枚举有 \(m\) 个篮子非空，然后分三步完成：从 \(k\) 个篮子中取出 \(m\) 个篮子，\(m\) 个篮子排一个顺序，将 \(n\) 个物品放入 \(m\) 个篮子中，然后乘法原理即可得到上式。

然后二项式反演可得

\[k! \cdot S(n, k) = \sum_{m=0}^k (-1)^{k-m} \cdot {k \choose m} \cdot m^n \\
S(n, k) = \sum_{m=0}^k \frac{(-1)^{k-m}}{(k-m)!} \cdot \frac{m^n}{m!}
\]

于是成了一个卷积的形式。

至于那个区间操作用线段树维护应该没啥好讲的吧。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

#include <cmath>

using namespace std;

#define rep(i, s, t) for(int i = (s), mi = (t); i <= mi; i++)

#define dwn(i, s, t) for(int i = (s), mi = (t); i >= mi; i--)

int read() {

	int x = 0, f = 1; char c = getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }

	return x * f;

}

#define maxn 262144

#define MOD 880803841

#define Groot 26

#define LL long long

int Pow(int a, int b) {

	int ans = 1, t = a;

	while(b) {

		if(b & 1) ans = (LL)ans * t % MOD;

		t = (LL)t * t % MOD; b >>= 1;

	}

	return ans;

}

int brev[maxn];

void FFT(int *a, int len, int tp) {

	int n = (1 << len);

	rep(i, 0, n - 1) if(i < brev[i]) swap(a[i], a[brev[i]]);

	rep(i, 1, len) {

		int wn = Pow(Groot, MOD - 1 >> i);

		if(tp < 0) wn = Pow(wn, MOD - 2);

		for(int j = 0; j < n; j += 1 << i) {

			int w = 1;

			rep(k, 0, (1 << i >> 1) - 1) {

				int la = a[j+k], ra = (LL)w * a[j+k+(1<<i>>1)] % MOD;

				a[j+k] = (la + ra) % MOD;

				a[j+k+(1<<i>>1)] = (la - ra + MOD) % MOD;

				w = (LL)w * wn % MOD;

			}

		}

	}

	if(tp < 0) {

		int invn = Pow(n, MOD - 2);

		rep(i, 0, n - 1) a[i] = (LL)a[i] * invn % MOD;

	}

	return ;

}

void Mul(int *A, int *B, int n, int m) {

	int N = 1, len = 0;

	while(N <= n + m) N <<= 1, len++;

	rep(i, 0, N - 1) brev[i] = (brev[i>>1] >> 1) | ((i & 1) << len >> 1);

	rep(i, n + 1, N - 1) A[i] = 0;

	rep(i, m + 1, N - 1) B[i] = 0;

	FFT(A, len, 1); FFT(B, len, 1);

	rep(i, 0, N - 1) A[i] = (LL)A[i] * B[i] % MOD;

	FFT(A, len, -1);

	return ;

}

int ava[maxn<<2];

bool tag[maxn<<2];

void build(int o, int l, int r) {

	tag[o] = 0;

	if(l == r) ava[o] = 1;

	else {

		int mid = l + r >> 1, lc = o << 1, rc = lc | 1;

		build(lc, l, mid); build(rc, mid + 1, r);

		ava[o] = ava[lc] + ava[rc];

	}

	return ;

}

void pushdown(int o, int l, int r) {

	if(l == r || !tag[o]) return (void)(tag[o] = 0);

	int mid = l + r >> 1, lc = o << 1, rc = lc | 1;

	tag[lc] ^= 1; ava[lc] = mid - l + 1 - ava[lc];

	tag[rc] ^= 1; ava[rc] = r - mid - ava[rc];

	tag[o] = 0;

	return ;

}

void rev(int o, int l, int r, int ql, int qr) {

	pushdown(o, l, r);

	if(ql <= l && r <= qr) tag[o] ^= 1, ava[o] = r - l + 1 - ava[o];

	else {

		int mid = l + r >> 1, lc = o << 1, rc = lc | 1;

		if(ql <= mid) rev(lc, l, mid, ql, qr);

		if(qr > mid) rev(rc, mid + 1, r, ql, qr);

		ava[o] = ava[lc] + ava[rc];

	}

	return ;

}

int ifac[maxn], A[maxn], B[maxn];

void work() {

	int n = read(), m = read(), q = read();

	ifac[1] = 1;

	rep(i, 2, n) ifac[i] = (LL)(MOD - MOD / i) * ifac[MOD%i] % MOD;

	ifac[0] = 1;

	rep(i, 1, n) ifac[i] = (LL)ifac[i-1] * ifac[i] % MOD;

	rep(i, 0, n) {

		A[i] = (LL)Pow(i, n) * ifac[i] % MOD;

		B[i] = ifac[i]; if(i & 1) B[i] = MOD - B[i];

	}

	Mul(A, B, n, n);

	build(1, 1, m);

	while(q--) {

		int l = read(), r = read();

		rev(1, 1, m, l, r);

		printf("%d\n", A[ava[1]]);

	}

	return ;

}

int main() {

	int T = read();

	while(T--) work();

	return 0;

}

巴特西

[ZOJ3899]State Reversing