组合数与杨辉三角
递推公式:Cnm = Cn-1m-1 + Cn-1m;
杨辉三角前缀和(注意边界(i,i)):找到k整除Cij(0~n)(0~m)的数量
s[i][j] = s[i - 1][j];
if (i != j) s[i][j] += s[i - 1][j - 1] + s[i - 1][j];
这里说明为什么i==j时不需要加s[i - 1][j - 1] - s[i - 1][j]
因为:这里其实加了:但是s[i - 1][j - 1] == s[i - 1][j],所以等于没加
杨辉三角前缀和处理一
#include <iostream>
#include <cstring>
using namespace std;
const int N = 2010;
int a[N][N];
int s[N][N];
int main()
{
int q, k, n, m;
scanf("%d%d", &q, &k);
//组合数初始化,前缀和初始化
for (int i = 0; i <= 2000; i ++) a[i][0] = 1;
for (int i = 1; i <= 2000; i ++)
{
for (int j = 1; j <= i; j ++ )
{
a[i][j] = (a[i - 1][j - 1] + a[i - 1][j]) % k;
int x = !a[i][j] ? 1 : 0;
s[i][j] =s[i][j - 1] + x;
if (i != j) s[i][j] += s[i - 1][j] - s[i - 1][j - 1];
}
}
while (q -- )
{
scanf("%d%d", &n, &m);
printf("%d\n", s[n][min(n, m)]);
}
return 0;
}
杨辉三角前缀和处理二
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 2010;
int a[N][N];
int s[N][N];
int main()
{
int q, k, n, m;
scanf("%d%d", &q, &k);
//组合数初始化,前缀和初始化
for (int i = 0; i <= 2000; i ++) a[i][0] = 1;
a[1][1] = 1;
for (int i = 2; i <= 2000; i ++)
{
for (int j = 1; j <= i; j ++ )
{
a[i][j] = (a[i - 1][j - 1] + a[i - 1][j]) % k;
int x = !a[i][j] ? 1 : 0;
s[i][j] =s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + x;
}
s[i][i + 1] = s[i][i];//继承
}
while (q -- )
{
scanf("%d%d", &n, &m);
printf("%d\n", s[n][min(n, m)]);
}
return 0;
}