szhlg 负责内容:

拉格朗日插值:

f(k)=\sum_{i=1}^n y_i \prod_{j!=i}\frac{k-x_j}{x_i-x_j}

证明:

带入 $x_i$ ,我们会发现除了前面系数为 $y_i$ 的,后面乘积项都会有一个0,然后就没值

然鹅只有在 $y_i$ 这项,会使得上面和下面都一样,约分后是1

如果有 $x_i=i$

我们可以预处理阶乘,以及k左右的阶乘,就能实现O(n)啦

重心拉格朗日插值

我们处理

g=\prod_{i=1}^n(k-x_i)

t_i=\frac{y_i}{\prod_{i!=j}x_i-x_j}

f_k=g*\sum_{i=0}^n\frac{t_i}{k-x_i}

不难发现,如果给出k(求k处的值),我们能做到O(n)插入一个点O(1)查询

如果不给出k,也可以用多项式除二项式实现O(n^2)预处理O(n)插入的维护多项式优秀复杂度qwq

多项式除法:

eg:

$(x^3+x^2+x+1)/(x+1)$

我们有消掉第一项

$-x^2*(x+1)$

那么答案的第一项就是 $x^2$

剩下(x+1)

$-(x+1)$

第二项是1

所以除法结果就是 $(x^2+1)$

$(x^2+1) * (x+1)$

question1:

求

\sum_{i=0}^n\sum_{j=1}^{a+id}\sum_{k=1}^j k^K

$K<=100,a,d,n<=1e9$

做法:

分步拉格朗日插值

首先我们最内层循环是一个 $\sum_{k=1}^j k^K$

自然幂数和,可以 $O(k^3)$ 插值出多项式

然后观察第二层 $\sum_{j=1}^{a+id}f_j$

是 $K+2$ 的多项式,可以插值出来,其中每一个点值带入进去要 $O(K)$

也是 $K^3$

然后观察第三层,也一样,是 $K+3$ 次多项式,带入一个点值要 $O(K)$ ,在插值出第二层的基础上qwq

P4463 [集训队互测2012] calc

我的做法好像是容斥,,,汗

你考虑dp

因为既然不同那么我们一定是选了一些出来,然后这些全排列了一下得到了所以方案

$f_{i,j}$ 表示前i个数,然后最后一个数是[1,j]的所有不同的合法序列权值之和

要么放,要么不放,得到

$f_{i,j}=f_{i-1,j-1}*j+f_{i,j-1}$

答案是 $f_{n,A}*n!$

然后呢?我们TLE了

但是转移式子这么简单我们真的不考虑插值吗?

就像NOI2019那个斗地主一样我们弄出几项然后剩下的直接插值出来就好啦

$f_{n,i}$ 是i的 $g_n$ 次多项式

观察式子我们有

f_{n,i}-f_{n,i-1}=f_{n-1,i-1}*i

g_n-1=g_{n-1}+1

n=0时就是0

那么有 $g_n=2n$

另外还有一个观察方式:

不考虑这个互不相等的限制,我们有答案是 $(k*(k+1)/2)^n$ ,显然相等的情况不是一个数量级的,所以是2n次的

所以是2n次多项式,只要求出 $f_{n,1}到f_{n,2n+1}$

也就是说我们dp出这些东西的答案,然后插值即可qwq

麻蛋你DP的定义是前缀和所以初始化一定别搞错了!


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2000;
int n, k, P;

ll f[MAXN][MAXN];

inline void add(ll &x, ll y) {
	x += y;
	if(x >= P)x -= P;
}

inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}

inline void init1() {
	int K = 2 * n + 1;
	for(int j = 0; j <= K; ++j)f[0][j] = 1;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= K; ++j) {
			add(f[i][j], (f[i - 1][j - 1] * j % P + f[i][j - 1]) % P);
			// printf("%lld ", f[i][j]);
		}
		// puts("");
	}

}

