题目背景
“随您怎么说,都由您好了。”他一面走出门道,到楼梯口去,一面说,“只是我得跟您预先声明一下:说不定有人偷听了我们的谈话了,为了避免我们的谈话被人家误解以致闹出什么乱子起见,我得把我们的谈话内容报告校长 —— 把大意说明一下。我不能不这样做。”
题目描述
校长听完很生气,以至于他把他十分拿手的冒泡排序都打错了:
@param p a permutation of 1~n
@param k an arbitrary variable
for(int i=1;i<=k;i++) // the upper limit should be @p n instead of @p k
for(int j=1;j<n;j++)
if(p[j]>p[j+1]) swap(p[j],p[j+1]);
不幸的是,校长在使用它对一个 \(1\sim n\) 的排列 \(\sigma\) 排序时并没有注意到这个问题,以至于祂没有喝上奶茶。
让祂更生气的,是大样例居然没有将这个错误测试出来,这让校长变得十分疯狂,于是就有了「疯狂の校长」,「疯狂の校长」找不到发泄对象,只好把 狗狗 装在套子里面,于是就有了 套套狗,简称 \(\sf TTG\),「疯狂の校长」让一只 \(\sf TTG\) 找到为什么大样例并没有测出祂的错误,这只 \(\sf TTG\) 通过一种 \(\mathcal O(n^3)\) 的算法发现,一种名为 套子 的排列会让「疯狂の校长」喝不上奶茶。具体来说,若一个排列 \(\sigma\) 在进行完以上的冒泡排序之后,存在一个长度为 \(n-1\) 的上升子序列,我们则称 \(\sigma\) 是 套子。
由于「疯狂の校长」还想要更多的 套套狗,所以祂想要找到当给定 \(n,k\) 时,祂一共会有多少套子,以便祂抓来数量相当的 狗狗 制作 套套狗,由于这个数字可能会很大,祂只需要你输出 \(\text{Ans}\bmod p\) 的结果,其中 \(p\) 为一给定质数。然而,即使是只知道这个余数,「疯狂の校长」也会知道祂需要多少 狗狗,因为总有 人 会报告给祂。
数据范围与提示
共 \(T\) 组测试,对于 \(100\%\) 的数据,满足 \(1\le n,k,T\le 5000,10^8\le p\le 10^9+7\). 然而空间只有 \(\rm 64MB\).
# include <bits/stdc++.h>
using namespace std;
// # define NDEBUG
# include <cassert>
namespace Elaina {
# define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
# define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
# define fi first
# define se second
# define mp(a, b) make_pair(a, b)
# define Endl putchar(‘\n‘)
# define mmset(a, b) memset(a, b, sizeof (a))
# define mmcpy(a, b) memcpy(a, b, sizeof (a))
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
template <class T> inline T fab(T x) { return x < 0? -x: x; }
template <class T> inline void getmin(T& x, const T rhs) { x=min(x, rhs); }
template <class T> inline void getmax(T& x, const T rhs) { x=max(x, rhs); }
inline char fgetc() {
# define BUFFERSIZE 5000
static char BUF[BUFFERSIZE], *p1=BUF, *p2=BUF;
return p1==p2 && (p2=(p1=BUF)+fread(BUF, 1, BUFFERSIZE, stdin), p1==p2)? EOF: *p1++;
}
template <class T> inline T readin(T x) {
x=0; int f=0; char c;
while((c=fgetc())<‘0‘ || ‘9‘<c) if(c==‘-‘) f=1;
for(x=(c^48); ‘0‘<=(c=fgetc()) && c<=‘9‘; x=(x<<1)+(x<<3)+(c^48));
return f? -x: x;
}
template <class T> inline void writc(T x, char s=‘\n‘) {
static int fwri_sta[55], fwri_ed=0;
if(x<0) putchar(‘-‘), x=-x;
do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
putchar(s);
}
} using namespace Elaina;
const int maxn=5000;
int n, k, mod;
inline int qkpow(int a, int n) {
int ret=1;
for(; n>0; n>>=1, a=1ll*a*a%mod)
if(n&1) ret=1ll*ret*a%mod;
return ret;
}
int mn[maxn+5];
inline void solve() {
n=readin(1), k=readin(1), mod=readin(1);
if(k>=n) {
int fac=1;
rep(i, 1, n) fac=1ll*fac*i%mod;
writc(fac); return;
}
int ans=0, fac=1;
rep(i, 1, k+1) fac=1ll*fac*i%mod;
ans=1ll*fac*qkpow(k+1, n-k-1)%mod; // no k+1
rep(len, 1, n-k-1) { // only one k+1 segment
int coe=(n-k-1)-len+1;
ans=(ans+1ll*fac*coe%mod*qkpow(k+1, n-k-1-len)%mod)%mod;
}
int mul=1;
rep(i, 1, n) mn[i]=min(i-1, k), mul=1ll*mul*(mn[i]+1)%mod;
// one of the number strictly over k+1
rep(i, 1, n) {
int res=max(0, i-1-(k+2)+1);
ans=(ans+1ll*mul*qkpow(mn[i]+1, mod-2)%mod*res%mod)%mod;
}
writc(ans);
}
signed main() {
rep(_, 1, readin(1)) solve();
return 0;
}
原文:https://www.cnblogs.com/Arextre/p/15253300.html