qbxt省选数学考试

考场唯一切掉的

对于一个位置i胜利的方案数?

考虑前面的(i/2)个随便选择,后面的dp即可

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 1e9 + 7;
const int MAXN = 1e6 + 7;
int n;
ll f[MAXN];
ll f2[MAXN], sum[MAXN];

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

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

int main() {
	scanf("%d", &n);
	init();
	f[n] = 1;
	sum[n] = 1;
	for(int i = n; i >= 1; --i) {
		add(f[i], (sum[i + 1] - sum[min(i * 2 - 1, n) + 1] + P) % P);
		sum[i] = sum[i + 1];
		add(sum[i], f[i]);
	}
	ll ans = 0;
	for(int i = 1; i <= n; ++i) {
		f[i] = f[i] * f2[i / 2 - 1] % P;
		add(ans, f[i] * f2[2] % P * i % P);
	}
	printf("%lld\n", ans);
	return 0;
}

从这个诡异的式子入手

max|\sum \frac{1}{2}(a_{p_i+1}-a_{p_i})\frac{b_{p_i+1}b_{p_i}}{a_{p_i+1}a_{p_i}}|

乘开

max|\sum \frac{1}{2}\frac{b_{p_i+1}b_{p_i}}{a_{p_i}}-\frac{b_{p_i+1}b_{p_i}}{a_{p_i+1}}|

观察发现我们要最大化 $\frac{b_{p_i+1}b_{p_i}}{a_{p_i}}-\frac{b_{p_i+1}b_{p_i}}{a_{p_i+1}}$

这个就是两个点(x,y)的叉积的形式,相当于最大化叉积形成的多边形面积

发现我们这个式子算的其实是凸包的三角剖分的每一段的面积

也就是说求凸包即可

最后一个点一定会在上面的原因也就可以知道了QAQ

如果只有一列,那么射杀的概率就是一个递推关系

然后观察一下就是 $1+p1+p1p2+p1p2p3+....+p1p2p3..pn$

那么对于一列内部,按照p排序是最优的

考虑两列之间怎么排序

加入第一列杀掉期望此时总期望 $e_i$ ,第j列是总期望 $e_j$

kill i表示第i列都杀光的概率,kill j表示第j列杀光的概率

假如i在j前面

于是我们有这一列没杀光的期望次数是 $(1-kill_i)*e_j+e_i$

直接排序即可

$f_{S,i}$ 表示s集合内的点组成了一条链,然后i是终点的方案

$g_{S,i}$ 表示s集合内的点组成了i条链的方案

怎么求g?

枚举一下 $S1∪S2=S$ 然后 $g_{S1,i-1}*f_{S2,k}$ ,枚举一个终点啊

既然可以状压dp....

那么我们是不是可以发现用了几条链就是几条边啊?

$h_{i,j}$ 表示前i个图,用原有的边,形成j条链的方案

$h_{i,j}=h_{i-1,k}*g_{2^n-1,j-k}$

相当于第i个图单独玩一下卷积一下而已

现在我们有任意不相交的链的方案了!

那么我们算哈密尔顿路就是连接这些链而已!

显然就是链的阶乘就是答案!

用这个dp就能求出 $h_{i,j}$ 并搞出答案qwq

显然g很好算

但是这个链太大了,i也太大了

但是h数组是可以倍增的!~~(矩阵乘法!)~~

发现这个东西就是卷积,多项式快速幂即可

夏晓光(loveJY)的博客

计数题经典技巧整理