這是一道典型的看上去很吊，實際上很渣的題。
省選考試時我是徹底挂在了這一題上。考試前兩個小時一直在推這道題的公式，結果完全往錯誤的方向去想了，白白浪費的大量的時間。考試後才發現這道題的公式竟然是如此的**，不禁感覺自己就是個大**。
題目大意：給你一個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;
}