inline ll chazhi(int N, ll k) {
	if(k <= 2 * N + 1) {
		return f[N][k];
	}
	ll g = 1;
	k %= P;
	for(int i = 1; i <= 2 * N + 1; ++i) {
		g = g * ((k - i + P) % P) % P;
	}
	ll S = 0;
	for(int i = 1; i <= 2 * N + 1; ++i) {
		ll tc = f[N][i];
		for(int j = 1; j <= 2 * N + 1; ++j) {
			if(i != j) {
				tc = tc * ksm((i - j + P) % P, P - 2) % P;
			}
		}
		add(S, tc * ksm(k - i, P - 2) % P * g % P);
	}
	return S;
}

int main() {
	scanf("%d%d%d", &k, &n, &P);
	init1();//dp
	ll ans = chazhi(n, k);
	for(int i = 1; i <= n; ++i)ans = ans * i % P;
	printf("%lld\n", ans);
	return 0;
}

P3270 [JLOI2016]成绩比较

毒瘤啊

~~也不是~~

我们可以考虑枚举B的成绩,然后因为每一科是独立的,所以每一科合法方案数乘起来就是总方案

考虑容斥, $f_i$ 表示至少i个人被碾压的方案数

只看第i科的,因为有枚举分数后固定人数的比他菜所以:

f_i=\sum_{j=1}^{u_i}j^{n-r_i}*(u_i-j)^{r_i-1}

然后外层我们要枚举那些人比他菜,以及这个课又有那些人菜过他

就是说先钦点i个比B菜,然后再选出剩下的人他们填充上B在j这一科的排名qwq

ans=\binom{n}{i}\prod_{j=1}^n\binom{n-i-1}{n-r_j-i} f_j

坏事了,解决一下,二项式反演

f_i=\sum_{j=1}^{u_i}j^{n-r_i}*\sum_{x=0}^{r_i-1}\binom{r_i-1}{x}u_i^x*(-j)^{r_i-1-x}

f_i=\sum_{x=0}^{r_i-1}\binom{r_i-1}{x}u_i^x(-1)^{r_i-1-x}\sum_{j=1}^{u_i}j^{n-x-1}

里面是一个自然幂数求和,所以可以插值出

然后我们有容斥吗,所以说要二项式反演,把恰好给容出来

\sum_{i=k}^{n-1}(-1)^{i-k}\binom{i}{k}ans_i

数数西格玛,直接做是TLE的

但是因为内层这个f好像对于每一科都只有 $u_i,r_i$ 不同,也就是说我们可以花费 $n^2m$ 的时间把所有这个f_j算出来,然后外面直接容斥复杂度就是 $O(nm)$ 的了

也就做完啦

一遍过/jk

#include<bits/stdc++.h>
#define ll long long
const int MAXN = 300;
const int P = 1e9 + 7;
int m, k, u[MAXN], r[MAXN];

ll fac[MAXN], ifac[MAXN];
ll tmpX[MAXN], tmpY[MAXN];


inline void add(ll &x, ll y) {
	x += y;
	if(x >= P)x -= P;
}

inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}

inline ll C(ll x, ll y) {
	if(x < y)return 0;
	return fac[x] * ifac[y] % P * ifac[x - y] % P;
}

inline void init(int n) {
	fac[0] = ifac[0] = 1;
	for(int i = 1; i <= n; ++i)fac[i] = fac[i - 1] * i % P;
	ifac[n] = ksm(fac[n], P - 2);
	for(int i = n - 1; i >= 1; --i)ifac[i] = ifac[i + 1] * (i + 1) % P;
	return;
}

ll f[MAXN];
ll tc[MAXN][MAXN];

//预处理N^的,注意是N+1次qaq,是N+2个点
inline void chazhi1(int N) {
	for(int i = 1; i <= N + 2; ++i) {
		tmpX[i] = i;
		tmpY[i] = 0;
		for(int j = 1; j <= i; ++j) {
			add(tmpY[i], ksm(j, N));
		}
	}
	for(int i = 1; i <= N + 2; ++i) {
		tc[N][i] = tmpY[i];
		for(int j = 1; j <= N + 2; ++j) {
			if(i != j) {
				tc[N][i] = tc[N][i] * ksm((tmpX[i] - tmpX[j] + P) % P, P - 2) % P;
			}
		}
	}
	return;
}

