P5135 painting（组合数）

传送门

如果\(op==1\)，那么每一个方案都可以看做从\(n\)个数里选出\(m\)个数，然后\(sort\)一下依次放到每列，方案数就是\({n\choose m}\)。因为\(n\)很大，但是\(m\)不大，所以可以直接计算\(\prod_{i=n-m+1}^ni\)，以及\(m\)的阶乘的逆元

如果\(op==0\)，我们枚举不同的列的个数\(i\)，那么选的方法有\({n\choose i}\)，然后相当于是把\(m\)分成\(i\)段连续的数，也就是\(i\)个数相加和为\(m\)的非负整数解的个数，为\({m-1\choose i-1}\)，于是方案数为\(\sum_{i=1}^{min(n,m)}{n\choose i}{m-1\choose i-1}\)，从\({n\choose i}\)到\({n\choose i+1}\)可以\(O(1)\)计算

//minamoto

#include<bits/stdc++.h>

#define R register

#define int long long

#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}

using namespace std;

char buf[1<<21],*p1=buf,*p2=buf;

inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}

int read(){

    R int res,f=1;R char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

const int N=1e6,P=1e9+7;

int inv[N+5],fac[N+5],ifac[N+5],n,m,op,res,qaq;

inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}

inline int mul(R int x,R int y){return (x%P)*(y%P)%P;}

inline int C(R int n,R int m){return fac[n]*ifac[m]%P*ifac[n-m]%P;}

void init(){

	inv[0]=inv[1]=1;

	fp(i,2,N)inv[i]=mul(inv[P%i],P-P/i);

	fac[0]=ifac[0]=1;

	fp(i,1,N)fac[i]=mul(fac[i-1],i),ifac[i]=mul(ifac[i-1],inv[i]);

}

signed main(){

//	freopen("testdata.in","r",stdin);

	int T=read();init();

	while(T--){

		n=read(),m=read(),op=read();

		if(op==1){

			if(m>n)puts("0");

			else{

				res=1;

				fp(i,n-m+1,n)res=mul(res,i%P);

				res=mul(res,ifac[m]);

				printf("%lld\n",res);

			}

		}else{

			res=0,qaq=n%P;

			fp(i,1,min(m,n)){

				res=add(res,mul(qaq,C(m-1,i-1)));

//				printf("%lld\n",mul(qaq,C(m-1,i-1)));

				qaq=qaq*inv[i+1]%P*((n-i)%P)%P;

			}printf("%lld\n",res);

		}

	}return 0;

}

巴特西

P5135 painting（组合数）

最新文章

热门文章