资讯详情

题目概述

给出 \(n,m,k,p\)，表示 \(n\) 行 \(m\) 列，然后每 \(n\) 行填充一个单调不下降的序列且数值为 \([1,k]\)。

任意两行之间至少需要一列不同。

\(1\leq n,m\leq 10^5,1\leq k,p\leq 2\cdot 10^9.\)

分析

本质上就是组合计数。

首先考虑一行有多少种选择，要是这个选择为 \(t\)，那么最终的答案就是 \(A_{t}^n\)。

考虑怎么求 \(t\)，套路地，映射到数组上。

首先有 \(1\leq a_1\leq a_2\leq \dots\leq a_m\leq k\)。

套路地令 \(b_i=a_i+i\)，然后：

\[1< b_1<b_2<\dots<b_m\leq k+m \]

这相当于选择几个数然后自动排序，所以说一行的答案就是 \(\binom{k+m-1}m\)。

考虑求这个东西，因为 \(p\) 不是质数，显然往 exlucas 方面想，发现 \(p\) 太大，exlucas 可能 TLE，因此我们只需要利用它的思路即可。

分解质因数然后CRT合并即可。

对于求取模结果，只需要和exlucas类似地搞一下这个即可，这一部分最多时间复杂度 \(\mathcal{O}(m\log k)\)。

直接做就行了。

代码

时间复杂度 \(\mathcal{O}(n+m\log k)\)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <map>
#define int long long
//#define N 
using namespace std;
#define isdigit(ch) ('0' <= ch && ch <= '9')
template<typename T>
void read(T&x) {x = 0;char ch = getchar();for (;!isdigit(ch);ch = getchar());for (;isdigit(ch);ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
}
template<typename T>
void write(T x) {if (x > 9) write(x / 10);putchar(x % 10 + '0');
}
int qpow(int a,int b,int mod) {int res = 1;while(b) {if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}
int gcd(int a,int b) {return b ? gcd(b,a % b) : a;
}
void exgcd(int a,int b,int &x,int &y) {if (b == 0) return x = 1,y = 0,void();int xx,yy;exgcd(b,a % b,xx,yy);x = yy,y = xx - a / b * yy;
}
int inv(int a,int mod) {int x,y;int g = gcd(a,mod);if (g ^ 1) return -1;exgcd(a,mod,x,y);return (x % mod + mod) % mod;
}
bool check(int n,int m,int lim) {int res = 1;for (int i = 1;res < lim && i <= m;res = res * (n - i + 1) / i,i ++);if (res < lim) return false;return true;
}
int C(int n,int m,int p,int pk) {int fz = 1,fm = 1;int cnt1 = 0,cnt2 = 0;for (int i = 1;i <= m;i ++) {int x = n - m + i;while(x % p == 0) x /= p,cnt1 ++;fz = fz * (x % pk) % pk;int y = i;while(y % p == 0) y /= p,cnt2 ++;fm = fm * (y % pk) % pk;}return fz * inv(fm,pk) % pk * qpow(p,cnt1 - cnt2,pk) % pk;
}
vector<pair<int,int>> factor;
vector<int> a,b;
signed main(){int n,m,k,p;read(n),read(m),read(k),read(p);if (p == 1) return putchar('0'),0;if (!check(m + k - 1,m,n)) return putchar('0'),0;int t = p;for (int i = 2;i * i <= t;i ++)if (t % i == 0) {int cnt = 0;while(t % i == 0) cnt ++,t /= i;factor.push_back({i,cnt});}if (t > 1) factor.push_back({t,1});for (auto i : factor) {int pk = i.first;for (int j = 1;j < i.second;j ++) pk = pk * i.first;int t = C(m + k - 1,m,i.first,pk),res = 1;for (int j = 0;j < n;j ++) res = res * (t - j) % pk;a.push_back(res),b.push_back(pk);}t = 1;for (auto i : b) t = t * i;int res = 0,temp;for (int i = 0;i < a.size();i ++) temp = t / b[i],res = (res + temp * a[i] % p * inv(temp,b[i]) % p) % p;write(res);return 0;
}