inline ll chazhi2(int N, ll w) {
	if(N == 0)return w;//qwq
	if(N < 0)return 0;
	ll g = 1;
	if(w <= N + 2) {//坏了
		ll ans = 0;
		for(int i = 1; i <= w; ++i) {
			add(ans, ksm(i, N));
		}
		return ans;
	}
	for(int i = 1; i <= N + 2; ++i) {
		g = g * ((w - i + P) % P) % P;
	}//全上!
	ll tmp = 0;
	for(int i = 1; i <= N + 2; ++i) {
		add(tmp, g * tc[N][i] % P * ksm((w - i + P) % P, P - 2) % P);
	}
	return tmp;
}

inline void init2(int n) {
	for(int i = 1; i <= n; ++i) {
		chazhi1(i);
	}
	for(int i = 1; i <= m; ++i) {
		for(int x = 0; x <= r[i] - 1; ++x) {
			ll t = C(r[i] - 1, x) * ksm(u[i], x) % P;
			t = (r[i] - 1 - x) & 1 ? (P - t) : t;
			t = t * chazhi2(n - x - 1, u[i]) % P;
			add(f[i], t);
		}
	}
	return;
}

int n;
ll ans[MAXN];

int main() {
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= m; ++i)scanf("%d", &u[i]);
	for(int i = 1; i <= m; ++i)scanf("%d", &r[i]);
	init(n);
	init2(n);
	//预处理插值函数,和f
	//这里用下On单点回答,要不然T了
	for(int i = 1; i <= n; ++i) {
		ans[i] = C(n - 1, i);
		for(int j = 1; j <= m; ++j) {
			ans[i] = ans[i] * C(n - i - 1, n - r[j] - i) % P;
			ans[i] = ans[i] * f[j] % P;
		}
	}
	ll qwq = 0;
	for(int i = k; i <= n - 1; ++i) {
		if((i - k) & 1)add(qwq, P - C(i, k) * ans[i] % P);
		else add(qwq, C(i, k) * ans[i] % P);
	}
	printf("%lld\n", qwq);
	return 0;
}

P4593 [TJOI2018]教科书般的亵渎

显然答案是一个m+1次多项式,我们要用m+1次啊

然后插值出总的n的答案,再去减去每个点值的即可qwq

其实没有那么简单,要枚举一下的,因为每用一次都自闭一次qwq


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 1e9 + 7;
const int MAXN = 100;
int T,  m;
ll a[MAXN];
ll ans, n;

inline void add(ll &x, ll y) {
	x += y;
	if(x >= P)x -= P;
}

inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}

ll dx[MAXN], dy[MAXN];

//插值出m次多项式
inline ll solve(ll n, int m) {
	//m+1个点值
	for(int t = 1; t <= m + 1; ++t) {
		dx[t] = t;
		dy[t] = 0;
		for(int g = 1; g <= t; ++g) {
			add(dy[t], ksm(g, m - 1));//qwq
		}
	}
	ll S = 0;
	for(int i = 1; i <= m + 1; ++i) {
		ll tmp = 0;
		tmp = dy[i];
		for(int j = 1; j <= m + 1; ++j) {
			if(i != j) {
				tmp = tmp * ((n - dx[j] + P) % P) % P * ksm((dx[i] - dx[j] + P) % P, P - 2) % P;
			}
		}
		add(S, tmp);
	}
	return S;
}
int main() {
	scanf("%d", &T);
	for(int i = 1; i <= T; ++i) {
		scanf("%lld%d", &n, &m);
		ans = 0;
		for(int i = 1; i <= m; ++i) {
			scanf("%lld", &a[i]);
		}
		sort(a + 1, a + m + 1);
		for(int i = 0; i <= m; ++i) {
			add(ans, solve(n - a[i], m + 2));
			for(int j = i + 1; j <= m; ++j)
				add(ans, P - ksm((a[j] - a[i] + P) % P, m + 1));
		}
		printf("%lld\n", ans);
	}
	return 0;
}

qwqchang 负责内容:

csp.ac 教科书般的亵渎

概述:带插入区间mex

