HDU3507

$(\sum_{i=1}^{n}C_i)^2+M$

$f_i=\min f_j+(sum_i-sum_j)^2+M$

$f_i=\min f_j+sum_i^2+sum_j^2-2*sum_i*sum_j+M$

$f_i-M-sum_i^2+2sum_isum_j=f_j+sum_j^2$

x坐标是 $sum_j$ ,斜率是 $2sum_i$ ,b是 $f_i-M-sum_i^2$ ,y是 $f_j+sum_j^2$

最小化,维护下凸壳,找到i,i+1斜率大于他的第一个点,i就是答案

并且从最后向前弹的时候,找到第一个斜率小于最后一个点的倒数第二个点,然后加入即可

$f_i=\max f_j+a(sum_i-sum_j)^2+b(sum_i-sum_j)+c$

$f_i=f_j+asum_i^2-2asum_isum_j+asum_J^2+bsum_i-bsum_j+c$

$f_i-bsum_i-c-asum_i^2+2asum_isum_j=f_j+asum_j^2-bsum_j$

x是 $sum_j$ ,k是 $2asum_i$

P1721国王饮水记

小于他的不用考虑
先合并这个小的再合并大的更优
一定从高到底合并

只考虑一段,去掉第二维枚举使用次数k的过程

$f_i=\max \frac{f_j+s_j-s_i}{j-i+1}$

$f_i=\max \frac{s_j-(s_k-f_k)}{j-(k-1)}$

显然是一个点到另一个点的斜率最大值,此时你会发现 $(j,s_j)$ (定点)

一定在凸包外,所以一定是相切最大,而且单调向右切qwq

P4027

$f_i=\max f_{i-1},A_ix_j+B_iy_j$

其中x,y是把第j天全兑换了的最大代价

$A_ix_j+B_iy_j=f_i$

$\frac{f_i}{b_i}-\frac{A_i}{B_i}x_j=y_j$

你会横坐标和斜率都不单增,要平衡树维护凸包吗亲?

不的不的我们直接cdq分治!!

归并排序!

(满足条件||右越界) && 左不越界

放左边

else 放右边

我们用1个log可以保证三个下个条件都满足!!

首先所有的点都按照k排序

然后我们考虑左边的所有点,把横坐标小于等于mid的分到左边,大于mid的分到右边

然后我们返回的时候把区间内的点按照x坐标排序

这样solve(l,mid)拿到的区间就是单调的x轴排序的结果

然后再建立凸包,此时右区间满足横坐标大于他而且斜率都是单调的!

然后再在上面做一遍即可

P3571

简直无情

我也不知道为什么观察可以知道最优方案一定是满足在前i层使用i次完成,然后在第i+1到之后的层数每次使用k次

证明很显然,前x层不可能少于x步结束,而后面的节点每次删除k个次数显然是最少的....

然后给出答案,对于每次能选上i的,我们 $f_i$ 答案有 $f_i=\max {j+\lceil\frac{s_j}{i}\rceil}$

我们不妨证明:如果k>j,并且在前k层不能有k次完成,而前j层可以用j次完成,那么我们一定有

$k-j<\lceil\frac{s_k-s_j}{i}\rceil$

注意到右边可以是实数意义,所以我们直接给予其实数意义去掉上取整

$ij+s_j>ik+s_k$

再观察原式,显然可以等于

$f_i=max \lceil\frac{ij+s_j}{j}\rceil$

加上上取整符号后显然不可能超过j,所以就有j的答案更小

另一个 $k<j$ 是一样的

那么对于这个式子斜率优化即可,时间复杂度 $O(n+q)$

