### T1 背包
观察数据范围，$n\le 100000$，而且有多组数据，应该不能进行$\text{dp}$，因此应该考虑贪心。
$80$分：这是一种错误的计算方法。我们忽视物品放入背包和背包体积增大的时间差，把直接把所有的$a$和$b$加起来，计算结果是否非负。
$85$分：这也是一些错误的贪心策略。
我们考虑把物品分为$a\le b$（贡献非负）和$a>b$（贡献为正）这两类。对于贡献为正的物品，我们按照$a$升序，即体积从小到大放入背包；对于贡献为负的物品，我们按照$a$降序，即体积从大到小放入背包。然后先把所有贡献为正的物品放入背包，再放置贡献为负的物品即可。
这样有一个问题，就是可能有体积很大、贡献很小的物品，放入它之后其他物品就难以放入了。
还有一种策略是，对于贡献为负的物品，按照$b-a$降序放入背包。这样也有问题，就是可能某个物品在当前时刻可以被放入背包，但是再推迟就放不进了。例如，$n=2,v_0=4;a_1=2,b_1=1;a_2=4,b_2=2$。如果先放$1$号物品，$2$号物品就不能再放进去了。
$100$分：正确的贪心策略是，贡献为负的物品按照$b$降序（即使背包容量增加的值从大到小）放入背包。这个策略怎么理解或证明呢？我们可以这么想：放入这些物品，它们所占的总体积是不变的，而每个物品使背包体积增加的量是不同的，使背包体积增加较大的物品能为后来的物品创造一个比较好的状态。~~以上纯属瞎扯~~
### T2 动态点数
注意到，存在满足要求的$a_k$等价于$a_k=\min\left\{ a_i,a_{i+1},\cdots ,a_j \right\}$且$a_k=\gcd\left\{ a_i,a_{i+1},\cdots ,a_j \right\}$。
数据范围不大，$n\le 5\times 10^5$，因此可以考虑$\text{O}(n\log n)$或$\text{O}(n \log n\log n)$的算法。
我们对答案进行二分。对于某个二分值，我们枚举区间的起始点，并使用线段树或$\text{ST}$表计算区间最小值和区间$\gcd$，即可判断是否可行。
当然，这题还有使用栈的尺取法，时间复杂度为$\text{O}(n)$，具体可参考[cultry神犇的博客](https://www.luogu.org/blog/cultry-solution/t2-ling-xie)。
### T3 [放棋子](https://www.luogu.org/problemnew/show/P3158)
这道题的数据范围可能会让人误以为是状压$\text{dp}$，其实他是~~萌萌的~~数学题呀~ ~~数学题什么的最讨厌了~~ ~~数学上来先打表~~
$20$分：管你是什么题，上来就暴搜，$20$分拿到就跑。
$100$分：算了算了，别激动，认真想一下怎么做。
我们发现，每一种颜色的棋子都会占据某些行或某些列，因此我们考虑按照棋子的颜色进行决策。而且棋盘上的行和列都是平等的，剩余的具体是哪些行或哪些列并不影响答案，因此我们可以定义递推状态$f[i][j][k]$为使用$k$种颜色的棋子，占据了棋盘上$i$行$j$列的方案数。
我们容易发现，“使用$k$个同色棋子占据棋盘上$i$行$j$列的方案数目”是一个重要的量。因此我们记$g[i][j][k]$为使用$k$个同色棋子占据棋盘上$i$行$j$列的方案数目。那么$f[i][j][k]$的转移方程就可以写出来了，即
$$f[i][j][k]=\sum _{p=1}^{i-1}\sum^{j-1}_{q=1} f[p][q][k-1]\times g[i-p][j-q][a[k]]\times \text{C}^{i-p}_{n-p}\text{C}^{j-q}_{m-q}$$
上式要求$(i-p)(j-q)\ge a[k]$。其中组合数的部分可以理解为，$f[p][q][k-1]$的部分已经选择好了棋盘上的$p$行$q$列，现在还需要从$n-p$行$m-q$列中选出$i-p$行$j-q$列来占据。
现在的重要问题（也是考试时我怎么都想不出的问题）是如何计算$g[i][j][k]$。
$g[i][j][k]$表示的是在棋盘中**刚好完全**占据了$i$行$j$列的方案数，而我们很容易求出的是在棋盘中**至多**占据了$i$行$j$列的方案数。因此我们可以考虑使用递推，即使用所有方案数减去不完全占据的方案数。
于是，$g[i][j][k]$的递推式就是
$$g[i][j][k]=\text{C}^{k}_{i\times j} -\sum^{i}_{p=1}\sum^{j}_{q=1}g[p][q][k]\times \text{C}^{p}_{i} \text{C}^{q}_{j}$$
其中要求$p+q< i+j$（即$p,q$不同时等于$i,j$），$pq\ge k$。组合数部分可以理解为：现在需要占据其中的$i$行$j$列，那么恰好占据了**任意**$p$行$q$列的方案都是不合法的，而我们要从$i$行$j$列中选出这任意的$p$行$q$列，因此乘以$\text{C}^{p}_{i} \text{C}^{q}_{j}$。
有了$f$和$g$，我们就可以计算出答案了。由于题目要求棋子要放完，但没有要求每一行和每一列上都要有棋子，因此答案是$\sum_{i=1}^{n}\sum _{j=1}^{m} f[i][j][c]$。
上述过程的时间复杂度较高，为$\text{O}(n^2m^2\text{tot})$，其中$\text{tot}$指总棋子数。因此数据范围很小。这要求我们看出题目中所包含的组合数学元素，从而避免无脑地进行状压$\text{dp}$。
当然，有一些优化可以把时间复杂度降低到$\text{O}(n^2 m^2 c)$。由于我们只会使用$g$数组中$k=a[i]$的部分，而且转移时也不会使用到别的部分，因此我们可以在计算第$i$种颜色时再计算$g[x][y][a[i]]$这些值。
下面是优化后的代码。
```cpp
#include <cstdio>
#define MOD 1000000009
#define MAXN 55
#define MAXT 1005
#define MAXC 15
using namespace std;
long long f[MAXC][MAXN][MAXN];
long long g[MAXN][MAXN][MAXT];
long long c_num[MAXT][MAXT];
int a[MAXC];
int main(void){
int n,m,c;
int tot=0;
scanf("%d%d%d",&n,&m,&c);
for (int i=1;i<=c;i++)
scanf("%d",a+i);
for (int i=1;i<=c;i++)
tot+=a[i];
//Init of c_num
int tot_graph=n*m;
c_num[0][0]=1;
for (int i=1;i<=tot_graph;i++){
c_num[i][0]=1;
for (int j=1;j<=i;j++)
c_num[i][j]=(c_num[i-1][j]+c_num[i-1][j-1])%MOD;
}
f[0][0][0]=1;
//Calc f
for (int i=1;i<=c;i++){
int tk=a[i]; //Calc g[i][j][tk]
for (int ti=1;ti<=n;ti++){
for (int tj=1;tj<=m;tj++){
if (ti*tj<tk){
g[ti][tj][tk]=0;
continue;
}
if (ti*tj==tk){
g[ti][tj][tk]=1; //Only one method:full
continue;
}
g[ti][tj][tk]=c_num[ti*tj][tk];
for (int p=1;p<=ti;p++){
for (int q=1;q<=tj;q++){
if (p*q<tk)
continue;
if (p==ti && q==tj) //Can't equal at the same time
break;
g[ti][tj][tk]=(g[ti][tj][tk]+MOD-g[p][q][tk]*c_num[ti][p]%MOD*c_num[tj][q]%MOD)%MOD;
}
}
}
}
for (int j=1;j<=n;j++){
for (int k=1;k<=m;k++){
for (int p=0;p<j;p++){
for (int q=0;q<k;q++){
if ((j-p)*(k-q)<a[i])
break;
f[i][j][k]=(f[i][j][k]+
f[i-1][p][q]*g[j-p][k-q][a[i]]%MOD
*c_num[n-p][j-p]%MOD*c_num[m-q][k-q]%MOD)%MOD;
}
}
}
}
}
long long ans=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
ans=(ans+f[c][i][j])%MOD;
printf("%lld\n",ans);
return 0;
}
```