做法:首先我们带插入是很令人死亡的一个事情,因为支持变更序列的也就平衡树一个了

所以说我们直接先预处理好所有的仆从位置,然后再挨个的点亮即可

显然可以用平衡树模拟,但是不能set,所以我们不能平衡树

怎么做呢?假设最后有n个仆从,那么我们可以把线段树n个位置变为1,然后从最后一个仆从向前找,假设插入到序列i号位置那么第i个仆从就找序列的从左向右第i个1,然后把它变成0,表示这个位置就是仆从i的位置qwq线段树二分即可

因为我们的影响是后面的会影响前面的,也就是说只看最后一个他的排名一定是对的,然后去掉最后一个看倒数第二个他的排名也是对的......这样子

然后我们考虑怎么实现区间mex,先二分答案,然后对于这一层的所有询问和修改,我们不能扫描线

但是可以考虑每个元素插入到线段树里维护一个lst数组表示这个元素上个元素的位置,如果没有就是0,并且在序列结尾插入一些哨兵指向前面,使得每个都被lst指到了

那么如果此时答案满足一个询问[l,r],显然所有的元素的在[r+1,n]这一段区间的lst位置的最小值都会在[l,r]区间范围内

因为mex使得[l,r]区间是一个充要的分割点使得lst都跳不过去吗~~

所以我们不打乱时间顺序的情况下可以这样用n个set维护相同血量的怪物前驱后继下标 qwq

注意向右边递归要不需要减去什么呢

HDU3842

n个机器， $d_i$ 天售出，有 $p_j$ 价格

买入则于第二天开始工作,每日收益 $g_i$

二手价 $l_i$ ,每次手上最多只能有一台机器

一开始有C元，问D+1天最大收益

可以考虑dp,按照价格排序, $f_i$ 表示考虑了前i台机器的最大收益

转移考虑枚举一个 $j<i$ , $f_j+g_j*(d_i-d_j-1)+l_j-p_j$ ,钦定我买了

但是这还不够,我们可以不买i啊,所以是 $max(f_i-1,.......)$

注意有限制 $f_j>=p_j$

紧接着我们可以发现这个式子很斜率优化,但是斜率是 $d_i$ (单调)而 $g_j$ 是横坐标不单调坏了

也就是说,我们凸包的形态动态变化

可以考虑cdq分治维护凸包,计算左边对于右边的贡献

先递归左边把左边的凸包建出来,然后右边的直线因为有斜率单调所以直接跑就好,在凸包上过一遍,挨个计算出一轮dp值

紧接着再递归右边即可

那个取max在最底层实现即可qwq

P4602混合果汁

对于一个询问,我们可以考虑二分一个答案然后直接判断是否合法

假如二分的值是mid我们把大于mid的美味度的果汁都加入序列中,然后排序,按照代价从小到大的选择如果能选满就再调大mid

这个是可以加速的,使用值域线段树,等价于二分出第一个前缀和大于我需要的果汁汁数的位置,然后暴力选上他们计算代价是否足够即可

但是如果整体二分的话,我们这样做会导致没法向两边递归,因为向右边的递归要全重新建树而不能够把之前的询问影响消除掉

所以直接考虑使用分治决策单调性的技巧,用一个指针 $[l,r]$ 表示我现在储存了美味度在 $[l,r]$ 区间的果汁,暴力移动端点以满足整体二分当前区间的性质即可

时间复杂度 $O(nlogvlogn)$

zhqwq 负责内容:

二项式反演

f_i=\sum_{j=m}^i\binom{i}{j}g(j)

g_n=\sum_{i=m}^n\binom{n}{i}f(i)(-1)^{n-i}

证明,把g带入f

f_i=\sum_{i=0}^n\binom{n}{i}\sum_{j=0}^i(-1)^{i-j}\binom{i}{j}f_j

\binom{n}{i}\binom{i}{j}=\binom{n}{j}\binom{n-j}{i-j}

f_i=\sum_{j=0}^n\binom{n}{j}f_j\sum_{i=j}^n(-1)^{i-j}\binom{n-j}{i-j}

