Loading [MathJax]/jax/output/HTML-CSS/jax.js

LibreOJ 6731 「2019 山东一轮集训 Day3」小孩召开法

ak(n) 为答案。
为了导出递推式,我们考虑一下原问题。

注意到必然至少存在一个最长交替子序列经过最大值 n,于是考虑枚举 n 的位置为 i
然后首先要从 n1 个数中选择 i1 个放到左边。
接下来考虑两边分配的交替子序列长度。枚举 2r+1+s=k,那么左边可以有 2r2r+1 的交替子序列(因为 n 可以替换掉 2r+1 处的),右边可以有 s 的交替子序列。
因此 fk(n)=ni=1(n1i1)2r+s=k1(f2r(i1)+f2r+1(i1))fs(ni)

设 BGF F(x,t)=fk(n)xnn!tkF0(x,t)=f2k(n)xnn!t2kF1(x,t)=f2k+1(n)xnn!t2k+1
那么根据如上递推式,我们有 Fx=(tF0+F1)FF0x=(tF0+F1)F1F1x=(tF0+F1)F2

然后注意到 (F20F21)x=F20xF21x=0

这样对于 F20F21,我们只需要对照常数。而根据定义仅有 F0x0 处有 1,因此 F20F21=1=(12(F(x,t)+F(x,t)))2(12(F(x,t)F(x,t))2=F(x,t)F(x,t)

Fx=(tF0+F1)F=12((t+1)F+(t1)F1)FF((t+1)F+(t1)F1)F=x2

G=F1t,则 F=(1t)G。代入得 G(1t2)G21=x2

α=1t2,我们作部分分式分解,就有 (αG)(1αG11αG+1)=αxlnαG1αG+1=αx+CαG1αG+1=eαx+C=eαxCG=1+Ceαxα(1Ceαx)

其中 C,C=eC 关于 x 都是常数。
然后注意到 B(0,t)=11t,因此 C=α1t1α1t+1=1αt

因此 G=1α(21Ceαx1)=1α(211αteαx1)

我们显然可以不管 [x0],接下来尝试提取其系数 2α(11αteαx)1=2αr(1αteαx)r=2αr(1αt)rs(rαx)ss!=2rtrs(rx)ss!(1α)rαs1

在出题人给出的标准做法中,这里凑出了一个有趣的形式,然后利用具体数学中提到的恒等式来辅助推导,但未免太过匪夷所思,这里展示一种更暴力却也更自然的做法(虽然最后推得的结果形式也不尽相同)。

我们想要展开 (11t2)r(1t2)(s1)/2

不妨作换元,令 4x=t2,则 t24=x,且原式变为 (114x)r(14x)(s1)/2

F 满足二叉树方程 F=x(1+F)2 就有熟知结论 F=12x14x2x,x=F(1+F)2

我们把原式整理成复合形式 (114x)r(14x)(s1)/2=(2x(1+F))r(12x2xF)s1=2rxr(1+F)r(12x(1+F))s1=2rFr(1F)s1(1+F)rs+1

然后使用另类拉格朗日反演提取系数 [xn]Fr(1F)r1(1+F)rs+1=[xn]xr(1x)r1(1+x)rs+11x(1+x)3(1+x)2n+2=[xn]xr(1x)r(1+x)2nrs=i(1)i(ri)(2nrsnri)

代回到原式,就有 =2rtrs(rx)ss!2rl(t24)li(1)i(si)(2lrslri)=2rtrs(rx)ss!2ru(t24)r+ui(1)i(si)(r+2usui)=r,s,u21r2utr+2u(rx)ss!i(1)i(si)(r+2usui)

则令 n=s,k=r+2u,便知 gk(n)=21k2i+rk,rk(mod2)rn(1)i(ni)(knkr2i)

枚举 r,则需要计算形如 ft=i(1)i(ni)(sti)

的数列。
考虑其生成函数,显然其为 F(x)=(1+x)s(1x)n

求导 F=sF1+xnF1x

tft=(n+s)ft1+(sn+t2)ft2

时间复杂度 O(klogkn)

感觉这题有意思的地方主要在于最前面的 DP 和微分方程部分,以及后面的提取系数部分。
由于这个题很明显是先想题意再想做法的,所以想复刻这种做法的题目还是比较无从下手(好像暴露了啥

代码:

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
#include <cstdio>
#include <cstring>
using namespace std;
const int K = 1e6;
const int mod = 998244353;
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;
}
long long n;
int k;
int ans;
int inv[K + 5];
int vis[K + 5],cnt,prime[K + 5],pw[K + 5];
int f[K + 5];
int get(long long n,int k)
{
if(k <= 0)
return 0;
int ret = 0;
int s = (n - k) % mod;
f[0] = 1;
for(register int t = 1;t <= (k >> 1);++t)
f[t] = ((2 * mod - n % mod - s) % mod * f[t - 1] + (s + t - n % mod - 2 + mod) % mod * (t >= 2 ? f[t - 2] : 0)) % mod,
f[t] = (long long)inv[t] * f[t] % mod;
for(register int r = k;r >= 0;r -= 2)
ret = (ret + (long long)pw[r] * f[k - r >> 1]) % mod;
ret = (long long)ret * fpow(2,(mod - k) % (mod - 1)) % mod;
return ret;
}
int main()
{
scanf("%lld%d",&n,&k);
pw[1] = 1;
for(register int i = 2;i <= k;++i)
{
if(!vis[i])
pw[i] = fpow(i,n % (mod - 1));
for(register int j = 1;j <= cnt && i * prime[j] <= k;++j)
{
vis[i * prime[j]] = 1,pw[i * prime[j]] = (long long)pw[i] * pw[prime[j]] % mod;
if(!(i % prime[j]))
break;
}
}
inv[1] = 1;
for(register int i = 2;i <= (k >> 1);++i)
inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
ans = (get(n,k) - get(n,k - 1) + mod) % mod;
printf("%d\n",ans);
}

0 comments
Anonymous
Markdown is supported

Be the first person to leave a comment!