#include<bits/stdc++.h>
#define db double
using namespace std;
const int MAXN = 2e6 + 7;
int n, q, ccnt, f[MAXN], k[MAXN], md;
int home[MAXN], nxt[MAXN], to[MAXN], que[MAXN];
inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
}
int dep[MAXN], s[MAXN];
inline void dfs(int u) {
	s[dep[u] - 1]++;
	md = max(dep[u] - 1, md);
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		dep[v] = dep[u] + 1;
		dfs(v);
	}
	return;
}
inline db getslope(int x, int y) {
	return (s[x] - s[y]) / (db)(x - y);
}
int main() {
	scanf("%d", &n);
	scanf("%d", &q);
	for(int i = 1; i <= q; ++i)scanf("%d", &k[i]), k[i] = min(k[i], n);
	for(int i = 2; i <= n; ++i) {
		scanf("%d", &f[i]);
		ct(f[i], i);
	}
	dep[1] = 1;
	dfs(1);
	for(int i = md; i >= 1; --i)s[i] += s[i + 1];
	int hd = 1, tl = 0;
	for(int i = 1; i <= md; ++i) {
		while(hd < tl && getslope(que[tl], que[tl - 1]) < getslope(que[tl], i))tl--;
		que[++tl] = i;
	}
	for(int i = 1; i <= n; ++i) {
		while(hd < tl && getslope(que[hd], que[hd + 1]) > -i)++hd;
		f[i] = que[hd] + (s[que[hd]] + i - 1) / i;
	}
	for(int i = 1; i <= q; ++i)printf("%d ", f[k[i]]);
	return 0;
}

P2900

考虑按照长度排序,然后你会发现,宽度不同的可以直接删除!!!

就是如果 $y_i>y_j,y_j<y_{j+1}$ , $y_j$ 点可以直接删除

发现这个的东西是横坐标无论如何都是单调递减

那么我们可以把一个符号放进k中,然后让x单调递增

P6047

注意我们是从左向右切,才能切断一条线

那么我们有排除掉那些没有用的项,就是 $(i,j),(u,v)i>u,j<v$ 的(i,j)可删除

所以直接会变成一个1D的dp

$f_i$ 表示到第i个点?或者第i条弦?先考虑后面那种

设 $mina[x,y]$ 是 $[x,y]$ 区间最小值,所以 $f_i=f_j+mina[1,u_j-1]*minb[v_i+1,n]$

处理一个前缀a一个后缀b的最小值然后直接斜率优化即可

第二个,就是点的方式qaq

每个点最多割一刀
每个点u,设u前所有点向后连的点的第二维最大值为j,那么u的到一定在j之后切

$f_i=min(f_j+a_i*rmin[max_{i+1<=k<=j}mv_k+1])$

这个式子要想斜率优化,那能不能用前缀最大值代替区间最大值呢?

能!

因为如果我们某一刀不优秀,就是他没有在区间最大值之后割导致代价更大

那你会发现我们一定要有一刀把那个线段割掉,所以说之后直接做没有关系

那么就是说,这一刀一定不优秀,不会比之后选择哪个决策点的决策优秀!


#include<bits/stdc++.h>
#define db double
#define ll long long
using namespace std;
const int MAXN = 5e5 + 7;
int n, m, que[MAXN];
ll w1[MAXN], w2[MAXN], f[MAXN];
struct rec {
	int up, dw;
	bool operator<(const rec &x)const {
		return up == x.up ? dw > x.dw : up < x.up;
	}
} a[MAXN], b[MAXN];
inline db getslope(int x, int y) {
	if(w1[a[y + 1].up - 1] == w1[a[x + 1].up - 1])return 1e18;
	return (f[y] - f[x]) / (db)(- w1[a[y + 1].up - 1] + w1[a[x + 1].up - 1]);
}
int main() {
	// freopen("test.in", "r", stdin);
	// freopen("test1.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i)scanf("%lld", &w1[i]);
	for(int j = 1; j <= n; ++j)scanf("%lld", &w2[j]);
	for(int i = 1; i <= m; ++i)scanf("%d%d", &a[i].up, &a[i].dw);
	int mx = 0;
	sort(a + 1, a + n + 1);
	int tot = 0;
	for(int i = 1; i <= n; ++i) {
		if(a[i].dw <= mx)continue;
		mx = max(mx, a[i].dw);
		b[++tot] = a[i];
	}
	for(int i = 1; i <= tot; ++i)a[i] = b[i];
	// printf("%d %d\n", b[i].up, b[i].dw);
	for(int i = 2; i <= n; ++i) {
		w1[i] = min(w1[i - 1], w1[i]);
		// printf("%d ?\n", w1[i]);
	}
	for(int i = n - 1; i >= 1; --i) {
		w2[i] = min(w2[i + 1], w2[i]);
	}
	int hd = 1, tl = 1;
	for(int i = 1; i <= tot; ++i) {
		while(hd < tl && getslope(que[hd], que[hd + 1]) < w2[a[i].dw + 1])++hd;
		// printf("%d ", que[hd]);
		f[i] = f[que[hd]] + w1[a[que[hd] + 1].up - 1] * w2[a[i].dw + 1];
		// printf("%d\n", f[i]);

		while(hd < tl && getslope(que[tl], que[tl - 1]) > getslope(que[tl], i))--tl;
		que[++tl] = i;
	}
	printf("%lld\n", f[tot]);
	return 0;
}
/*
7 5
7 5 4 3 5 2 1
2 5 8 3 6 8 9

2 2
3 3
4 4
5 5
6 6

*/