f_i=\sum_{j=0}^n\binom{n}{j}f_j\sum_{i=0}^{n-j}(-1)^{i}\binom{n-j}{i}

二项式定理,后面没了

f_i=\sum_{j=0}^n\binom{n}{j}f_j *0^{n-j}

有0^0=1,也就是说只有j=n的时候有意义/kk

此时 $m$ 是上界!

实际上我们的组合意义是

f(3)代表了:(至多)

${1}{2}{3}{12}{23}{13}{123}$

而g的定义就是恰好i个条件符合的方案数

那么我们会发现 ${12}{23}{13}$ 都会被算一次

也就是说我们有 $\binom{2}{3}$ 次算g(2)的方案数!

至少和恰好

f(i)=\sum_{j=i}^m\binom{m}{j}g_j

g(n)=\sum_{j=n}^m\binom{j}{n}f_j*(-1)^{j-n}

你会发现这个是算超集

eg $S={12}$

${12}{123}{124}{1234}$

也就是说我们这个f会使得 ${123}$ 被算三次,可以重复算

因为满足条件的两个的集合有 ${12}{23}{13}$

注意!

这里至多是所有元素本质相同,我们{123}{234}方案数一样!!

而恰好对应了所有的方案数的和!!!就是{123}+{234}+{124}...的方案数总和!!!

错排

恰好n个不在原位置上

至多反演

$f_n=x!$

至多n个不同

至少x个反演

转换为其他的

$f_n=\binom{n}{x}(n-x)!$

${1,2,3}$

c=0的case,我们选出了一个空集

c=1,我们选出了 ${1}{2}{3},3g(1)$

c=2同理, $3g(2)$

至少/恰好

${1,2,3,4}$

我们考虑带标号容斥

$123,124,134,234$

12,13,23 算3次

12,24,14 算3次....

所以对于每个三元组会加上 $\binom{3}{2}$

整个加起来,然后发现每个g都会贡献一个带组合数系数的总方案数qwq

快讲题!

BZOJ3622

$dp_{i,j}$ 表示至少j个A中的元素和B配对成功了,然后考虑了前i个A的数字

排序后,我们考虑i是否和小于i的匹配,如果匹配,成功的个数+1,否则我们这个i就放任自由,因为我们是dp至少的方案数,这个恰不恰好都一样

$dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}*(cnt(i)-j-1)$

剩下 $dp_{n,m}$ 其他n-m个自由匹配的方案数是 $(n-m)!$

其他的也一样,然后使用至少的二项式反演就有了

p6076

高阶二项式反演

考虑变成至多才好做, $f(x,y,z)$ 表示恰好x行y列用了z个颜色方案数

f(x,y,z)=\sum_{i=x}^m\sum_{j=y}^m\sum_{k=z}^c(-1)^{i+j+k-x-y-z}C(x,i)C(y,j)C(z,k)g(i,j,k)

这个式子是钦点和至少是 $i,j,k$ 没用的...如果要写至多的式子应该是

f(x,y,z)=\sum_{i=0}^x\sum_{j=0}^y\sum_{k=0}^z(-1)^{x-i+y-j+z-k}C(i,x)C(j,y)C(k,z)g(i,j,k)

于是我们 $f(x,y,z)$ 就是答案

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int P = 1e9 + 7;
const int MAXN = 405;
ll c[MAXN][MAXN];
int n, m, K;
//最多多少答案f_i
//\sum_{i=0}^n\sum_{j=0}^m\sum_{k=0}^K(-1)^{i+j+k}C_{n,i}C_{m,j}C_{K,k}(c-k+1)^(n-i)(m-j)
inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}
inline void init() {
	int N = 400;
	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]) % P;
		}
	}
	return ;
}

inline void add(ll &x, ll y) {
	x += y;
	if(x >= P)x -= P;
}

inline void sub(ll &x, ll y) {
	x -= y;
	if(x < 0)x += P;
}

