我不会斯特林数。
CF960G Bandit Blues
给你三个正整数 \(n\)，\(a\)，\(b\)，定义 \(A\) 为一个排列中是前缀最大值的数的个数，定义 \(B\) 为一个排列中是后缀最大值的数的个数，求长度为 \(n\) 的排列中满足 \(A = a\) 且 \(B = b\) 的排列个数。\(n \le 10^5\)，答案对 \(998244353\) 取模。
一道水黑。
排列，计数题，与数之间的相对大小有关，buff 叠满了。
从大到小插入数。设正在插入 \(u = n - i\)，插入它之前有 \(i + 1\) 个空位。
如果 \(i = 0\)，也就是插入 \(n\)，那么它一定同时是前缀最大值和后缀最大值。
如果 \(i = 1\)，那么它能插入两个空位之一，能够成为前缀最大值或后缀最大值，各有 \(1\) 个空位可行。
否则有三种情况：
- 插入到当前序列最左边，贡献一个前缀最大值，有 \(1\) 个空位可行。
- 插入到当前序列最右边，贡献一个后缀最大值，有 \(1\) 个空位可行。
- 插入到其他位置，不贡献，有 \(i - 1\) 个空位。
把 \(i = 0\) 的情况解决掉，令 \(n, a, b\) 都减去 \(1\) 即可。下文默认 \(n, a, b\) 都减了 \(1\)。
那么剩下可以套个多项式。用变量 \(x\) 代表前缀最大值，\(y\) 表示后缀最大值的话，对每个数有三种选择，成为前缀最大值、后缀最大值或者不贡献，所以答案可以表示为：
\[[x^ay^b]\prod _{i = 0} ^{n - 1} (x + y + i) \]啊？这里有两个变量， \([x^ay^b]\) 我不会操作啊！
注意前缀最大值和后缀最大值互不干扰，也就是每个数都既有前缀最大值的可能也有后缀最大值的可能。
那就能把 \(x\) 和 \(y\) 合并起来了。把操作转化为每个数有两种选择，成为前或后缀最大值，或者不贡献。
然后再用组合数把成为前缀最大值的数挑出来就行了。
所以式子可以化成这个样子：
\[\binom{a + b}{a}[x^{a + b}] \prod _{i = 0} ^{n - 1} (x + i) \]后半部分用分治 NTT 求一下就行了。见 P6012 或者 AT_abc352_g。（P6012 因为模数不喜欢没写）
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
namespace poly {
const int G = 3, P = 998244353;
int Ksm(int u, int v) {
int ret = 1;
while (v) {
if (v & 1) ret = 1ll * ret * u % P;
u = 1ll * u * u % P, v >>= 1;
}
return ret;
}
int NTT(vector<int> &A, int N) {
int d = N >> 1;
vector<int> trn;
trn.push_back(0);
trn.push_back(d);
for (int w = 2; w <= N; w <<= 1) {
d >>= 1;
for (int c = 0; c < w; c ++)
trn.push_back(trn[c] | d);
}
for (int i = 1; i < N; i ++)
if (trn[i] > i)
swap(A[i], A[trn[i]]);
for (int len = 2, M = 1; len <= N; M = len, len <<= 1) {
int W;
W = Ksm(G, (P - 1) / len);
for (int l = 0; l <= N - len + 1; l += len) {
auto w0 = 1;
for (int nw = l; nw < l + M; nw ++) {
int x = A[nw], y = 1ll * w0 * A[nw + M] % P;
A[nw] = (x + y) % P, A[nw + M] = (x - y + P) % P;
w0 = 1ll * w0 * W % P;
}
}
}
return 0;
}
vector<int> convolution(vector<int> a, vector<int> b) {
int n = a.size(), m = b.size();
if (!n || !m)
return {};
int sm = n + m - 1;
int k = 1;
while (k < sm)
k <<= 1;
a.resize(k), b.resize(k);
NTT(a, k);
NTT(b, k);
for (int i = 0; i < k; i ++)
a[i] = 1ll * a[i] * b[i] % P;
NTT(a, k);
reverse(++ a.begin(), a.end());
int invk = Ksm(k, P - 2);
for (int i = 0; i < a.size(); i ++)
a[i] = 1ll * a[i] * invk % P;
a.resize(n + m - 1);
return a;
}
}
namespace solve1 {
int n, A, B;
vector<int> a;
int sum = 0;
int ans, C = 1;
const int modd = 998244353;
using namespace poly;
vector<int> calc(vector<int> &a, int l, int r) {
if (r - l == 1)
return {a[l], 1};
int mid = (l + r) >> 1;
return convolution(calc(a, l, mid), calc(a, mid, r));
}
int main() {
cin >> n >> A >> B;
if(n == 1){
if(A == 1 && B == 1) return cout << 1, 0;
return cout << 0, 0;
}
if(A == 0 || B == 0) return cout << 0, 0;
if (A == 0 || B == 0) return cout << 0, 0;
if(A + B - 1 > n)
return cout << 0, 0;
n --, A --, B --;
int jc1 = 1, jc2 = 1, jc3 = 1;
for (int i = 1; i <= A + B; i ++){
(jc1 *= i) %= P; if(i <= A) (jc2 *= i) %= P;
if(i <= B) (jc3 *= i) %= P;
}
int iv2 = Ksm(jc2, P - 2), iv3 = Ksm(jc3, P - 2);
int ans = (((jc1 * iv2) % modd) * iv3) % modd;
for (int i = 0; i < n; i ++)
a.push_back(i);
vector<int> res = calc(a, 0, n);
cout << ans * res[A + B] % modd;
return 0;
}
}
signed main() {
int T = 1;
while (T --)
solve1::main();
return 0;
}
你说得对，但是我的大常数多项式被同机房的以二分之一常数薄纱。
你说得对，但是我在做完后才知道最后那一坨东西其实是第一类斯特林数。
标签：return,前缀,trn,后缀,题解,最大值,Bandit,int,Blues From： https://www.cnblogs.com/AzusidNya/p/18229655