A

原本两维息息相关，相当麻烦，容易想到转$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)$。

B

不妨让我们先换一种方式描述积和式。

一个边权二分图，一个完美匹配的贡献为匹配边边权的乘积。

求所有完美匹配贡献的和。

接下来我们认为矩阵上不为$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}})$。

C

首先$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}$

后面部分可以预处理后缀和，那么这个式子也可以快速计算。