inline void solve() {
	ll ans = 0;
	for(int i = 0; i <= n; ++i) {
		for(int j = 0; j <= m; ++j) {
			for(int k = 0; k <= K; ++k) {
				if((i + j + k) & 1)sub(ans, c[n][i]*c[m][j] % P * c[K][k] % P * ksm(K - k + 1, (n - i) * (m - j)) % P);
				else add(ans, c[n][i]*c[m][j] % P * c[K][k] % P * ksm(K - k + 1, (n - i) * (m - j)) % P);
			}
		}
	}
	printf("%lld\n", ans);
	return ;
}

int main() {
	scanf("%d%d%d", &n, &m, &K);
	init();
	solve();
	return 0;
}

p5505

恰好n个人有物品->至多n个人有物品

(也可以直接钦定n个人没有物品)

所以我们讲至少k个人没有物品,即n-k可能有或没有物品

现在枚举下科目然后插板法就行了!

比如钦点t个人然后插板法一下

$f(t)=\binom{n}{t}\prod_{i}^m\binom{a_i+n-t-1}{n-t-1}$

zhq的DP做法

考虑 $f_{i,,j}$ 表示前i个人已经至少有物品了,考虑了前j个科目的方案数

然后我们可以考虑转移系数:枚举一下有多少个人从无到有,然后有多少个物品分给已有的人

然后这个是 $n^4$

变换组合意义,我们想枚举前k个人有1个,然后剩下使用可以为空的方案

实际写的时候注意用脑袋思考一下反演系数,应该是容出恰好0的方案数,那么我们应该乘上选0个的方案数,就是1

//你谷真是数理知识基础雄厚
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 3e3 + 7;
const int P = 1e9 + 7;
int n, m, a[MAXN];
ll C[MAXN][MAXN];

inline void add(ll &x, ll y) {
	x += y;
	if(x >= P)x -= P;
}

inline void sub(ll &x, ll y) {
	x -= y;
	if(x < 0)x += P;
}

inline void init() {
	int N = 2e3;
	C[0][0] = 1;
	for(int i = 1; i <= N; ++i) {
		C[i][0] = 1;
		for(int j = 1; j <= i; ++j) {
			add(C[i][j], C[i - 1][j]);
			add(C[i][j], C[i - 1][j - 1]);
		}
	}
	return;
}

inline ll calc(ll t) {
	if(n == t)return 0;
	ll ret = C[n][t];
	// printf("%d %d %lld\n", t, n, ret);
	for(int i = 1; i <= m; ++i) {
		ret = ret * C[a[i] + n - t - 1][n - t - 1] % P;
	}
	// printf("?? : %lld %lld\n", t, ret);
	return ret;
}


inline void solve() {
	ll ans = 0;
	// printf("%lld\n", calc(1));
	for(int i = 0; i <= n; ++i) {
		if(i & 1)sub(ans, calc(i) % P);
		else add(ans, calc(i) % P);
	}
	printf("%lld\n", ans);
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++i) {
		scanf("%d", &a[i]);
	}
	init();
	solve();
	return 0;
}

MinMax容斥

max(S)=\sum_{T \in S}(-1)^{|T|-1}min(T)

相当于用以排名至少为前x的数容斥

$K-MinMax$ 容斥

kMax(S)==\sum_{T \in S,|T|>k}(-1)^{T-k}\binom{T-1}{k-1}Min(T)

第x小的元素会在大小为T的集合中产生贡献

$f(|T|+1)\binom{n-x}{|T|}$

$\sum_{|T|=0}^{n-x}f(|T|+1)\binom{n-x}{|T|}$

$[x==k-1]=\sum_{|T|=0}^xf(|T|+1)\binom{x}{|T|}$ 这一步是根据按理说右边应该只有x在k-1的时候贡献一次

$[x==k-1]=\sum_{|T|=0}^xf'(|T|)\binom{x}{|T|}$ 然后考虑我们二项式反演这个式子

$f'(|T|)=(-1)^{T-k+1}\binom{|T|}{k-1}$

然后 $f(|T|)=(-1)^{T-k}\binom{T-1}{k-1}$

带回去就有了

hdu????4336??

膜板题qwq直接套用期望的线性性即可qwq

BZOJ4036

相当于每一位出现的时间最大值

$Max(T)$ 表示T位数集合出现的最后时间是什么

