2023辽宁省赛E
Solution
题目大致分为三个步骤
- 计算 P ( S ) P(S) P(S)
- 证明删除区间连续且找到最值位置
- 根据最值位置求出答案
接下来过程中不合法的组合数都默认为 0 0 0
第 1 步 - 求出总值
考虑 S m = { 1 , 2 , ⋯ , m } S_m = \{1, 2, \cdots, m\} Sm={1,2,⋯,m} , 则有 $P(S_{n+2}) = P(S_{n+1})+P(S_{n}) $
因为
P
(
S
n
)
=
∑
i
=
1
n
(
n
−
i
i
−
1
)
,
P
(
S
n
+
1
)
=
∑
i
=
1
n
+
1
(
n
+
1
−
i
i
−
1
)
,
P
(
S
n
+
2
)
=
∑
i
=
1
n
+
2
(
n
+
2
−
i
i
−
1
)
P(S_n) = \sum_{i=1}^n \binom{n-i}{i-1} \ , \ P(S_{n+1}) = \sum_{i=1}^{n+1} \binom{n+1-i}{i-1} \ , \ P(S_{n+2}) = \sum_{i=1}^{n+2} \binom{n+2-i}{i-1}
P(Sn)=i=1∑n(i−1n−i) , P(Sn+1)=i=1∑n+1(i−1n+1−i) , P(Sn+2)=i=1∑n+2(i−1n+2−i)
利用公式
(
n
m
)
=
(
n
−
1
m
)
+
(
n
−
1
m
−
1
)
\binom{n}{m} = \binom{n-1}{m} + \binom{n-1}{m-1}
(mn)=(mn−1)+(m−1n−1)
可以得到
P
(
S
n
+
2
)
=
∑
i
=
1
n
+
2
(
n
+
2
−
i
i
−
1
)
=
∑
i
=
2
n
+
1
(
n
+
1
−
i
i
−
1
)
+
∑
i
=
2
n
+
1
(
n
+
1
−
i
i
−
2
)
+
(
n
+
2
−
1
0
)
+
(
n
+
2
−
(
n
+
2
)
n
+
2
)
=
∑
i
=
1
n
+
1
(
n
+
1
−
i
i
−
1
)
−
1
+
∑
i
=
1
n
(
n
−
i
i
−
1
)
+
1
=
P
(
S
n
+
1
)
+
P
(
S
n
)
\begin{aligned} P(S_{n+2}) &= \sum_{i=1}^{n+2} \binom{n+2-i}{i-1} \\ &= \sum_{i=2}^{n+1} \binom{n+1-i}{i-1} + \sum_{i=2}^{n+1} \binom{n+1-i}{i-2} + \binom{n+2-1}{0} + \binom{n+2-(n+2)}{n+2} \\ &= \sum_{i=1}^{n+1} \binom{n+1-i}{i-1}-1 +\sum_{i=1}^{n}\binom{n-i}{i-1} + 1 \\ &= P(S_{n+1}) + P(S_n) \end{aligned}
P(Sn+2)=i=1∑n+2(i−1n+2−i)=i=2∑n+1(i−1n+1−i)+i=2∑n+1(i−2n+1−i)+(0n+2−1)+(n+2n+2−(n+2))=i=1∑n+1(i−1n+1−i)−1+i=1∑n(i−1n−i)+1=P(Sn+1)+P(Sn)
其中
P
(
S
1
)
=
1
P(S_1) = 1
P(S1)=1 ,
P
(
S
2
)
=
1
P(S_2) = 1
P(S2)=1 , 所以
P
(
S
n
)
=
f
i
b
(
n
)
P(S_n) = \mathrm{fib}(n)
P(Sn)=fib(n)
或者由恒等式
∑
i
=
0
⌊
n
/
2
⌋
(
n
−
i
i
)
=
f
i
b
(
n
+
1
)
\sum_{i=0}^{\lfloor n/2 \rfloor} \binom{n-i}{i} = \mathrm{fib}(n+1)
i=0∑⌊n/2⌋(in−i)=fib(n+1)
然后
P
(
S
n
)
=
∑
i
=
1
n
(
n
−
i
i
−
1
)
=
∑
i
=
0
n
−
1
(
(
n
−
1
)
−
i
i
)
=
f
i
b
(
n
)
\begin{aligned} P(S_n) &= \sum_{i=1}^n \binom{n-i}{i-1} \\ &= \sum_{i=0}^{n-1} \binom{(n-1)-i}{i} \\ &= \mathrm{fib}(n) \end{aligned}
P(Sn)=i=1∑n(i−1n−i)=i=0∑n−1(i(n−1)−i)=fib(n)
第 2 步 - 证明连续
最为关键的一点是 , 删点顺序不影响答案(我们将所有数当成数轴的点以简化说明) , 所以我们记 F ( x 1 , ⋯ , x r , x ) F(x_1,\cdots,x_r, x) F(x1,⋯,xr,x) 为去掉点 x 1 , ⋯ , x r x_1,\cdots,x_r x1,⋯,xr 后再删掉点 x x x 少的贡献 , 这里我们钦定 x 1 > x 2 > ⋯ > x r > x x_1 > x_2 > \cdots > x_r > x x1>x2>⋯>xr>x
首先考虑仅删除一个点时少掉的贡献 , 假设删除的位置是
x
x
x , 有
F
(
x
)
=
(
n
−
x
x
−
1
)
+
∑
i
=
1
x
−
1
(
n
−
i
−
1
i
−
2
)
F(x) = \binom{n-x}{x-1} + \sum_{i=1}^{x-1} \binom{n-i-1}{i-2}
F(x)=(x−1n−x)+i=1∑x−1(i−2n−i−1)
我们尝试找一找
F
(
x
)
F(x)
F(x) 的最值点(如果只删掉一个点肯定是越大越好) , 有
F
(
x
+
1
)
−
F
(
x
)
=
(
n
−
x
−
1
x
)
−
(
n
−
x
x
−
1
)
+
(
n
−
x
−
1
x
−
2
)
=
(
n
−
x
−
1
x
)
−
(
n
−
x
−
1
x
−
1
)
−
(
n
−
x
−
1
x
−
2
)
+
(
n
−
x
−
1
x
−
2
)
=
(
n
−
x
−
1
x
)
−
(
n
−
x
−
1
x
−
1
)
\begin{aligned} F(x+1) - F(x) &= \binom{n-x-1}{x} - \binom{n-x}{x-1} + \binom{n-x-1}{x-2} \\ &= \binom{n-x-1}{x} - \binom{n-x-1}{x-1} - \binom{n-x-1}{x-2} + \binom{n-x-1}{x-2} \\ &= \binom{n-x-1}{x} - \binom{n-x-1}{x-1} \end{aligned}
F(x+1)−F(x)=(xn−x−1)−(x−1n−x)+(x−2n−x−1)=(xn−x−1)−(x−1n−x−1)−(x−2n−x−1)+(x−2n−x−1)=(xn−x−1)−(x−1n−x−1)
可以发现
F
(
x
)
F(x)
F(x) 是先增后减的单峰函数(最值点唯一或相邻两个) , 且最值点位置关系有
⌈
n
−
x
′
−
1
2
⌉
=
x
′
o
r
⌊
n
−
x
′
−
1
2
⌋
=
x
′
\lceil \cfrac{n-x'-1}{2} \rceil = x' \ or \ \lfloor \cfrac{n-x'-1}{2} \rfloor = x'
⌈2n−x′−1⌉=x′ or ⌊2n−x′−1⌋=x′
现在我们考虑删除两个点时的情况 , 我们来考虑
F
(
x
1
,
x
)
F(x_1,x)
F(x1,x) 的最值点(不一定能取到) , 有
F
(
x
1
,
x
)
=
(
(
n
−
1
)
−
x
x
−
1
)
+
∑
i
=
1
x
−
1
(
(
n
−
1
)
−
i
−
1
i
−
2
)
F(x_1,x) = \binom{(n-1)-x}{x-1} + \sum_{i=1}^{x-1} \binom{(n-1)-i-1}{i-2}
F(x1,x)=(x−1(n−1)−x)+i=1∑x−1(i−2(n−1)−i−1)
(因为删除
x
1
x_1
x1 对删除
x
x
x 的影响一定是"比
i
i
i (
1
≤
i
≤
x
1
−
1
1 \leq i \leq x_1-1
1≤i≤x1−1) 大的数少了一个")
有一种更感性的理解方法 , 因为 x < x 1 x < x_1 x<x1 所以我们可以将 x 1 + 1 x_1+1 x1+1 到 n n n 重标号为 x 1 x_1 x1 到 n − 1 n-1 n−1 , 问题就转化为了从 1 1 1 到 n − 1 n-1 n−1 的子问题
类比之前的求法可以得到
F
(
x
1
,
x
)
F(x_1,x)
F(x1,x) 的最值点位置关系有
⌈
(
n
−
1
)
−
x
′
−
1
2
⌉
=
x
′
o
r
⌊
(
n
−
1
)
−
x
′
−
1
2
⌋
=
x
′
\lceil \cfrac{(n-1)-x'-1}{2} \rceil = x' \ or \ \lfloor \cfrac{(n-1)-x'-1}{2} \rfloor = x'
⌈2(n−1)−x′−1⌉=x′ or ⌊2(n−1)−x′−1⌋=x′
依此类推 , 可以证明
F
(
x
1
,
⋯
,
x
k
−
1
,
x
)
F(x_1, \cdots, x_{k-1}, x)
F(x1,⋯,xk−1,x) 的最值点位置关系有
⌈
(
n
−
k
)
−
x
k
′
2
⌉
=
x
k
′
o
r
⌊
(
n
−
k
)
−
x
k
′
2
⌋
=
x
k
′
\lceil \cfrac{(n-k)-x'_k}{2} \rceil = x'_k \ or \ \lfloor \cfrac{(n-k)-x'_k}{2} \rfloor = x'_k
⌈2(n−k)−xk′⌉=xk′ or ⌊2(n−k)−xk′⌋=xk′
去掉取整符号可以得到
(
n
−
k
)
−
1
≤
3
x
k
′
≤
(
n
−
k
)
+
1
(n-k)-1 \leq 3x'_k \leq (n-k)+1
(n−k)−1≤3xk′≤(n−k)+1
这说明
−
1
≤
x
k
+
1
′
−
x
k
′
≤
0
-1 \leq x_{k+1}'- x_k' \leq 0
−1≤xk+1′−xk′≤0
接下来我们要证明删除序列为连续的一段
假定目前已经删除了 r r r 个点 , 且删的第 r r r 个点满足 x r ≤ x r ′ x_r \leq x_r' xr≤xr′ , 由上面不等式有 x r + 1 ′ = x r ′ x'_{r+1} = x'_r xr+1′=xr′ 或者 x r + 1 ′ = x r ′ − 1 x'_{r+1}=x'_r-1 xr+1′=xr′−1
由前论 F F F 的性质 , 可知 x r + 1 = x r − 1 x_{r+1} = x_r-1 xr+1=xr−1 时 F ( x 1 , ⋯ , x r + 1 ) F(x_1,\cdots,x_{r+1}) F(x1,⋯,xr+1) 最大 , 归纳可得 x r , ⋯ , x m x_r,\cdots, x_m xr,⋯,xm 连续
我们不妨假设第 k k k 次删除的点是第一个满足 x k = x k ′ x_k = x'_k xk=xk′ 的 , 即它是第一个删除点等于对应最值点的
有 x k ′ < x k − 1 < ⋯ < x 1 x'_k < x_{k-1} < \cdots < x_1 xk′<xk−1<⋯<x1 , 考虑 F ( x ) , F ( x 1 , x ) , ⋯ , F ( x 1 , ⋯ , x k − 2 , x ) F(x), F(x_1,x) ,\cdots , F(x_1,\cdots,x_{k-2},x) F(x),F(x1,x),⋯,F(x1,⋯,xk−2,x)
可以发现在 x k ′ < x k − 1 x'_k<x_{k-1} xk′<xk−1 的限制下根据最值点的不等式 , F ( x 1 , ⋯ , x k − 2 , x ) F(x_1,\cdots,x_{k-2},x) F(x1,⋯,xk−2,x) 可以取到的最大值点一定为 x k ′ + 1 x'_k+1 xk′+1
同理可得 x i = x k ′ + ( k − i ) x_i = x'_k + (k-i) xi=xk′+(k−i) , 这说明 x 1 , ⋯ , x k x_1,\cdots,x_k x1,⋯,xk 连续
如果不存在这样的 k k k , 那么可以分为两种情况
- 对于所有的 x i x_i xi , 要么 x i < x i ′ x_i < x'_i xi<xi′ 要么 x i > x i ′ x_i > x'_i xi>xi′
- 存在 k k k 使得 x k > x k ′ x_k > x'_k xk>xk′ 且 x k + 1 < x k + 1 ′ x_{k+1} < x'_{k+1} xk+1<xk+1′
对于情况 1 , 将 x m x_m xm 或 x 1 x_1 x1 移动到最值点处会更优
对于情况 2 , 将 x k + 1 x_{k+1} xk+1 移动到其最值点上会更优
这说明了最优解的删除方法至少有一次满足 x k = x k ′ x_k = x'_k xk=xk′ , 这样的 k k k 必定存在
综上 , 删除区间连续
这部分简单地说 , 就是如果将删除的数定序为从大到小 , 那么删一个点后减掉的贡献只和前面删数的数量相关(当然要考虑最值点的位置) , 而又由于最值点之间相距很近 , 所以删除序列连续
第三步 - 求出贡献
现在不妨假设我们删了 l l l 到 r r r , 现在我们来寻找使得答案最小的 l l l 和 r r r
我们从最后的答案
P
(
S
′
)
P(S')
P(S′) 来分析 , 则最小的
P
(
S
l
,
r
)
P(S_{l,r})
P(Sl,r) (
S
S
S 删除
l
l
l 到
r
r
r 的数) 对应我们所要的
l
l
l 和
r
r
r
P
(
S
l
,
r
)
=
∑
i
=
1
l
−
1
(
n
−
(
r
−
l
+
1
)
−
i
i
−
1
)
+
∑
i
=
r
+
1
n
(
n
−
i
i
−
1
)
P(S_{l,r}) = \sum_{i=1}^{l-1} \binom{n-(r-l+1)-i}{i-1} + \sum_{i=r+1}^n \binom{n-i}{i-1}
P(Sl,r)=i=1∑l−1(i−1n−(r−l+1)−i)+i=r+1∑n(i−1n−i)
依旧做差
P
(
S
l
+
1
,
r
+
1
)
−
P
(
S
l
,
r
)
=
∑
i
=
1
l
(
n
−
(
r
−
l
+
1
)
−
i
i
−
1
)
+
∑
i
=
r
+
2
n
(
n
−
i
i
−
1
)
−
∑
i
=
1
l
−
1
(
n
−
(
r
−
l
+
1
)
−
i
i
−
1
)
−
∑
i
=
r
+
1
n
(
n
−
i
i
−
1
)
=
(
n
−
(
r
−
l
+
1
)
−
l
l
−
1
)
−
(
n
−
r
−
1
r
)
=
(
n
−
r
−
1
l
−
1
)
−
(
n
−
r
−
1
r
)
\begin{aligned} P(S_{l+1,r+1}) -P(S_{l,r}) &= \sum_{i=1}^{l} \binom{n-(r-l+1)-i}{i-1} + \sum_{i=r+2}^n \binom{n-i}{i-1} - \sum_{i=1}^{l-1} \binom{n-(r-l+1)-i}{i-1} - \sum_{i=r+1}^n \binom{n-i}{i-1} \\ &= \binom{n-(r-l+1)-l}{l-1} - \binom{n-r-1}{r} \\ &= \binom{n-r-1}{l-1} - \binom{n-r-1}{r} \end{aligned}
P(Sl+1,r+1)−P(Sl,r)=i=1∑l(i−1n−(r−l+1)−i)+i=r+2∑n(i−1n−i)−i=1∑l−1(i−1n−(r−l+1)−i)−i=r+1∑n(i−1n−i)=(l−1n−(r−l+1)−l)−(rn−r−1)=(l−1n−r−1)−(rn−r−1)
可以通过分析得到
P
(
S
l
,
r
)
P(S_{l,r})
P(Sl,r) 是单峰函数且最小值点要么有一个 , 要么有相邻的两个 , 且有
r
=
n
+
m
−
1
3
r = \frac{n+m-1}{3}
r=3n+m−1
这样我们就确定了删除的范围
l
l
l ,
r
r
r (
r
≥
m
r \geq m
r≥m)
接下来我们来计算
P
(
S
l
,
r
)
m
o
d
p
P(S_{l,r}) \ \mathrm{mod}\ p
P(Sl,r) mod p , 观察式子 , 实际上我们要计算的是
f
(
a
,
n
)
=
∑
i
=
0
a
(
n
−
i
i
)
m
o
d
p
f(a,n) = \sum_{i=0}^{a} \binom{n-i}{i} \ \mathrm{mod} \ p
f(a,n)=i=0∑a(in−i) mod p
若
n
≤
p
n \leq p
n≤p , 则上式可以在预处理后暴力计算 , 复杂度
Θ
(
p
)
\Theta(p)
Θ(p) , 以下假定
n
>
p
n > p
n>p
根据 Lucas 定理稍作变换
f
(
a
,
n
)
=
∑
i
=
0
a
(
n
−
i
i
)
m
o
d
p
=
∑
i
=
0
a
(
⌊
(
n
−
i
)
/
p
⌋
⌊
i
/
p
⌋
)
(
(
n
−
i
)
%
p
i
%
p
)
m
o
d
p
=
∑
i
=
0
p
−
1
(
(
n
−
i
)
%
p
i
)
∑
j
=
0
⌊
a
/
p
⌋
−
1
(
⌊
(
n
−
i
)
/
p
⌋
−
j
j
)
+
∑
i
=
0
a
%
p
(
(
n
−
i
)
%
p
i
)
(
⌊
(
n
−
i
)
/
p
⌋
−
⌊
a
/
p
⌋
⌊
a
/
p
⌋
)
m
o
d
p
=
g
(
a
,
n
)
+
h
(
a
,
n
)
\begin{aligned} f(a,n) &= \sum_{i=0}^{a} \binom{n-i}{i} \ \mathrm{mod} \ p \\ &= \sum_{i=0}^{a} \binom{\lfloor (n-i)/p \rfloor}{\lfloor i/p \rfloor} \binom{(n-i) \% p}{i \% p} \ \mathrm{mod} \ p \\ &= \sum_{i=0}^{p-1} \binom{(n-i) \% p}{i} \sum_{j=0}^{\lfloor a/p \rfloor-1} \binom{\lfloor (n-i)/p \rfloor-j}{j} + \sum_{i=0}^{a\%p} \binom{(n-i) \% p}{i}\binom{\lfloor (n-i)/p \rfloor-\lfloor a/p \rfloor}{\lfloor a/p \rfloor} \ \mathrm{mod} \ p \\ &= g(a,n)+ h(a,n) \end{aligned}
f(a,n)=i=0∑a(in−i) mod p=i=0∑a(⌊i/p⌋⌊(n−i)/p⌋)(i%p(n−i)%p) mod p=i=0∑p−1(i(n−i)%p)j=0∑⌊a/p⌋−1(j⌊(n−i)/p⌋−j)+i=0∑a%p(i(n−i)%p)(⌊a/p⌋⌊(n−i)/p⌋−⌊a/p⌋) mod p=g(a,n)+h(a,n)
因为
⌊
(
n
−
i
)
/
p
⌋
\lfloor (n-i)/p \rfloor
⌊(n−i)/p⌋ 只会在
i
=
n
%
p
i=n\%p
i=n%p 到
i
=
n
%
p
+
1
i=n\%p+1
i=n%p+1 内变一次 , 所以我们可以将
g
(
a
,
n
)
g(a,n)
g(a,n) 拆分
g
(
a
,
n
)
=
∑
i
=
0
p
−
1
(
(
n
−
i
)
%
p
i
)
∑
j
=
0
⌊
a
/
p
⌋
−
1
(
⌊
(
n
−
i
)
/
p
⌋
−
j
j
)
m
o
d
p
=
[
∑
i
=
0
n
%
p
(
n
%
p
−
i
i
)
+
∑
i
=
n
%
p
+
1
p
−
1
(
n
%
p
+
p
−
i
i
)
]
∑
j
=
0
⌊
a
/
p
⌋
−
1
(
⌊
(
n
−
i
)
/
p
⌋
−
j
j
)
m
o
d
p
=
∑
i
=
0
n
%
p
(
n
%
p
−
i
i
)
∑
j
=
0
⌊
a
/
p
⌋
−
1
(
⌊
n
/
p
⌋
−
j
j
)
+
∑
i
=
n
%
p
+
1
p
−
1
(
n
%
p
+
p
−
i
i
)
∑
j
=
0
⌊
a
/
p
⌋
−
1
(
⌊
n
/
p
⌋
−
1
−
j
j
)
m
o
d
p
=
f
(
n
%
p
,
n
%
p
)
f
(
⌊
a
/
p
⌋
−
1
,
⌊
n
/
p
⌋
)
+
[
f
(
p
−
1
,
n
%
p
+
p
)
−
f
(
n
%
p
,
n
%
p
+
p
)
]
f
(
⌊
a
/
p
⌋
−
1
,
⌊
n
/
p
⌋
−
1
)
m
o
d
p
\begin{aligned} g(a,n) &= \sum_{i=0}^{p-1} \binom{(n-i) \% p}{i} \sum_{j=0}^{\lfloor a/p \rfloor-1} \binom{\lfloor (n-i)/p \rfloor-j}{j}\ \mathrm{mod} \ p \\ &= \left[ \sum_{i=0}^{n\%p}\binom{n\% p - i}{i} + \sum_{i=n\%p+1}^{p-1}\binom{n\% p + p - i}{i} \right] \sum_{j=0}^{\lfloor a/p \rfloor-1} \binom{\lfloor (n-i)/p \rfloor-j}{j}\ \mathrm{mod} \ p \\ &= \sum_{i=0}^{n\%p}\binom{n\% p - i}{i}\sum_{j=0}^{\lfloor a/p \rfloor-1} \binom{\lfloor n/p \rfloor-j}{j}\ + \sum_{i=n\%p+1}^{p-1}\binom{n\% p + p - i}{i} \sum_{j=0}^{\lfloor a/p \rfloor-1} \binom{\lfloor n/p \rfloor-1-j}{j}\ \mathrm{mod} \ p \\ &= f(n\%p, n\%p)f(\lfloor a/p \rfloor-1, \lfloor n/p \rfloor) +\\ &\ \ \ \ \left[ f(p-1,n\%p+p)-f(n\%p,n\%p+p) \right] f(\lfloor a/p \rfloor-1, \lfloor n/p \rfloor-1)\ \mathrm{mod} \ p \\ \end{aligned}
g(a,n)=i=0∑p−1(i(n−i)%p)j=0∑⌊a/p⌋−1(j⌊(n−i)/p⌋−j) mod p=
i=0∑n%p(in%p−i)+i=n%p+1∑p−1(in%p+p−i)
j=0∑⌊a/p⌋−1(j⌊(n−i)/p⌋−j) mod p=i=0∑n%p(in%p−i)j=0∑⌊a/p⌋−1(j⌊n/p⌋−j) +i=n%p+1∑p−1(in%p+p−i)j=0∑⌊a/p⌋−1(j⌊n/p⌋−1−j) mod p=f(n%p,n%p)f(⌊a/p⌋−1,⌊n/p⌋)+ [f(p−1,n%p+p)−f(n%p,n%p+p)]f(⌊a/p⌋−1,⌊n/p⌋−1) mod p
令
T
(
n
)
T(n)
T(n) 代表计算
f
(
a
,
n
)
f(a,n)
f(a,n) 的复杂度上界 , 计算
h
(
a
,
n
)
h(a,n)
h(a,n) 的复杂度为
p
log
n
<
2
C
p \log n < 2C
plogn<2C , 则有
T
(
n
)
=
2
∗
T
(
n
/
p
)
+
2
C
T(n) = 2*T(n/p) + 2C
T(n)=2∗T(n/p)+2C
其中
T
(
1
)
=
1
T(1)=1
T(1)=1 , 令
m
=
log
p
n
m = \log_p n
m=logpn 则有
T
′
(
m
)
=
2
∗
T
′
(
m
−
1
)
+
2
C
T'(m) = 2*T'(m-1) + 2C
T′(m)=2∗T′(m−1)+2C
推得
T
′
(
m
)
=
2
m
×
2
C
T'(m) = 2^m \times 2C
T′(m)=2m×2C
所以
T
(
n
)
=
2
log
p
n
×
2
C
=
n
log
p
2
×
2
C
=
n
log
p
2
×
2
p
log
n
T(n) = 2^{\log_pn} \times 2C = n^{\log_p 2} \times 2C = n^{\log_p 2} \times 2p \log n
T(n)=2logpn×2C=nlogp2×2C=nlogp2×2plogn
当
p
>
2
p > 2
p>2 时复杂度满足要求
当 p = 2 p=2 p=2 时 , 发现 g ( a , n ) g(a,n) g(a,n) 中 [ f ( p − 1 , n % p + p ) − f ( n % p , n % p + p ) ] \left[ f(p-1,n\%p+p)-f(n\%p,n\%p+p) \right] [f(p−1,n%p+p)−f(n%p,n%p+p)] 在 n n n 为奇数情况下为 0 0 0
而对 g ( a , n ) g(a,n) g(a,n) 的一次拆分必定将 n n n 分成一奇一偶 , 所以最后 [ f ( p − 1 , n % p + p ) − f ( n % p , n % p + p ) ] \left[ f(p-1,n\%p+p)-f(n\%p,n\%p+p) \right] [f(p−1,n%p+p)−f(n%p,n%p+p)] 不为 0 0 0 的点的个数至多等于长度小于等于 log n \log n logn 的 01 串中不含有连续两个 1 作为子串的方案数 , 计算可以得到数量级为 f i b ( log n + 4 ) \mathrm{fib}(\log n+4) fib(logn+4) , 在题中所给数据限制下 f i b ( log n + 4 ) ≤ f i b ( 34 ) < 1 0 7 \mathrm{fib}(\log n+4) \leq \mathrm{fib}(34) < 10^7 fib(logn+4)≤fib(34)<107 , 复杂度满足
于是按如下式子计算
P
(
S
l
,
r
)
=
f
(
l
−
2
,
n
−
m
−
1
)
+
f
(
n
−
1
,
n
−
1
)
−
f
(
r
−
1
,
n
−
1
)
P(S_{l,r}) = f(l-2,n-m-1) + f(n-1,n-1) - f(r-1,n-1)
P(Sl,r)=f(l−2,n−m−1)+f(n−1,n−1)−f(r−1,n−1)
其中
f
(
n
−
1
,
n
−
1
)
=
f
i
b
(
n
)
f(n-1,n-1) = \mathrm{fib}(n)
f(n−1,n−1)=fib(n)