洛谷 7289 & 7292 「EZEC-5」「KrOI2021」Chasse Neige

发表于 | 分类于 | 11

称满足 πi−1<πi 且 πi>πi+1 的 i 为「极大值」（1<i<n）。

整一个平凡又阴间的 DP……
设 f0/1,0/1(n,k) 分别表示 π1<π2 / π1>π2 且 πn−1<πn / πn−1>πn 的，有 k 个「极大值」的 n 阶排列。

容易观察得到 f0,0=f1,1 且 f0,1(n,k)=f1,0(n,k−1)。

然后开始阴间 DP 转移，对于 f0,0(n,k)，考虑从 n−1 阶排列插入一个 n 得到 n 阶排列。
那么插入在「极大值」左右不会增加极大值，而其他位置都会。
则有 f0,0(n,k)=2kf0,0(n−1,k)+(n−2k−1)f0,0(n−1,k−1)+f0,0(n−1,k)+f0,1(n−1,k)+f1,0(n−1,k−1)

对于 f0,1(n,k)，类似地有 f0,1(n,k)=2kf0,1(n−1,k)+(n−2k)f0,1(n−1,k−1)+f0,0(n−1,k−1)+f1,1(n−1,k−1)

进一步 {f0,1(n,k)=2kf0,1(n−1,k)+(n−2k)f0,1(n−1,k−1)+2f0,0(n−1,k−1)f0,0(n,k)=(2k+1)f0,0(n−1,kj)+(n−2k−1)f0,0(n−1,k−1)+2f0,1(n−1,k)

令 g(n,k)={f0,1(n,k2),k≡0(mod2)f0,0(n,k−12),k≡1(mod2)

于是有 g(n,k)=kg(n−1,k)+(n−k)g(n−1,k−2)+2g(n−1,k−1)

但是你发现这个阴间 DP 是没有前途的。
（但是所以我为什么要写呢？当然是为了膜拜卡老师！）

观察数据可以考虑求 g(n,n−1) 再倒推，因此考虑另一个 DP。
设 fn,gn 分别表示 π1<π2,πn−1>πn 和 π1<π2,πn−1<πn 且有 ⌊n−12⌋ 个「极大值」的排列个数。

DP 式比较显然，快进到 GF： F′=F2+1,G′=FG

这个微分方程比较好解，容易得到 F=tan,G=sec，于是可以得到 {g(n,n−1)} 的生成函数为 F+G=tan+sec，多项式求逆一下就好了。

考虑如何倒推，令 h(n,k)=g(n,n−k)，则 DP 式可以写作 h(n,k)=(n−k)h(n−1,k−1)+kh(n−1,k+1)+2h(n−1,k)

考虑关于 k 改写这个式子 h(n,k+1)=1k[h(n+1,k)−(n−k+1)h(n,k−1)−2h(n,k)]

于是可以直接 O(n(n−2k)) 递推预处理答案。
总复杂度 O(nlogn+n(n−2k))。

比较卡常，我左转这里贴了一份 DIF / DIT，并左转这里学了个常数稍微小一点的求逆……

代码： 

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include <cstdio>
#include <vector>
#include <cstring>
#include <utility>
#include <algorithm>
#define add(a,b) (a + b >= mod ? a + b - mod : a + b)
#define dec(a,b) (a < b ? a - b + mod : a - b)
using namespace std;
const int N = 1e6;
const int LIM = 23;
const int mod = 998244353;
int T,r;
int n,k;
inline int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
namespace Poly
{
    const int LG = 20;
    const int N = 1 << LG + 1;
    const int G = 3;
    int lg2[N + 5];
    int rev[N + 5],fac[N + 5],ifac[N + 5],inv[N + 5];
    int rt[N + 5],irt[N + 5];
    inline void init()
    {
        for(register int i = 2;i <= N;++i)
            lg2[i] = lg2[i >> 1] + 1;
        int w = fpow(G,(mod - 1) / N / 2),wi = fpow(w,mod - 2);
        rt[0] = irt[0] = 1;
        for(register int i = 1;i <= N;++i)
            rt[i] = (long long)rt[i - 1] * w % mod,
            irt[i] = (long long)irt[i - 1] * wi % mod;
        for(register int i = 0;i < N;++i)
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << LG),
            i < rev[i] && (swap(rt[i],rt[rev[i]]),swap(irt[i],irt[rev[i]]),1);
        fac[0] = 1;
        for(register int i = 1;i <= N;++i)
            fac[i] = (long long)fac[i - 1] * i % mod;
        ifac[N] = fpow(fac[N],mod - 2);
        for(register int i = N;i;--i)
            ifac[i - 1] = (long long)ifac[i] * i % mod;
        for(register int i = 1;i <= N;++i)
            inv[i] = (long long)ifac[i] * fac[i - 1] % mod;
    }
    struct poly
    {
        int a[N + 5];
        int len;
        inline poly(int x = 0)
        {
            len = 0;
            x && (a[len++] = x,1);
        }
        inline int operator[](int x) const
        {
            if(x < 0 || x >= len)
                return 0;
            return a[x];
        }
        inline int &operator[](int x)
        {
            return a[x];
        }
        inline void dit()
        {
            int n = len;
            for(register int i = 1,l = n >> 1;i < n;i <<= 1,l >>= 1)
                for(register int j = 0,w,o = 0;j < i;++j,o += l << 1)
                {
                    w = rt[i | j];
                    for(register int k = o,t;k < o + l;++k)
                        t = (long long)a[k + l] * w % mod,
                        a[k + l] = dec(a[k],t),
                        a[k] = add(a[k],t);
                }
        }
        inline void dif()
        {
            int n = len;
            for(register int i = n >> 1,l = 1;i;i >>= 1,l <<= 1)
                for(register int j = 0,w,o = 0;j < i;++j,o += l << 1)
                {
                    w = irt[i | j];
                    for(int k = o,t;k < o + l;++k)
                        t = a[k + l],
                        a[k + l] = dec(a[k],t),a[k + l] = (long long)a[k + l] * w % mod,
                        a[k] = add(a[k],t);
                }
            for(register int i = 0;i < n;++i)
                a[i] = (long long)a[i] * inv[n] % mod;
        }
        inline void ntt(int type = 1)
        {
            type == 1 ? dit() : dif();
        }
        inline void inver(int m)
        {
            poly res(fpow(a[0],mod - 2)),f,g;
            for(register int k = 1;k < m;)
            {
                k <<= 1,f.len = g.len = k;
                memcpy(f.a,a,sizeof(int) * k),memcpy(g.a,res.a,sizeof(int) * k);
                f.ntt(),g.ntt();
                for(register int i = 0;i < k;++i)
                    f[i] = (long long)f[i] * g[i] % mod;
                f.ntt(-1),memset(f.a,0,sizeof(int) * (k >> 1)),f.ntt();
                for(register int i = 0;i < k;++i)
                    f[i] = (long long)f[i] * g[i] % mod;
                f.ntt(-1);
                for(register int i = (k >> 1);i < k;++i)
                    res[i] = dec(0,f[i]);
                res.len = k;
            }
            for(register int i = 0;i < m;++i)
                a[i] = res[i];
            len = m;
        }
        inline void operator*=(poly o)
        {
            int lim = 1,tot = len + o.len - 1;
            for(;lim < tot;lim <<= 1);
            len = o.len = lim;
            ntt(),o.ntt();
            for(register int i = 0;i < lim;++i)
                a[i] = (long long)a[i] * o[i] % mod;
            ntt(-1),len = tot;
        }
    };
}
using Poly::init;
using Poly::poly;
inline int C(int n,int m)
{
    return n < m ? 0 : (long long)Poly::fac[n] * Poly::ifac[m] % mod * Poly::ifac[n - m] % mod;
}
poly f,g;
int h[LIM + 5][N + LIM + 5];
int main()
{
    init();
    scanf("%d%d",&T,&r),r += LIM,f.len = r + 1,g.len = r + 1,f.a[0] = 1;
    for(register int i = 0;2 * i <= r;++i)
        2 * i + 1 <= r && (f.a[2 * i + 1] = i & 1 ? dec(0,Poly::ifac[2 * i + 1]) : Poly::ifac[2 * i + 1]),
        g.a[2 * i] = i & 1 ? dec(0,Poly::ifac[2 * i]) : Poly::ifac[2 * i];
    g.inver(r + 1),f *= g;
    for(register int i = 1;i <= r;++i)
        h[1][i] = (long long)f[i] * Poly::fac[i] % mod;
    for(register int k = 1;k < LIM;++k)
        for(register int i = k + 1;i <= r;++i)
            h[k + 1][i] = ((long long)(i - k + 1) * (k ? h[k - 1][i] : 0) + 2LL * h[k][i] - h[k][i + 1] + mod) % mod * Poly::inv[k] % mod,
            h[k + 1][i] = dec(0,h[k + 1][i]);
    for(;T;--T)
        scanf("%d%d",&n,&k),printf("%d\n",h[n - 2 * k][n]);
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment