又上了节课。。。俩题
计算系数 组合数问题。。。
要不是大佬指点就只能阶乘暴力算了
（主要还是我忘了杨辉三角）
杨辉三角与组合数C有着千丝万缕的联系，在计算，使用方面相当方便。
先说计算系数
计算系数
给定一个多项式(by+ax)^k，请求出多项式展开后x^n*y^m项的系数。
输出结果%10007
#include<bits/stdc++.h>
using namespace std;
long long k,a,b;
long long n,m;
long long t=;
long long c[][];
int main(){
cin>>a>>b>>k>>m>>n;
c[][]=;
a=a%;
b=b%;
k=k%;
n=n%;
m=m%;//输入需要先取模，不然会很大
for(int i=;i<=k;i++){
for(int j=;j<=i;j++){
c[i][]=;
c[i][j]=c[i-][j]+c[i-][j-];//处理原理,杨辉三角
c[i][j]%=;//预处理,待会直接调用
}
}
for(int i=;i<=m;i++){
t*=a;
t%=;
}
for(int i=;i<=n;i++){
t*=b;
t%=;
}//忘记*a*b很致命...
cout<<(t%*c[k][n]%)%;
return ;
}
组合数问题
给定 n,m 和 k，对于所有的 0≤i≤n,0≤j≤min(i,m) 有多少对 (i,j) 满足C 是 k的倍数。
#include<bits/stdc++.h>
using namespace std;
int k;
int n,m;
int t;
int c[][];
int ans[][];
int main(){
scanf("%d%d",&t,&k);
for(int i=;i<=;i++) c[i][]=;
for(int i=;i<=;i++){
for(int j=;j<=i;j++){
c[i][j]=(c[i-][j]+c[i-][j-])%k;//这里取模免去以后的判断
}
}
for(int i=;i<=;i++){
for(int j=;j<=i;j++){
ans[i][j]=ans[i-][j]+ans[i][j-]-ans[i-][j-];//前缀和,减去重复的
if(!c[i][j]) ans[i][j]++;
}
ans[i][i+]=ans[i][i];
}
for(int a=;a<=t;a++){
scanf("%d%d",&n,&m);
if(n<m) m=n;
printf("%d\n",ans[n][m]);
}
return ;
}
同样杨辉三角
最后%下子谦。