注意斜率优化当横坐标相同维护下凸壳的时候返回1e18,维护上凸壳的时候返回-1e18,这个是大部分题的做法

uoj告诉我们要叉积判......这个建凸包的时候相当对啊,但是你乘过去还要看这个正负号烦死了吧??拿斜率去卡的时候没办法啊.....

P6302 [NOI2019] 回家路线加强版

每个点都直接构造一个凸包,再在路径上动态规划,然后再考虑消除限制

就是扫描时间轴依次加入,然后每次加入在一个点上的凸包,再在那个点更新一下所有点的答案qwq

P2305 [NOI2014] 购票

考虑暴力dp的式子

$f_u=\min f_v+(d_u-d_v)*p_v+q_v$

同时有一车限制: v is u ancestor

$d_u-d_v<=l_u$

解除第二个限制?

按照 $d_u-l_u$ 排序,这样我们一定可以按照深度递增加入决策点,并进行转移

但是怎么保证我们不用CDQ而直接转移呢?

点分治

区分子树,由于这个 $ancestor$ 可能会导致一些奇怪的结果,所以我们把 $u$ 到 $F_u$ 的那个子树单独提出来

即

优先处理这个红色的子树

于是我们先循环递归 $F->u$ 的这条链,然后再解决u的子树

u的子树所有点按照上述的限制排序

然后再去按照从u开始深度从小到大加入u->F的这条链

并且每次加入都用在凸壳上二分转移一下u的子树中的那些点即可

时间复杂度就是 $O(nlog^2n)$

点分治

把前面的子树都算出来,然后考虑合并子树新产生的贡献
把整个根代表的子树答案都算出来,然后再合并所有子树内部的贡献

还有齐神说的

找重心:相当于找到一个点做根的时候最大子树大小最小

那么就是所有子树和连通块-子树大小(另一个棵树)的最大值最小的值

P4149 [IOI2011]Race

板子题

P3714 [BJOI2017]树的难题

考虑维护两个数组的单调队列,按照相同颜色的顺序合并一下

我们按照深度挨个加入进行匹配,那么 $[l,r]$ 就对应在另一个数组的 $[l-dep,r-dep]$

同时不难发现,随着深度的递增这个能匹配的也会向前移动

因为如果颜色相同,我们的答案还会减去一点,所以要特判相同颜色的,而每次优先遍历合并所有相同颜色子树就能只开两个单调队列啦qwq

经过一点点讨论,这道题单调队列的复杂度是 $O(nlogn)$ ,但是这个复杂度分析是每次个分治重心使 $O(maxdep*子树个数)$ 而你会发现这个 $maxdep$ 不会很大!不会超过maxsiz,而既然西格玛siz都合法,这个也不可能不合法

P2664 树上游戏

还是算跨过分治中心的贡献

