[NOIP2016 提高组] 组合数问题
难度:普及+/提高
解题思路
此题需要计算大量的排列组合结果,所以选择杨辉三角来计算排列组合数。
解题难点
下面先编写了一段杨辉三角和计算个数的代码
90pts: O(tnm) 杨辉三角
#include <bits/stdc++.h> using namespace std; int k,t,n,m; int f[2500][2500],ans; int main(){ scanf("%d%d",&t,&k); f[0][0]=1; for(int i=1;i<2500;i++) for(int j=1;j<2500;j++){ f[i][j]=f[i-1][j-1]+f[i-1][j]; f[i][j]%=k; } while(t--){ ans=0; scanf("%d%d",&n,&m); for(int i=1;i<=n+1;i++) for(int j=1;j<min(i, m+1)+1;j++){ if(f[i][j]==0) ans++; } printf("%d\n",ans); } return 0; }
如果先要拿到100pts,那么就要对代码进行优化。
我们可以在计算杨辉三角时计算前缀和。
解题代码
100pts: O(tn) 杨辉三角与前缀和
#include <bits/stdc++.h> using namespace std; int k,t,n,m; int f[2500][2500],cnt[2500][2500],ans; int main(){ scanf("%d%d",&t,&k); f[0][0]=1; for(int i=1;i<2500;i++) for(int j=1;j<2500;j++){ f[i][j]=f[i-1][j-1]+f[i-1][j]; f[i][j]%=k; cnt[i][j]=cnt[i][j-1]+(!f[i][j]); } while(t--){ ans=0; scanf("%d%d",&n,&m); for(int i=1;i<=n+1;i++) ans+=cnt[i][min(i,m+1)]; printf("%d\n",ans); } return 0; }