序
开考前我看是$NOIP$模拟，结果考了好久都没下考，原来…
原来没有”$P$”…(晕)
结果
题目
题解
T1
原本两维息息相关，相当麻烦，容易想到转$45$度坐标，可以使得两维独立。
那么原本$x^ny^m$会变成$(\frac{x+y}{2})^n(\frac{x-y}{2})^m$。
可以用二项式展开真正使得两维独立，接下来需要解决的是求$E(a^k)$。
可以简单设一个dp。
用$F_{i,j}$表示$i$步后$E(a^j)$是多少，同样用二项式展开可以得到转移式。
把转移写成矩阵，可以使用矩阵乘法。
复杂度$O((n+m)^3\ log\ t)$。
计算$F_{i,j}$的过程可以不用矩阵乘法。
注意到转移过程中$j$减少的次数不超过$n$次，那么记$g_{i,j}$表示经过$i$次减少量至少为$1$的转移，总的变化是$j$的所有转移的系数乘积和。
对于减少量为$0$的转移，$F_{i,j}$会对$F_{i+1,j}$产生$2F_{i,j}$的贡献。
所以，最终的和就是$\sum \limits_{i=0}^n\binom t i \times \sum\limits_{j=0}^n g_{i,j}\times x^j\times 2^{t-i}$。
复杂度$O((n+m)^3)$。
T2
不妨让我们先换一种方式描述积和式。
一个边权二分图，一个完美匹配的贡献为匹配边边权的乘积。
求所有完美匹配贡献的和。
接下来我们认为矩阵上不为$1$的位置对应的就是一条关键边。
假设$S$是一个关键边集,任意两条属于边集的边没有相同的端点。
令$f(S)$表示有多少种完美匹配方案恰好只包含边集$S$，也就是不包含多余的关建边。
令$g(S)$表示有多少种完美匹配方案包含边集$S$，显然$g(S)=(n-|S|)!$。
定义$v(S)$表示边集$S$内所有边边权的乘积。$w_e$来表示边$e$的权值。
首先显然$g(S)=\sum_{S\subset T}f(T)$
则显然有$f(S)=\sum_{S\subset T}g(T)*(-1)^{|T|-|S|}$
我们再来写出答案的式子。
$\sum_{S}v(S)*f(S)$
$\sum_{S}v(S)\sum_{S\subset T}g(T)*(-1)^{|T|-|S|}$
$\sum_{T}g(T)\sum_{S\subset T}v(S)*(-1)^{|T|-|S|}$
整理一下式子可以发现答案的表达。
$\sum_{S}(n-|S|)!\prod_{e\in S}(w_e-1)$。
因此我们可以把所有边权减一，那么问题变成计算对于每个$k$，任选$k$条不相交的关键边边权乘积和是多少。
算法一
首先显然可以将联通块分开独立来做，最后再背包在一起。
假设一个联通块点数为$n$，边数为$m$，因为是二分图，其中一边一定有不超过$\frac{n}{2}$个点。
可以将小的一边状压，假设小的一边是Y部。
设$f_{i,s}$表示做到X部的第$i$个点，目前对于一端在X部的前$i$个点的关键边，我们选择了一些，它们没有相同的另一端并覆盖了$s$这个状态，边权积的和是多少。
转移只需要枚举当前点的一条边即可。
复杂度为$O(m*2^{\frac{n}{2}})$，
即$O(n^2*2^{\frac{n}{2}})$。
算法二
考虑对图做出任意一颗生成树。
对于非树边，我们暴力枚举其选或不选。
对于生成树的部分，我们设$dp_{x,i,0/1}$表示$x$子树内已经做完，一共选了$i$条关键边，目前$x$的匹配状态是什么。
合并时需要枚举两个子树的第二维，枚举上界显然不会超过子树的大小。
如果这样枚举，复杂度实际只有$n^2$，可以发现任意两个点都会在lca处被计算一次。
那么我们的复杂度为$O(n^2*2^{m-n+1})$
正解
对于每个联通块，我们只需要选择复杂度小的算法即可。
最终复杂度为$O(n^2*2^{\frac{m}{3}})$。
T3
首先$A$与$B$两维顺序没有关系，我们默认$A\geq B$。
我们来尝试写出一个式子。首先肯定开始飞了之后就不会正常驾驶，容易想到枚举起飞位置。接下来是简单的鸽笼原理。
$\sum_{a=0}^A\sum_{b=0}^B\binom{a+b}{a}\sum_{x=1}^{min(A-a,B-b,C)}\binom{A-a-1}{x-1}\binom{B-b-1}{x-1}\binom{C-1}{x-1}$
$\sum_{i=0}^n\binom{a}{i}\binom{b}{n-i}=\binom{a+b}{n}$
从组合意义去理解，有$a+b$个格子，要求给$n$个格子染上黑色，求方案数。两个式子都能表达。
$\sum_{i=0}^n\binom{i}{a}\binom{n-i}{b}=\binom{n+1}{a+b+1}$
从组合意义去理解，有$n$个格子，要求给$a$个格子染上红色，给$b$个格子染上绿色，最后一个红色格子严格在最前一个绿色格子之前，同时还要选择一条分界线$i$，使得前$i$个格子只有红格子，后面只有绿格子。
不妨额外添加一个格子，同样要求给$a$个格子染红，$b$个格子染绿，还需要给一个格子染黄，规定一个格子只能染一种颜色。
要求黄格子前只有红格子，黄格子后只有绿格子。显然每一种新问题的染色方案对应原问题一种方案。
根据我们得出的答案的表达式，不妨先将$A,B,C$都减一，接下来设$up$表示$min(A,B,C)$。
为了方便对比，先贴出答案表达式。
$\sum_{a=0}^A\sum_{b=0}^B\binom{a+b}{a}\sum_{x=1}^{min(A-a,B-b,C)}\binom{A-a-1}{x-1}\binom{B-b-1}{x-1}\binom{C-1}{x-1}$
接下来用$x$代替原来的$x-1$，$a$代替原来的$A-a$，$b$代替原来的$B-b$，同时我们已将$A,B,C$减一。
$\sum_{x=0}^{up}\binom{C}{x}\sum_{a=0}^A\binom{a}{x}\sum_{b=0}^B\binom{b}{x}\binom{A+B-a-b}{A-a}$
$\sum_{x=0}^{up}\binom{C}{x}\sum_{a=0}^A\binom{a}{x}\sum_{b=0}^B\binom{b}{x}\binom{A+B-a-b}{A-a}$
注意到$b>B$会让$\binom{A+B-a-b}{A-a}$值为$0$，因此我们可以抬高上界。
$\sum_{x=0}^{up}\binom{C}{x}\sum_{a=0}^A\binom{a}{x}\sum_{b=0}^{A+B-a}\binom{b}{x}\binom{A+B-a-b}{A-a}$
$\sum_{x=0}^{up}\binom{C}{x}\sum_{a=0}^A\binom{a}{x}\binom{A+B-a+1}{A-a+x+1}$
使用之前基础知识提到的可以变换成这条式子。
$\sum_{x=0}^{up}\binom{C}{x}\sum_{a=0}^A\binom{a}{x}\binom{A+B-a+1}{A-a+x+1}$
$\sum_{x=0}^{up}\binom{C}{x}(\sum_{a=0}^{A+B+1}\binom{a}{x}\binom{A+B-a+1}{A-a+x+1}-\sum_{a=A+1}^{A+B+1}\binom{a}{x}\binom{A+B-a+1}{A-a+x+1})$
$\sum_{x=0}^{up}\binom{C}{x}(\sum_{a=0}^{A+B+1}\binom{a}{x}\binom{A+B-a+1}{B-x}-\sum_{a=A+1}^{A+B+1}\binom{a}{x}\binom{A+B-a+1}{A-a+x+1})$
前面部分可以使用基础知识提到的等式，后面部分我们改枚举$a-(A+1)$。
$\sum_{x=0}^{up}\binom{C}{x}(\binom{A+B+2}{B+1}-\sum_{a=0}^{B}\binom{a+A+1}{x}\binom{B-a}{x-a})$
容易发现$up,B\leq 10^6$，因此前面部分已经可以快速计算，接下来我们只考虑后面部分。
$\sum_{x=0}^{up}\binom{C}{x}\sum_{a=0}^{B}\binom{a+A+1}{x}\binom{B-a}{x-a}$
我们用基础知识介绍的等式拆开组合数。
$\sum_{x=0}^{up}\binom{C}{x}\sum_{a=0}^{B}\binom{B-a}{x-a}\sum_{i=0}^x\binom{A+1}{i}\binom{a}{x-i}$
$\sum_{x=0}^{up}\binom{C}{x}\sum_{i=0}^x\binom{A+1}{i}\sum_{a=0}^{B}\binom{B-a}{x-a}\binom{a}{x-i}$
$\sum_{x=0}^{up}\binom{C}{x}\sum_{i=0}^x\binom{A+1}{i}\sum_{a=0}^{B}\binom{B-a}{B-x}\binom{a}{x-i}$
$\sum_{x=0}^{up}\binom{C}{x}\sum_{i=0}^x\binom{A+1}{i}\binom{B+1}{B-i+1}$
$\sum_{i=0}^{up}\binom{A+1}{i}\binom{B+1}{B-i+1}\sum_{x=i}^{up}\binom{C}{x}$
后面部分可以预处理后缀和，那么这个式子也可以快速计算。
代码
T1
60’
1 | #include<bits/stdc++.h> |
std
1 | #include <cstdio> |
T2
std
1 | #include<cstdio> |
T3
10’
1 | #include<bits/stdc++.h> |
std
1 | #include<cstdio> |