题面
前言
这道题作为我们的考试题，蒟蒻我不透彻第一类斯大林数，就只打了个爆搜 10分滚粗。丢人。
果然，我是这个机房最菜的。
今天，就恶补一下第一类斯大林数。
前置芝士
-
第一类斯大林数
-
组合数
不会的童鞋，右转上边那篇博客，哪里有详细介绍。
题解
首先，一句话题意问我们前缀最大值为 \(A\) 且 后缀最大值为 \(b\) 的排列有几种。
我们思考这样一个问题，最大的数 \(n\) 会把我们的序列分成两部分，
前边就是我们的前缀最大值，后边就是我们的后缀最大值。（因为 \(n\) 是最大的数了，其他没有比他再大的了）
也就是说，我们把 \(n\) 看做一个分水岭，他左边的被左边的挡住，右边的被右边的挡住。
那我们把一个数以及被他挡住的一个数看成一个块。 \(n\)这个数看成独立的一块。
引用下luogu 的图片
每个块都由块内最大的数表示。
那我们就需要把这 剩下的 \(n-1\) 个数 分到 \(A+B-2\) 个块中。
这也就是第一类斯大林数 \(S_{n-1}^{A+B-2}\)
我们把每个块填完之后，就要分是把这个块放到 \(n\) 的左边还是右边
这就用到了组合数 \(C_{A+B-2}^{A-1}\)
这个柿子的意思是，我们在 \(A+B-2\) 个块中 选 \(A-1\) 个块的方案数
所以，最后的总柿子就是 \(S_{n-1}^{A+B-2} \times C_{A+B-2}^{A-1}\)
第一类斯大林数可以通过它的递推式来求，组合数也可以用杨辉三角。
最后的复杂度就是 \(O(A*n)+O(A*A)\) 的预处理，以及 O(1)的回答
Code：
#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int p = 1e9+7;
int n,a,b,Q;
long long s[50010][250],c[250][250];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s =s * 10+ch - '0'; ch = getchar();}
return s * w;
}
void YYCH()//预处理第一类斯大林数和组合数
{
s[0][0] = 1;
for(int i = 1; i <= 50000; i++)
{
for(int j = 1; j <= 240; j++)
{
s[i][j] = (s[i-1][j-1] + s[i-1][j] * (i-1) % p) % p;
}
}
c[0][0] = 1;
for(int i = 1; i <= 240; i++)
{
c[i][0] = 1;
for(int j = 1; j <= i; j++)
{
c[i][j] = (c[i-1][j-1] + c[i-1][j]) % p;
}
}
}
int main()
{
Q = read(); YYCH();
while(Q--)
{
n = read(); a = read(); b = read();
long long ans = s[n-1][a+b-2] * c[a+b-2][a-1] % p;//回答
printf("%lld\n",ans);
}
return 0;
}
总结
考场上不会推也不要紧，自己打表找找规律。
此外也可以用来和自己推到的柿子进行对拍。
另外还有本题的加强版 CF960G Bandit Blues
不过这题要用 NTT来写。
但 Ame__ 大佬A了这道题 %%%。