- 有一个(n imes m)的表格，要求在每个格子里填上(1sim k)的整数。
- 要求每一行的数单调不降，任意两行的数不完全相同，求能填出多少个不同的表格。
- (n,mle10^5,kle2 imes10^9)，模数不一定是质数
组合数学简单题
首先考虑计算一行的填法，粗糙地想就是从(k)个数中选出(m)个，但因为可重，还要增加上(m-1)个辅助元。
因此方案数就是(C_{m+k-1}^m=frac{(m+k-1)!}{m!(k-1)!})，上下同时约去((k-1)!)之后发现都只剩(m)项。
由于模数不一定是质数，且剩余的分母为(m!)，我们直接枚举(2sim m)中的所有质因子去约分，最终把分子中没被约分过的因子和约分后剩余的因子乘起来即可。
知道了一行的填法（设其为(t)），任选(n)种填法的排列就可以形成一个表格，因此就是(A_t^n=t^{underline{n}})，直接暴力算一遍就好了。
代码：(O(n+m))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define M 100000
using namespace std;
int n,m,k,X,c[M+5],u[M+5],v[M+5];
int main()
{
RI i,j,x;for(scanf("%d%d%d%d",&n,&m,&k,&X),i=1;i<=m;++i) u[i]=i+k-1,v[i]=i;//记下分子和分母
for(i=2;i<=m;++i)//枚举2~m中的所有质因子去约分
{
for(j=i;j<=m;j+=i) W(!(v[j]%i)) v[j]/=i,--c[i];//计算1~m中的次数
for(j=((k-1)/i+1)*i-(k-1);j<=m;j+=i) W(!(u[j]%i)) u[j]/=i,++c[i];//计算k~m+k-1中的次数
}
RI t=1;for(i=1;i<=m;++i) t=1LL*t*u[i]%X;for(i=1;i<=m;++i) W(c[i]--) t=1LL*t*i%X;//统计没被约过的因子和约分剩下的因子
RI s=1;for(i=1;i<=n;++i) s=1LL*s*(t--)%X;return printf("%d
",s),0;//计算排列数
}