HHHOJ #666. 「NOIP2021模拟赛 By CQY C」相爱（loved）

题面传送门
真 十二重计数法弱化版。
这里就讲一下8,9
8的话随便推一下就是\((^{n-1}_{m-1})\)
但是\(n,m\leq 10^9\)的范围显然不可行。
我们发现模数等于\(3*10007*35617\)，然后可以Lucas之后中国剩余定理合并。
9的话就是集合划分数，有一个经典的dp:设\(dp_{i,j}\)表示\(i\)个数分成\(j\)份，那么有\(dp_{i,j}=dp_{i,j-1}+dp_{i-j,j}\)，一个是多分了一个0，另一个是将现有的所有都加上\(1\).
然后\(O(n^2)\)递推就好了。
code:

#include
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define RI re int
#define ll long long
#define db double
#define lb long db
#define M 30000
#define mod 1000000007
#define eps (1e-4)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
using namespace std;
struct IO{
    static const int S=1<<21;
    char buf[S],*p1,*p2;int st[105],Top;
    ~IO(){clear();}
    inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
    inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
    inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='\r');return *this;}
    templateinline IO&operator >> (T&x){
        x=0;bool f=0;char ch=gc();
        while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
        while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
        f?x=-x:0;return *this;
    }
    inline IO&operator << (const char c){pc(c);return *this;}
    templateinline IO&operator << (T x){
        if(x<0) pc('-'),x=-x;
        do{st[++st[0]]=x%10,x/=10;}while(x);
        while(st[0]) pc('0'+st[st[0]--]);return *this;
    }
}fin,fout;
int T,op;
I ll mpow(ll x,int y=mod-2){ll Ans=1;while(y) y&1&&(Ans=Ans*x%mod),y>>=1,x=x*x%mod;return Ans;}
namespace Solve1{
	int x,y;
	I void Make(){
		while(T--) fin>>x>>y,fout<>x>>y,fout<<(x>y?0:frc[y]*Inv[y-x]%mod)<<'\n';
	}
}
namespace Solve3{
	const int N=200000;int x,y;ll Inv[N+5],frc[N+5],Ans;I void Make(){
		RI i;for(frc[0]=i=1;i<=N;i++)frc[i]=frc[i-1]*i%mod;Inv[N]=mpow(frc[N]);for(i=N-1;~i;i--) Inv[i]=Inv[i+1]*(i+1)%mod;
		while(T--){
			fin>>x>>y;for(i=0;i<=y;i++) Ans+=(i&1?mod-frc[y]*Inv[i]%mod*Inv[y-i]%mod*mpow(y-i,x)%mod:frc[y]*Inv[i]%mod*Inv[y-i]%mod*mpow(y-i,x)%mod);printf("%lld\n",Ans%mod); 
		}
	}
}
namespace Solve4{
	const int N=5000;ll dp[N+5][N+5];int x,y;I void Make(){
		RI i,j;dp[0][0]=1;for(i=1;i<=N;i++){
			for(j=1;j<=N;j++) dp[i][j]=(dp[i-1][j-1]+dp[i-1][j]*j)%mod;
		}
		for(i=1;i<=N;i++){
			for(j=1;j<=N;j++) dp[i][j]+=dp[i][j-1];
		}
		while(T--) fin>>x>>y,fout<>x>>y;for(i=0;i<=y;i++) Ans+=(i&1?mod-frc[y]*Inv[i]%mod*Inv[y-i]%mod*mpow(y-i,x)%mod:frc[y]*Inv[i]%mod*Inv[y-i]%mod*mpow(y-i,x)%mod);fout<>x>>y;y--;Ans=1;for(i=x+1;i<=y+x;i++) Ans=Ans*i%mod;for(i=1;i<=y;i++) Ans=Ans*Inv[i]%mod;fout<>x>>y;fout<<(x>y?0:frc[y]*Inv[x]%mod*Inv[y-x])%mod<<'\n';
		}
	}
}
namespace Solve8{
    I ll mpow(ll x,int p,int y){ll Ans=1;while(y) y&1&&(Ans=Ans*x%p),y>>=1,x=x*x%p;return Ans;}
	const int N=40000,p1=3,p2=10007,p3=35617,Mod=p1*p2*p3;int X[N+5<<2],Y[N+5<<2];ll Inv[N+5],frc[N+5],Ans,A1[N+5<<2],A2[N+5<<2],A3[N+5<<2];
	I ll Lucas(int n,int m,int p){if(!n||!m) return 1;return (n%p>X[i]>>Y[i],X[i]--,Y[i]--;
		for(frc[0]=Inv[0]=i=1;iX[i]?0:(A1[i]*p2*p3%Mod*mpow(p2*p3,p1,p1-2)+A2[i]*p1*p3%Mod*mpow(p1*p3,p2,p2-2)+A3[i]*p1*p2%Mod*mpow(p1*p2,p3,p3-2))%Mod)<<'\n';
	}
}
namespace Solve9{
	const int N=5000;ll dp[N+5][N+5];int x,y;I void Make(){
		RI i,j;for(i=0;i<=N;i++) dp[0][i]=1;for(i=1;i<=N;i++){
			for(j=0;j<=N;j++) dp[i][j]=dp[i][j-1],i>=j&&(dp[i][j]=(dp[i][j]+dp[i-j][j])%mod);
		}while(T--) fin>>x>>y,fout<=j&&(dp[i][j]=(dp[i][j]+dp[i-j][j])%mod);
		}while(T--) fin>>x>>y,fout<<(x>=y?dp[x-y][y]:0)<<'\n';
	}
}
int main(){
	freopen("1.in","r",stdin);freopen("1.out","w",stdout);
    fin>>T>>op;
    if(op==1) Solve1::Make();
	if(op==2) Solve2::Make();
    if(op==3) Solve3::Make();
    if(op==4) Solve4::Make();
    if(op==5) Solve5::Make();
	if(op==6) Solve6::Make();
    if(op==7) Solve7::Make();
    if(op==8) Solve8::Make();
    if(op==9) Solve9::Make();
    if(op==10) Solve10::Make();
    // 不建议用 scanf 和 printf，会多占用 0.2 s 的时间、
    return 0;
}