【BZOJ 4599】[JLOI2016] 成绩比较

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4559
神犇题解:http://blog.lightning34.cn/?p=286

解题报告

仍然是广义容斥原理
可以推出$\alpha(x)={{n-1}\choose{x}} \prod\limits_{i=1}^{m}{{{n-1-x}\choose{R_i-1}}\sum\limits_{j=1}^{U_i}{(U_i-j)^{R_i-1}j^{n-R_i}}}$
我们发现唯一的瓶颈就是求$f(i)=\sum\limits_{j=1}^{U_i}{(U_i-j)^{R_i-1}j^{n-R_i}}$
但我们稍加观察不难发现$f(i)$是一个$n$次多项式,于是我们可以用拉格朗日插值来求解
于是总的时间复杂度:$O(mn^2)$

Code

这份代码是$O(mn^2 \log 10^9+7)$的
实现得精细一点就可以把$\log$去掉

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200;
const int MOD = 1000000007;

int n,m,K,r[N],u[N],f[N],g[N],h[N],alpha[N],C[N][N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
} 

inline int Pow(int w, int t) {
	int ret = 1;
	for (;t;t>>=1,w=(LL)w*w%MOD) {
		if (t & 1) {
			ret = (LL)ret * w % MOD;
		} 
	}
	return ret;
}

inline int LagrangePolynomial(int x, int len, int *ff, int *xx) {
	int ret = 0;
	for (int i=1;i<=len;i++) {
		int tmp = ff[i];
		for (int j=1;j<=len;j++) {
			if (i == j) continue;
			tmp = (LL)tmp * (x - xx[j]) % MOD;
			tmp = (LL)tmp * Pow(xx[i] - xx[j], MOD-2) % MOD;
		}
		ret = (ret + tmp) % MOD;
	}
	return (ret + MOD) % MOD;
} 

int main() {
	n = read(); m = read(); K = read();
	for (int i=1;i<=m;i++) {
		u[i] = read();
	}
	for (int i=1;i<=m;i++) {
		r[i] = read();
	}
	//预处理组合数 
	C[0][0] = 1;
	for (int i=1;i<=n;i++) {
		C[i][0] = 1;
		for (int j=1;j<=i;j++) {
			C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
		}
	}
	//拉格朗日插值
	for (int w=1;w<=m;w++) {
		for (int i=1;i<=n+1;i++) {
			f[i] = 0; h[i] = i;
			for (int j=1;j<=i;j++) {
				f[i] = (f[i] + (LL)Pow(i-j, r[w]-1) * Pow(j, n-r[w])) % MOD;
			}
		}  
		g[w] = LagrangePolynomial(u[w], n+1, f, h);
	}
	//广义容斥原理 
	int ans = 0;
	for (int i=K,t=1;i<=n;i++,t*=-1) {
		alpha[i] = C[n-1][i];
		for (int j=1;j<=m;j++) {
			alpha[i] = (LL)alpha[i] * C[n-1-i][r[j]-1] % MOD * g[j] % MOD;
		}
		ans = (ans + t * (LL)C[i][K] * alpha[i]) % MOD;
	}
	printf("%d\n",(ans+MOD)%MOD);
	return 0;
}

【日常小测】魔术卡

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/06/20170614-statement.pdf

题目大意

给你$m(m \le 10^3)$种,第$i$种有$a_i$张,共$n(n = \sum\limits_{i = 1}^{m}{a_i} \le 5000)$张卡
现在把所有卡片排成一排,定义相邻两个卡片颜色相同为一个魔术对
询问恰好有$k$个魔术对的本质不同的排列方式有多少种,对$998244353$取模
定义本质不同为:至少有一位上的颜色不同

解题报告

一看就需要套一个广义容斥原理
于是问题变为求“至少有$x$个魔术对的方案数”

于是我们可以钦定第$i$种卡片组成了$j$个魔术对
然后用一个$O(n^2)$的$DP$来求出至少有$x$个魔术对的方案数

为了方便去重,我们先假设相同颜色的卡片有编号,最后再依次用阶乘除掉
考试的时候就是这里没有处理好,想的是钦定的时候直接去重,但这样块与块之间的重复就搞不了,于是$GG$了

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5009;
const int MOD = 998244353;

