洛谷 P2822 组合数问题（NOIp 提高组2016）
思路
首先想到的当然是暴力，直接暴力阶乘然后算，开个longlong然后得分看天。
我想了好久怎么优化，好像想到了一个(O(nmt))的算法，但是写挂了，(WA)了好多点，还(T)了两个点，只得了(30pts)。
然后我就开始想正解。然而想了半天也不会。只发现他给出全局不变的(k)，应该是可以预处理然后(O(1))查询。虽然这的确就是正解的思路，但我死活就是不会。
看了眼题解，发现有种东西叫做杨辉三角，于是茅塞顿开，恍然大悟，发现可以用杨辉三角预处理出所有的值。因为(nm)的范围较小，两层循环不会炸，所以可以(dp)转移，边加边模得到所有的值。然后判断，如果这个值是(k)的倍数，那么将这个位置的值赋为1。反之就是0。然后每次查询的时候扫一遍整个杨辉三角再输出答案。但发现这样的复杂度仍和我一开始写挂了的算法时间复杂度相同，实际测试可以得到90分。在考场上的话这个分属实很可以了。
但练习就要寻求正解。很容易想到这个东西可以通过前缀和来优化得到。看了好几篇题解，都是用一种奇妙的前缀和优化加上容斥，从而实现(O(1))查询，总时间复杂度为(O(nm+t))。但这些题解太多了我不必赘述，就记录一下作为蒟蒻的我的前缀和优化吧。我想不到那么神仙的容斥，于是我就求出了每一列的前缀和。这样查询的时候我从最后一行第一个开始扫，扫上(m)行，然后累加答案，这样的总复杂度就是(O(nm+tm))了。但由于(t)的范围也很小，所以这样还是可以(A)掉这个题的。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
int n,m,t,k;
int f[2010][2010],s[2010][2010];
int main()
{
scanf("%d%d",&t,&k);
for(int i=0;i<=2000;i++){
f[i][0]=1;
f[i][i]=1;//杨辉三角初始化
}
for(int i=1;i<=2000;i++){
for(int j=1;j<=2000;j++){
f[i][j]=(f[i-1][j-1]%k+f[i-1][j]%k)%k;//边加边模
}
}
for(int i=1;i<=2000;i++){
for(int j=1;j<=i;j++){//注意这个循环，这两层循环恰好代表了整个杨辉三角，如果j循环到2000的话，就会多出右上角的部分，它们都为0。但注意，0%任何数都是0，所以就会导致多算很多答案，从而导致出现错误答案
s[i][j]=s[i-1][j];
if(f[i][j]%k==0){
s[i][j]++;
}
}
}
for(int i=1;i<=t;i++){
int ans=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
ans+=s[n][i];
}
printf("%d
",ans);
}
return 0;
}