这是一道典型的看上去很吊，实际上很渣的题。
省选考试时我是彻底挂在了这一题上。考试前两个小时一直在推这道题的公式，结果完全往错误的方向去想了，白白浪费的大量的时间。考试后才发现这道题的公式竟然是如此的**，不禁感觉自己就是个大**。
题目大意：给你一个n * m的棋盘，k和p，让你用1 - k的数字去填满这个棋盘，要求同一行从左至右不递减，每一行之间至少有一列数字不一样。问你最后方案数模p为多少。交换两行算不同的方案。
对于10%的数据，1 <= n, m, k <= 3;
对于40%的数据，1 <= n, m, k <= 1000;
对于60%的数据，p = 1000000007;
对于100%的数据，1 <= n, m <= 100000, 1 <= p, k <= 2000000000
给出两组样例应该看得更明白些：
输入：1 3 3 10 输出：0
输入：2 2 2 10 输出： 6
看到这个问题我们可以比较轻松地发现，只要计算出一行的方案数，就可以轻松求出总共的方案数。
而一行总共的方案数这个问题就是求一个序列，使得1 <= a1 <= a2 <= ······ <= am <= k，而这个问题并不好计算。我们可以把这个问题转化一下，变为：
求一个序列，使得1 < a1 + 1 < a2 + 2 < ······ < am + m < k + m + 1。而这个问题的方案数很明显是
。
这个问题如果用杨辉三角暴力求
能拿40分。。
而我们发现只需要求出
即可。用扩展欧几里得算法或者欧拉函数求出乘法逆元是能拿到p是质数的60分的。
但是因为数据太弱了。。。欧拉函数把合数当质数做能拿90分，而强行用中国剩余定理是100分。。。
这道题的正解也是简单的一塌糊涂。。。我们发现m是小于100000的整数，那么我们可以把小于m的质数全部求出来，然后暴力枚举每个质数，从分子里把对应指数的这些质数从分母里除去。然后就暴力做完了。答案也显而易见了。
我考试的时候都在干什么啊ORZ。。。。。。
放上我的渣代码，求轻喷。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
using namespace std;
const int MAXN = 101010;
const int MAXP = 10101;
int n, m, p, k, u[MAXN], d[MAXN];
int tot, prime[MAXP], whe[MAXN];
void init()
{
scanf("%d%d%d%d", &n, &m, &k, &p);
for(int i = 2; i <= m; i ++)
if(!whe[i])
{
prime[tot ++] = i;
for(int j = 2; i * j <= m; j ++)
if(!whe[i * j])
whe[i * j] = 1;
}
}
void work()
{
for(int i = 0; i < m; i ++)
{
u[i] = k + i;
d[i] = i + 1;
}
for(int i = 0; i < tot; i ++)
{
int cnt = 0;
for(int j = prime[i] - 1; j < m; j += prime[i])
if(d[j] % prime[i] == 0)
while(d[j] % prime[i] == 0)
d[j] /= prime[i], cnt ++;
int tak = (k - 1) % prime[i] + 1;
for(int j = prime[i] - tak; j < m; j += prime[i])
if(u[j] % prime[i] == 0)
{
while(u[j] % prime[i] == 0 && cnt)
u[j] /= prime[i], cnt --;
if(!cnt)
break;
}
}
long long int st = 1;
for(int i = 0; i < m; i ++)
(st *= u[i]) %= p;
if(st < n)
printf("0\n");
else
{
long long int ans = 1;
for(int i = 0; i < n; i ++)
{
(ans *= st) %= p;
st --;
}
printf("%I64d\n", ans);
}
}
int main()
{
init();
work();
return 0;
}