int n, m, K, a[N], pw[N], inv[N], f[N][N], C[N][N];

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret * f;
}

inline int Pow(int w, int t) {
	int ret = 1;
	for (; t; t >>= 1, w = (LL)w * w % MOD) {
		if (t & 1) {
			ret = (LL)ret * w % MOD;
		}
	}
	return ret;
}

int main() {
	freopen("magic.in", "r", stdin);
	freopen("magic.out", "w", stdout);
	m = read(); n = read(); K = read();
	for (int i = 1; i <= m; i++) {
		a[i] = read();
	}
	C[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		C[i][0] = 1;
		for (int j = 1; j <= n; j++) {
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
		}
	}
	pw[0] = inv[0] = 1;
	for (int i = 1; i <= n; i++) {
		pw[i] = (LL)pw[i - 1] * i % MOD;
		inv[i] = Pow(pw[i], MOD - 2);
	}
	f[0][0] = 1;
	for (int i = 1, pre_sum = 0; i <= m; i++) {
		pre_sum += a[i] - 1;
		for (int j = 0; j <= pre_sum; j++) {
			for (int k = min(a[i] - 1, j); ~k; k--) {
				f[i][j] = (f[i][j] + (LL)f[i - 1][j - k] * C[a[i]][k] % MOD * pw[a[i] - 1] % MOD * inv[a[i] - 1 - k]) % MOD;
			}
		} 
	}
	int ans = 0;
	for (int i = K, ff = 1; i < n; i++, ff *= -1) {
		f[m][i] = (LL)f[m][i] * pw[n - i] % MOD;
		ans = (ans + (LL)ff * C[i][K] * f[m][i]) % MOD;
	}
	for (int i = 1; i <= m; i++) {
		ans = (LL)ans * inv[a[i]] % MOD;
	}
	printf("%d\n", (ans + MOD) % MOD);
	return 0;
}

【BZOJ 3622】已经没有什么好害怕的了

相关链接

解题报告:http://www.lydsy.com/JudgeOnline/problem.php?id=3622

解题报告

恰好有$k$个条件满足,这不就是广义容斥原理吗?
不知道广义容斥原理的同学可以去找$sengxian$要他的$PDF$看哦!

知道广义容斥原理的同学,这题难点就是求$\alpha(i)$
设$f_{i,j}$表示考虑了前$i$个糖果,至少有$j$个糖果符合条件的方案数
那么$\alpha(i)=f_{n,i} \cdot (n-i)!$

于是先$O(n^2)$DP出$\alpha(i)$
然后根据广义容斥原理$O(n)$推出$\beta(k)$就可以了
总时间复杂度:$O(n^2)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2009;
const int MOD = 1000000009;

int n,K,a[N],b[N],sum[N],fac[N],alpha[N],f[N][N],C[N][N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	n = read(); K = read();
	if ((n + K) & 1) {
		puts("0");
		exit(0);
	} 
	K = n + K >> 1; 
	for (int i=1;i<=n;i++) {
		a[i] = read();
	}
	sort(a+1, a+1+n);
	for (int i=1;i<=n;i++) {
		b[i] = read();
	} 
	sort(b+1, b+1+n);
	for (int i=1,j=0;i<=n;i++) {
		for (;j < n && b[j+1] < a[i];++j);
		sum[i] = j;
	}
	C[0][0] = 1;
	for (int i=1;i<=n;i++) {
		C[i][0] = 1;
		for (int j=1;j<=i;j++) {
			C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
		}
	}
	fac[0] = 1;
	for (int i=1;i<=n;i++) {
		fac[i] = fac[i-1] * (LL)i % MOD; 
	}
	f[0][0] = 1;
	for (int i=1;i<=n;i++) {
		for (int j=0;j<=i;j++) {
			f[i][j] = (f[i-1][j] + (j?f[i-1][j-1] * max(0ll, (sum[i] - j + 1ll)):0ll)) % MOD;
		}
	}
	for (int i=0;i<=n;i++) {
		alpha[i] = (LL)f[n][i] * fac[n - i] % MOD;
	}
	int ans = 0;
	for (int i=K,t=1;i<=n;i++,t*=-1) {
		ans = (ans + (LL)alpha[i] * C[i][K] * t) % MOD;
	}
	printf("%d\n",(ans+MOD)%MOD);
	return 0;
}