然后考虑求 $Min(T)$

你会发现相当于T某一位为1的超集的所有数的概率和

所以我们要求 $f_T$ 表示T的超集的概率和

不好算,考虑变成和T交集为空的方案,相当于凑齐V的补集的形式

这个可以高维前缀和,把V的子集和求出来,然后角一下就好了

P4707重返现世

容斥dp

你观察一下发现容斥的 $minT$ 之和只有两个变量就是 $\sum_P$ 和T

所以把概率大小和选的多少计入状态就有一个 $O(n^2m)$ 的不优秀做法

但是我们就算求出来也不能够...所以考虑把容斥系数也搞进

$h_{i,j,k,q}$ 就是把第k大这个放进去

怎么求转移呢?

根据反演的式子

$h_{i,j,k,q}=(-1)^{j-k}\binom{j-1}{k-1}f_{i,j,q}$

我们把f和组合数拆开

$h_{i,j,k,q}=(-1)^{j-k}\binom{j-1}{k-1}(f_{i-1,j,q}+f_{i-1,j-1,q-p[i]})$

左边就是 $h_{i-1,j,k,q}$

右边完蛋了,我们拆开组合数吧

$\binom{j-1}{k-1}=\binom{j-2}{k-1}+\binom{j-2}{k-2}$

然后还有一个-1系数不对,我们稍稍配凑一下

(-1)^{j-1-k}*\binom{j-2}{k-1}*f'+(-1)^{j-1-(k-1)}\binom{j-2}{k-2}*f'

其中f'是对应的那个系数

然后你观察一下就是

h_{i,j,k,q}=h_{i-1,j,k,q}-h_{i-1,j-1,k,q-p_i}+h_{i-1,j-1,k-1,q-p_i}

然后j这个维度在摸鱼,我们对于j求和,因为和式里面好像也是对于他求和

然后自闭了,这个对k求和是假的,因为你要求的是恰好k的方案数qaq

$g_{i,k,q}=g_{i-1,k,q}-g_{i-1,k,q-p_i}+g_{i-1,k-1,q-p_i}$

这样所有的 $g_{i,0,q}=0$ 边界甚至是-1....

猎人杀

考虑容斥,我们设1之后死掉至少包含点集S的所有人概率 $PS$

考虑这个局面怎么妙的转移,我们钦点打中尸体就再打一枪

有 $p(S)=\frac{a_1}{tot}+\frac{S}{tot}+\frac{tot-a_1-S}{tot}p(S)$

这个移项可得

$p(S)=\frac{S}{a_1+S}$

然后发现我们可以把S写进去

我们要求一个西格玛的等于一个值的系数,这个可以:

\prod_{i}^n(1-w^i)

然后考虑分治FFT就没了,答案就是对应项的系数

百鸽笼

你会发现首先容斥

然后 $\frac{1}{|S|+1}$ 就是1在他们之前出现的概率

怎么算这个概率啊

考虑1结束时S都不结束,把S内柱子的血量都-1

我们考虑按照顺序记录当前长度处理相对顺序的需要,所以就是要乘上一个可重组合数

就是说内部是什么物品不知道,所以我们要在内部放入一些元素,他们相对顺序是组合数出来的qwq

这个之和剩下的空位数有关qwq,所以我们可以对着这个 $12345121313452$ 放物品序列来做

最后推出来是 $n^6$ 我们考虑加速背包的过程

也就是说删除一个元素的影响后的背包

只需要从小到大减过去就好了

相当于一车01背包卷起来,我们除掉其中一个单项式,然后减掉即可

不妨直接抄zhq的博客,zhq的博客讲的特别的好,在友链里面有呢

wyz负责内容:

$n^3$ 的高复杂度

相邻不同色计数DP

P4448

球球的排列

相邻不能是平方数的排列方案数

$xy$ 是平方数, $xz$ 是平方数

$x^2yz$ 总是平方数,那么 $yz$ 也是一个平方数

所以所有不能相邻的数是一张完全图

所以这些点是一个颜色,那么其他点就是另一个颜色

所以就是相邻不同色方案数计数qwq