考虑每个颜色的贡献,对于跨过分治重心的路径

先把所有子树信息加入,然后再删除一个子树的,再算这个子树的答案qwq

如果某个颜色在这个点到根路径出现了,贡献就是 $Sizsum-sizu$

否则如果某个颜色的贡献就等价于其他点到根的路径这个颜色的贡献

这个怎么维护呢?考虑处理每个子树所有不为祖先父子关系的最浅的该颜色的那些点的子树 $siz$ 和

边分治

如果不三度化,我们复杂度就是度数*(度数-1)log

定理:可以有一条边他两侧的子树大小差不多是1:(maxdep-1)...

举例:菊花图

三度化:每次我们建立一个新点,然后把一个儿子挂上去这个新点,然后继续把这个新点连到父亲节点

写的时候只有一个儿子就不建新点,否则建立新点挂上去

数组要开至少4倍,边要开8倍!

ljh的思维题

区间权值定义为两端最小值*区间长度

那么做法就是第一次选择[1,n],计算一下答案,设左边是a,右边是b

如果 $a<b$ 删掉a,然后递归[2,n],否则递归[1,n-1]就做完了qwq

树上链的权值为点最小权值*路径长度,问这个树的最大权值

首先有点分治做法,建立权值线段树进行合并即可qaq

然后注意我们可以从前到后扫一遍从后到前

然后还有一个序列上树的做法,就是权值从大到小加入,然后每次维护合并连通块后树的直径

注意到这个树形态不会改变,所以可以直接做哦,直接合并这个长度qwq??

虚点权值设置成0,其他点设置成1,然后按照最小值sort,双指针一下??/qaq因为此时我们只有两个数呢

复杂度也是两个log,要排序啊

P4220 [WC2018]通道

考虑两条链的做法,我们对于abs拆开,有2^4种情况,不难发现都维护然后取max即可,如果是错的那显然不会优(昨天的套路啦)

考虑两颗树的做法,我们有暴力写挂那道题的借鉴,可以考虑第一棵树边分治,然后第二棵树直接建立虚树,把第一棵树的到根的dis赋值为权值,并且把边左边的子树变为白色,右边的子树变为黑色,就等价于一个 $dis(x,y)+a_x+a_y$ 的问题,可以直接点分治

考虑三棵树的做法,此时我们直接嵌套下去是显然不行的,不仅4种颜色,而且复杂度是3log的

我们考虑还是边分治第一个树,然后拿第二个树建立虚树,然后考虑在第二棵树上dp

枚举LCA后,相当于每个子树维护子树内在第三棵树上的黑色点集的直径,白色点集的直径,然后合并点集的时候求出这些黑白点的交错点的直径,并加上第二棵子树的信息更新答案

CF1400

$F_{i,S}$ 表示到了第i位,i向左的后缀和有S这些值的最少步数

考虑是否合法,如果加入这个i,相当于所有后缀S右移一个值,并截断全x位,如果此时出现了x,那么相当于成为了一次区间,那么就要判断前面的点是不是合法的qwq

然后再考虑这样会T,因为我们不合法状态很少,只有对于S集合上,两个相邻的位置有数就会不合法

eg:10 1 9,那么9和10会连续出现,就是不合法的

相当于我们要 $f_i=f_{i-2}+f_{i-3}....$ 这个f的第20项就是斐波那契数的某一项,只有三千都

预处理这些不合法状态,建立AC自动机,问题等价于不能走到AC自动机的一个终止节点qwq

动态点分治

x修改时,从x不断跳点分树父亲一直到根,每次经过的节点S2修改他的贡献,然后每个点维护数据结构维护贡献即可qwq

震波

带修查询小于一个点距离为k的权值和

对于一个点u,考虑向上爬,到某个点分树父亲距离为d,然后在这个点查询距离k-d的所有点的权值和

再在这一级分治重心的线段树中减去深度为 $k-d-e$ 的权值和,这个e是上一级分治重心到这一级分治中心的子树的那条边的距离

幻想乡战略游戏

