MicDZ's blog

NOIP2016中除了玩具谜题这道大水题之外,稍难一点的就是这道题了。

题目链接

核心思路

用杨辉三角存储下组合数的值,利用二维前缀和累加。代码实现非常简单,思维难度仅限于杨辉三角的部分。

不要被题面所迷惑了,都是骗人的,使用公式最多30分(代码完成度非常高且非常鲁棒)。

杨辉三角

1
2
3
4
5
6
     1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
…… ……

上述就是最基础的杨辉三角。

你可以很轻松地发现第nn行的第kk个数字为组合数 Cn1k1C^{k-1}_{n-1}

具体的论证过程参照here

这样我们就可以Θ(2000×2000)\Theta(2000\times \sqrt{2000})把所有的组合数的值求出来了

二维前缀和

可以参照我的这篇文章

这里的转移方程是

1
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];

s(i,j)表示题意中的n,m所对应的对数。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
#define MAXN 2000+10

using namespace std;

int read() {//快读略
}
int a[MAXN][MAXN],s[MAXN][MAXN];
int main() {
int t=read(),k=read();
for(int i=0;i<=2000;i++) {
a[i][i]=1;
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]+a[i-1][j-1])%k;//在计算的时候直接%k可以避免后面无效的重复计算
for(int i=1; i<=2000; i++)
for(int j=1; j<=2000; j++) {
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];//前缀和口诀:上加左 减左上 加自己
if(a[i][j]==0&&j<=i) s[i][j]++;//如果a[i][j]满足要求则++
}
for(int i=1; i<=t ;i++) {
int n=read(),m=read();
printf("%d\n",s[n][m]);
}
return 0;
}

 评论