CF1528F

其实不难,但是又有懂得都懂的感觉。

某谷的翻译真的鬼畜。

题目大意:

一个合法的序列 Ajn,i=1n[aij]nj+1

给了一个限制 B 序列,要求 ab1=ab2==abk

求这样 (A,B) 的数量和。


首先考虑 A,B 看起来很独立,我们考虑分开计算。

对于 A 的限制我们不妨改变一下。

看成有 n 个人,每个人都选择了一个位置 ai。每个人依次坐其选定的位置,如果这个位置有人了那么就向右坐一个位置。如果 n+1 这个位置没有人,就是合法的。

我们考虑总方案是 (n+1)n 然后对于一个合法位置其经过变换可以得到 n 个不合法的位置。

那么合法的方案就是 (n+1)n1

然后考虑 B 的计数,因为只要满足 ab1=ab2==abk 的限制即可。我们可以任意钦定。

然后我们考虑计算 B 的时候不妨计算所有 A 序列的贡献,之后再 ÷(n+1) 即可。

然后对于一个数相同的情况,总共的数的个数为 n+1 所以应该外面再乘上 n+1 正好抵消。

注意 B 选择了相同的位置也不影响。

容易得到方案。
i=0n(ni)nniik

稍微解释一下:总共只有 n 个数,去枚举哪些数相同,剩下的数随便选即可。后面就是 B 选择的方案了。

然后和 n 有关就不太行。

直接通过斯特林数化简得到。
i=0k{k\i}(ni)i!(n+1)nj
之后发现是一个卷积。

然后斯特林数也是可以使用卷积的,复杂度 O(klogk)
{k\j}=1j!i=0j(ij)(1)j(ij)k
就很一脸卷积样。

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
using namespace std;

//#define Fread
#define Getmod

#ifdef Fread
char buf[1 << 21], *iS, *iT;
#define gc() (iS == iT ? (iT = (iS = buf) + fread (buf, 1, 1 << 21, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
#define getchar gc
#endif // Fread

template <typename T>
void r1(T &x) {
x = 0;
char c(getchar());
int f(1);
for(; c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
for(; '0' <= c && c <= '9';c = getchar()) x = (x * 10) + (c ^ 48);
x *= f;
}

#ifdef Getmod
const int mod = 998244353;
template <int mod>
struct typemod {
int z;
typemod(int a = 0) : z(a) {}
inline int inc(int a,int b) const {return a += b - mod, a + ((a >> 31) & mod);}
inline int dec(int a,int b) const {return a -= b, a + ((a >> 31) & mod);}
inline int mul(int a,int b) const {return 1ll * a * b % mod;}
typemod<mod> operator + (const typemod<mod> &x) const {return typemod(inc(z, x.z));}
typemod<mod> operator - (const typemod<mod> &x) const {return typemod(dec(z, x.z));}
typemod<mod> operator * (const typemod<mod> &x) const {return typemod(mul(z, x.z));}
typemod<mod>& operator += (const typemod<mod> &x) {*this = *this + x; return *this;}
typemod<mod>& operator -= (const typemod<mod> &x) {*this = *this - x; return *this;}
typemod<mod>& operator *= (const typemod<mod> &x) {*this = *this * x; return *this;}
int operator == (const typemod<mod> &x) const {return x.z == z;}
int operator != (const typemod<mod> &x) const {return x.z != z;}
};
typedef typemod<mod> Tm;
#endif
const Tm G = 3, invG = 332748118;
template <typename T,typename... Args> inline void r1(T& t, Args&... args) {
r1(t); r1(args...);
}

//#define int long long
const int maxn = 4e5 + 5;
const int maxm = maxn << 1;

Tm tmp[maxn], Sl[maxn], Sr[maxn], fac[maxn], inv[maxn], C[maxn];
int rev[maxn];
int lim, len;
void getrev(int x) {
lim = 1, len = 0;
while(lim <= x) lim <<= 1, ++ len;
for(int i = 0; i < lim; ++ i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len - 1));
}

Tm ksm(Tm x,int mi) {
if(mi < 0) return 0;
Tm res(1);
while(mi) {
if(mi & 1) res *= x;
mi >>= 1;
x *= x;
}
return res;
}

void NTT(Tm *A,int opt = 1) {
for(int i = 0; i < lim; ++ i) if(i < rev[i]) swap(A[i], A[rev[i]]);
for(int mid = 1; mid < lim; mid <<= 1) {
Tm wn(ksm((opt == 1) ? G : invG, (mod - 1) / (mid << 1)));
for(int j = 0, c = (mid << 1); j < lim; j += c) {
Tm W(1);
for(int k = 0; k < mid; ++ k, W *= wn) {
Tm x = A[j + k], y = W * A[j + k + mid];
A[j + k] = x + y;
A[j + k + mid] = x - y;
}
}
}
if(opt != 1) {
Tm z = ksm(lim, mod - 2);
for(int i = 0; i < lim; ++ i) A[i] *= z;
}
}

int n, k;

signed main() {
// freopen("S.in", "r", stdin);
// freopen("S.out", "w", stdout);
int i, j;
r1(n, k);
Tm vis[2] = {1, mod - 1};
fac[0] = 1;
for(i = 1; i <= k; ++ i) fac[i] = fac[i - 1] * i;
inv[k] = ksm(fac[k], mod - 2);
for(i = k - 1; ~ i; -- i) inv[i] = inv[i + 1] * (i + 1);
for(i = 0; i <= k; ++ i) {
Sl[i] = inv[i] * vis[i & 1];
Sr[i] = ksm(i, k) * inv[i];
}
getrev(2 * k);
// printf("lim = %d\n", lim);
NTT(Sl, 1), NTT(Sr, 1);
for(i = 0; i < lim; ++ i) Sl[i] *= Sr[i];
NTT(Sl, -1);
// printf("s1 = %d\n", Sl[k].z);
Sl[0] = 0;
C[0] = 1;
for(i = 1; i <= k; ++ i) C[i] = C[i - 1] * (n - i + 1) * ksm(i, mod - 2);
// Tm x = ksm(n + 1, n);
// printf("s0 = %d\n", Sl[0].z);
Tm ans(0);
for(i = 0; i <= k; ++ i) ans += C[i] * Sl[i] * fac[i] * ksm(n + 1, n - i);
printf("%d\n", ans.z);
return 0;
}