从根向下跳,查询每个点的 $a_i$ 和,维护最大的那个重儿子向下跳即可

修改暴力向上跳即可

P3676 小清新数据结构题

先处理1为根的答案,然后u为根相当于

$ans_u=ans_1+(k-1)*a_0^2-2a_0\sum_{i=0}^ka_i$

链的权值和,然后树剖直接做即可

没棵子树权值和的平方和,相当于第一次选一个点x,第二次选一个点y,贡献为 $a_x*a_y*dep[LCA(x,y)]$

把这个式子展开来有

\sum_{x}\sum_{y}a_xa_y(dep_x+dep_y-dep_{LCA})

\frac{1}{2}(2(\sum_{x}a_xdep_x)(\sum_x a_x)-\sum_{x}\sum_{y}a_xa_ydis(x,y))

前面那个权值和直接维护

所以说右边那个动态点分治维护即可,相当于维护

$\sum_{i=1}^n a_i dis_{i,x}$

(其实我在口胡你)

你考虑一个点对怎么产生贡献,在两个点的路径上只有处于lca的时候不会被算一遍,其他的路径处都会被算一次

wyz负责内容

wyz线段树二分

考虑我们向左找还是向右找,对应了两个方向递归下去qwq

不光开 $l,r,k$ 再开 $spr$ 区间的前缀值,就是向右区间走的时候的一个前缀附加信息,同样如果需要还要开一个后缀的附加信息来帮助判断二分的!

ZROI省选一轮T3

如果我们要在线段树二分的时候查询一个区间内的信息的时候,我们可以不从 $1,n,pos$ 从 $l,r,pos$ 直接开始查就好了,就是从这个区间直接开始查qwq

这样可以做到除以2的常数qwq

链表优化DP/se

命运

如果我们填了1,所有限制都会消除

$dp_{i,j}$ 表示考虑了i子树,然后受第j个限制限制最为严重,即深度最大限制为j这个限制

然后可以变成到j级祖先或者深度为j的qwq

这样做是48分,转移瞎考虑一下即可!

一个n个节点的二叉树,深度就是logn的

如果我们从下到上按深度考虑,你会发现每一个限制绝对不会重复的,即每一层只有一个节点出现一个限制

那么每个限制在每一层只会被算一遍!

你会发现这样有大量冗余状态,可以只达到m*层数的记录

然后我们考虑怎么转移,合并限制

把所有儿子的状态枚举一遍,然后合并,用链表实现就是 $O1$ 的

你会发现转移好像要钦点一个儿子达到某一个限制,如果我们直接做就 $2^n$ 了

但是这样你会发现可以直接容斥dp一个一个并入u中,只考虑u,v两个子树,就只需要钦定哪个达到足够深度

这个也太毒瘤了吧😢

因为相当于套了一层容斥dp转移啊qaq

CF609F Frogs and mosquitoes

set做法:

考虑有些青蛙永远吃不到,删除这样的青蛙,我们所有区间互不相交

那么你会发现每个蚊子被吃到范围内最靠左的就是upperbound的第一个右端点对应的青蛙

[()])因为都是这样的形态所以可以

max做法:

把青蛙按照左端点排序,离散化维护线段树,然后考虑线段树二分

记录一个区间的maxR,然后尽可能二分向左边的青蛙qwq

然后改变的时候单调修改,并且用set维护所有的青蛙即可qwq

min做法:

考虑每个右端点插入左端点,那么一个蚊子就会被一个后缀最小值查询qwq

然后蚊子就直接用同样的set维护,或者用一个线段树维护,有点毒瘤啊

P2595 [ZJOI2009]多米诺骨牌

如果没有行列必须连起来的性质我们可以直接头插DP,但是我们有

然后发现我们要给每一个行每一个列进行容斥

考虑一个子矩阵,他们的方案数该怎么办呢?

暴力dp qwq $2^n*n^4$

dp的时候你会发现我们一定有一个时刻是记录了一行的整个状态,就是说我们类似于扫描过第三维即可....