ljh的转换:

我们对于质因子的指数对2取模,等价于两个相等的数不能放在一起

然后都转换为同色不相邻,考虑n色球怎么做呢

$dp_{i,j,k}$ 表示前i个球有j个颜色相同相邻位置,以及第i种颜色分了k段

转移,去掉第三维,看上去只需要考虑插入多少个相邻位置,以及选择分成多少段qaq

枚举一下我们插入多少个j,就是相邻同色位置

考虑插板法

n个苹果k个华清我们要分,每个华清都要有个苹果

华清和华清之间本质不同,所以我们答案就是 $\binom{k-1}{n-1}$
每个华清可以双手空空也可以拿

我们钦定多出k-1个苹果,然后随意分配,最后每个华清没收一个苹果

$\binom{k-1}{n-k+1}$
ABA,BAB,ABAB我们要把他们分配成某些段,然后保证每一段只能是ABA,BAB,ABAB qwq

一个细节,知道了ABA,BAB就知道ABAB的数量了,因为我们知道A,B数量->A-B-x+y就是应该的数量

第一种最少有一个A,第三种最少一个A,如果我们知道了第一段的A的数量和第三段A的数量就能知道每一段的形态了!

$zhq$ 又切了!!!

考虑我们先强行钦定每个case2都要选上一个A

那么就是乘上 $\binom{a+y-1}{m-1}$ 然后我们就有剩下可重组合,并且有 $2^z$ 的方案数qwq出

$\frac{P^m_m}{P^x_xP^y_yP^z_z}\binom{a+y-1}{m-1}2^z$

然后球球问题

我们最后把一个颜色给叉成k段,然后前l个人给前面的,然后 $sum-l+1$ 段拿后面的即可qwq

zhq又切了

购物问题,选出一些数凑齐某个面值的方案数

考虑我们dp一下完全背包,然后求出每个容量(不限制每种选数多少的任意选取的)方案数

然后钦定其中一个集合S的选择数量超过目标,然后剩下的乘上我们完全背包的方案数就好了

复杂度就是 $O(n*16+S)$

#include<bits/stdc++.h>
#define ll long long
const int MAXN = 2e5 + 7;
using namespace std;
int c[10], d[10], n, s;
ll dp[MAXN];
inline void add(ll &x, ll y) {
	x += y;
}
inline void init() {
	int N = 1e5;
	dp[0] = 1;
	for(int i = 1; i <= 4; ++i) {
		for(int j = 1; j <= N; ++j) {
			if(j - c[i] >= 0) {
				add(dp[j], dp[j - c[i]]);
			}
		}
	}
	// for(int i = 1; i <= N; ++i) {
	// 	printf("%d %d \n", i, dp[i]);
	// }
	return ;
}

int main() {
	scanf("%d%d%d%d%d", &c[1], &c[2], &c[3], &c[4], &n);
	init();
	for(int i = 1; i <= n; ++i) {
		scanf("%d%d%d%d%d", &d[1], &d[2], &d[3], &d[4], &s);
		ll ans = 0;
		int mS = (1 << 4) - 1;
		for(int S = 0; S <= mS; ++S) {
			int q = s, g = 1;
			for(int k = 0; k < 4; ++k)
				if(S >> k & 1) {
					g *= -1;
					q -= (d[k + 1] + 1) * c[k + 1];
				}
			if(q < 0)continue;
			add(ans, dp[q]*g);
		}
		printf("%lld\n", ans);
	}
	return 0;
}

\text{酮与氰化氢加成：}\ce{\chemfig{CH_3C(=[1]O)(-[7]CH_3)} + \chemfig{CN(-[2]H)} ->T[催化剂] \chemfig{CH_3(-[0]C(-[2]OH)(-[0]CN)(-[6]CH3))}}

夏晓光(loveJY)的博客

ytez省队集训讲课篇一轮

P4463 [集训队互测2012] calc

P3270 [JLOI2016]成绩比较

P4593 [TJOI2018]教科书般的亵渎

注意!

快讲题!

P4707重返现世

艾丝·华伦斯坦的生成函数入门篇