就是说固定L,R单调后移,就能确定所有R的答案,暴力没必要把区间都枚举一遍,顺便扫过去即可!

也就是说我们枚举的 $x_2$ 不用算了,我们只需要知道从 $y_1~y_2$ 这两行夹出来的一列的信息

然后考虑容斥这个间隙有无覆盖,这些间隙切割开整个矩阵,就变成了好几个小矩形乘起来的方案

这样还是不行,因为这样还是 $O(2^{n+m})$ 直接考虑,所以我们要把系数写进dp方程再容斥dp一下

CF1327F

$dp_{i,j}$ 表示前i个数,然后最近的一个0在位置j

假如我们已经预处理出了每个点最近的限制位置p

那么你会发现转移时,如果我们放0, $dp_{i,i}$ 的值就是前面所有数的和

否则我们放1,全局其他位置不发生改变,并且将p之前的全部减为0

会发现这个位置单调前移,所以用一个双指针维护dp数组即可!

P1399 [NOI2013] 快餐店

基环树直径

定义为所有两点最长值的最短值

先把环提出来,每个点的子树求出来,求出树内直径,这些直径取max,然后考虑每个子树传一个最大深度上去,看看怎样拼起来

考虑环,先随便一个pos断开

$B_i$ 表示1~i的前缀两颗子树自己拼起来的最大直径

$C_i$ 表示i~n后缀两颗子树自己拼起来的最大直径

这两个都很好处理

$A_i$ 表示在前缀选一颗子树+这个点到开头的距离和的最大值

$D_i$ 表示在i~n后缀选一颗子树+这个点到结尾的距离和的最大值

那么显然有位置i断开的答案是 $max(B_i,C_{i},A_i+D_{i+1}+w)$

那么所有断开位置取max就是答案啦~

时间复杂度 $O(n)$

P3239 [HNOI2015]亚瑟王

$f_{i,j}$ 表示所有的r轮中,前i张牌一共打出j张的概率

那么我们考虑前i-1张牌选了j张牌,有j轮不会考虑到第i张牌,而有r-j轮都有第i张牌

我们想算第i张牌在所有的r轮中打出去的概率

$1-(1-p_i)^{r-j}$ 就是在第 $r-j$ 轮使用第i张牌的概率qaq

转移考虑这一张牌能不能选择,如果选择,就是 $f_{i-1,j-1}*(1-p_i^{r-j+1})$

否则就是 $f_{i-1,j}*p_i^{r-j}$ ,一轮都不选择我呢!

然后用期望的线性性把每个牌的贡献加一下就好了

P3750 [六省联考2017]分手是祝愿

一个点修改是不会被其他点表示出来的,也就是说必须再来一次

那么所有点对应关键点和垃圾点两种状态

考虑 $f_i=\frac{i}{n}f_{i-1}+\frac{n-i}{n}f_{i+1}$

然后就可以直接转移,系数矩阵高斯消元

还可以设出差分数组,然后直接转移

P5516 [MtOI2019]小铃的烦恼

怎么做呢?钦定哪个颜色是最终状态?

钦定i为最终状态,那么你会发现我们要求出i的成为最终颜色概率 $\frac{num_i}{n}$

$p_i$ 表示i个数的颜色成为最终颜色的概率, $P_0$ =0, $p_i=0.5*(p_{i-1}+p_{i+1})$

然后你发现 $p_0=0,p_n=1$

于是我们考虑怎么设状态转移, $f_i$ 表示i个颜色的期望步数

$f_i=\frac{2i*(i-1)}{n*(n-i)}+\frac{2i}{i+1}f_{i+1}+\frac{2i}{i-1}f_{i-1}$

其中??是走到自己导致的步数

同时你会发现 $f_{i-1}$ 有坑,因为 $f_0$ 是不可能的,0个颜色不可能转移过去

所以要特判边界qwq稀疏矩阵高斯消元

所以我们可以套那个 $p_i/p_{i-1}$ ,推出 $f_{i-1}$

P7245 灯光效果

考虑枚举一个小矩形的期望贡献,显然我们只有n^2个不同的矩形,设P为操作一次改变它的概率

\sum_{i=1}^NP^i*(1-P)^{K-i}\binom{K}{i}[i \% 2==0]

wyz:你会发现我们可以把奇偶性变成0.5直接做呢!

$0=0.5+0.5*(-1)^{i+1}$

$1=0.5+0.5*(-1)^{i+1}$

你会发现还真是这样

因此每个都拆开然后我们有

\sum_{i=1}^NP^i*(1-P)^{K-i}\binom{K}{i}(0.5+0.5(-1)^{i+1})

然后我们二项式展开前面这个

当然你也可以发现我们可以使用生成函数技巧: $\frac{(P+(1-P))^k-(-P+(1-P))^k}{2}$

就做完了复杂度 $O(n^2logK)$

P6620 [省选联考 2020 A 卷] 组合数问题

$x^k=\sum_{i=0}^k\binom{x}{i}S_{k}^ii!$ 把这个式子二项式反演

$S_{k}^i=\frac{1}{m!}\sum_{k=0}^m(-1)^k\binom{m}{k}(m-k)^n$

都有组合意义,相当于k个球x个盒子然后放球的方案数,然后二项式反演得到这个S的方案数qaq

下面都是下降幂

$f(k)=\sum_{i=0}^ma_ik^i$

$=\sum_{i=0}^ma_i\sum_{j=0}^iS_{i,j}k^{j}$

$=\sum_{i=0}^mk^{i}\sum_{j=i}^mS_{j,i}a_{j}$

显然后面可以预处理了

然后考虑Ans,ix表示下降幂

$ans=\sum_{k=0}^n\sum_{i=0}^kb_ik^{ix}x^k\binom{n}{k}$

先交换,再裂项凑组合数

$\sum_{i=0}^mb_i\sum_{k=0}^n\frac{k!}{(k-i)!}x^k\frac{n!}{(n-k)!k!}$

$\sum_{i=0}^mb_i\frac{n!}{(n-i)!}\sum_{k=0}^m\frac{(n-i)!}{(k-i)!(n-k)!}x^k$

$\sum_{i=0}^mb_i\frac{n!}{(n-i)!}\sum_{k=0}^n\binom{n-i}{k-i}x^k$

k=k-i,x^k

$\sum_{i=0}^mb_i\frac{n!}{(n-i)!}x^i(x+1)^{n-i}$

$b_i$ n^2预处理了就做完了

P5405 [CTS2019]氪金手游

题目要求我们每一个都满足树形结构的DAG

考虑容斥,钦定为根后拉成外向树好解决,对于那些反向边,我们容掉他们

如果这条边为正向,概率很好算,相当于整个子树要比他的父亲满,是 $\frac{p_i}{siz[u]}$

否则相当于这条边正向反向一样,我们有直接断掉这条边方案相乘即可

然后考虑那个分布怎么办?

你发现我们dp出来的相当于子树中所有正向边能走到的点的点权和

那么有u一定在他们之前,所以直接乘上u选择这个权值的概率即可

注意我们要树形背包,因此不能写成 $n^3$

P3317 [SDOI2014]重建

这个题也挺毒瘤的qwq

dp?显然是不行的,每个点本质不同,之前我们整数划分记录连通块是可行的qwq

你发现答案相当于 $\prod_{e\not\in S} (1-p) \prod_{e \in S} p$

再变形 $\prod_{e\in E} (1-p) \prod_{e \in S} \frac{p}{(1-p)}$

直接矩阵树即可qaq

Cards

推式子即可qaq

枚举使用次数,然后二项式反演化简得到

\sum_{i=1}^kS_{k,i}\binom{n}{i}(\frac{1}{m})^i

要做到O(n),可以推出系数的一个递推关系,然后O(n)推出每一项系数

CF961G Partitions

直接抄讲义qwq

夏晓光(loveJY)的博客

ytez省队集训讲课篇二轮