CF2127F题解
wrkwrkwrk
·
·
题解
先考虑答案的形式：这个东西很像是 a_n-a_1，但是看到样例发现不对，[2,0,2] 是分段的值，于是答案是每段的 a_n-a_1 之和（n 是段长。）。
考虑最基本的分析：枚举 \text{max}，枚举出现次数得到 + 的和，然后需要知道 - 的和，考虑枚举这样的位置数量，然后考虑 - 的和是啥，这样可以得到一个 O(n^3) 的做法。
我们考虑分析更深层次的东西。考虑之前的东西等价于枚举统计所有的方案求和。但是“和” 里面的东西是可以拆开的。我们发现：
-
每个和都可以写成 \sum f_ia_i 的形式，其中 f_i \in \{-1,0,1\}。
-
答案是 \sum_{A}\sum_{i=1}^n f_{Ai}A_i，可以写成 \sum_{i=1}^n \sum_{f,x} f \cdot x \cdot \sum_{A}[ f_{Ai} = f, A_i = x]，简而言之，就是可以枚举这一项系数和值求有多少个方案是这样的和。
考虑所谓“和” 有啥：+ 和 -。
$a_i$ 是统计到 `-` 的当且仅当 $a_i$ 是某一段的开头，就是 $i=1$ 或者前一项是最大值且 $a_{i-1}=a_n$。注意 $i=n$ 的时候是 $a_{i-1}=a_i$ 且最大。
先算第一项：我们发现本质不同的答案东西是 $=n$ 位置和 $\neq n$ 的位置。考虑枚举这个值是啥，对于 $\neq n$，答案是 $\sum_{i=1}^m i\operatorname{g}(n-2,m-2i,i)$。对于 $=n$ 则是 $\sum_{i=1}^m i\operatorname{g}(n-1,m-i,i)$。其中 $\operatorname{g}(x,y,z)$ 是长度为 $x$ 的序列中最大值不超过 $z$，和为 $y$ 的方案数，通过容斥多少不满足条件的容易知道是：
$$
\sum_{k=0}^{y-k(z+1)\geq 0}\binom n k (-1)^k\binom {y-k(z+1)+x-1} {x-1}
$$
单次计算的运算量是 $\frac y {z+1}$ 的，注意到在上面的求和中这个的和是不超过 $\sum \frac m i$ 就是 $m\log m$ 的，然后是前面 $n-1$ 和最后 $n$ 两次算，因此直接计算即可。
现在考虑 `-` 的贡献，对于第一个数，就是要求最后一个数比它大。枚举最后一个数是啥，这个的式子是：
$$
\sum_{i=1}^m i\sum_{j-i}^{j\leq m-i} \operatorname{g}(n-2,m-i-j,j)
$$
显然不能直接算，展开 $\operatorname{g}$ 得到：
$$
\sum_{i=1}^m i\sum_{j=i}^{j\leq m-i} \sum_{k=0} \binom {n-2} k (-1)^k \binom{m-i-j-k(j+1)+n-3}{n-3}\\
= \sum_{j=0}^{m}\sum_{k=0}^{m-j-k(j+1)\geq 0} \binom {n-2} k (-1)^k \sum_{i=1}^{i\leq \min(j,m-j-k(j+1))} i\binom{m-i-j-k(j+1)+n-3}{n-3}
$$
令
$$
a=\min(j,m-j-k(j+1)),b=m-i-j-k(j+1)+n-3,c=n-3
$$
则变成：
$$
\sum_{j=0}^{m}\sum_{k=0}^{m-j-k(j+1)\geq 0} \binom {n-2} k (-1)^k \operatorname{h}(a,b,c)
$$
其中 $\operatorname{h}$ 是 $\sum_{i=1}^a \binom {b-i} c$，其值为 $(b+1)\bigl[\binom{b}{c+1} - \binom{b-a}{c+1}\bigr]- (c+1)\bigl[\binom{b+1}{c+2} - \binom{b-a+1}{c+2}\bigr]$。[推导细节](https://www.luogu.com.cn/paste/bg0jcocz)。
对于中间位置的数，存在前面的数了也要被算进去，则式子是：
$$
\sum_{i=1}^m i\sum_{j=i}^{j\leq m-i} \operatorname{g}(n-3,m-i-2j,2j)
$$
也可以推导出：
$$
\sum_{j=0}^{m}\sum_{k=0}^{m-2j-k(j+1)\geq 0} \binom {n-3} k (-1)^k \operatorname{h}(a,b,c)
$$
其中 $a=\min(j,m-2j-k(j+1)),b=m-2j-k(j+1)+n-4,c=n-4$。当然别忘了乘以 $n-2$。
最后是最后一个数的和，直接算 $\sum_{i=1}^{\frac m 2} i \operatorname{g}(n-2,m-2i,i)$ 即可。
> 其实题解中提到更好的方法是：注意到两个数相邻的限制是即使不相邻也是这个答案，因此对于所有非最大位置的答案相同，因此求和后除法可行。
>
> 因此可以直接枚举 $a_n$，对于第一个数，答案是 $\sum_{i=1}^m \frac {m-i}{n-1}\operatorname{g}(n-1,m-i,i)$，对于中间项，答案是：$\sum_{i=1}^{\frac m 2} \frac {m-2i}{n-2}\operatorname{g}(n-2,m-2i,i)$。
时间复杂度 $O(m \log m)$，注意可能需要特判 $n=2$，因为可能会算出 $\binom {-1} {-1}=1$ 的组合数。
```cpp
mint g(int n,int y,int z){
mint ans=0;
for(int k=0;y-k*(z+1)>=0;k++){
mint prep=math.binom(n,k)*math.binom(y-k*(z+1)+n-1,n-1);
if(k&1){
ans-=prep;
}else{
ans+=prep;
}
}
return ans;
}
mint f(int a,int b,int c){
//sum i=1^a \binom b-i c
return mint(b+1)*(math.binom(b,c+1)-math.binom(b-a,c+1))-mint(c+1)*(math.binom(b+1,c+2)-math.binom(b-a+1,c+2));
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
if(n==2){
mint ans=0;
for(int a=0;a<=m-a;a++){
ans+=m-a;
ans-=a;
}
cout<<ans<<'\n';
continue;
}
mint ans=0;
for(int i=1;i<=m;i++){
ans+=mint(i)*g(n-1,m-i,i);
}
for(int i=1;i<=m/2;i++){
ans+=mint(i)*g(n-2,m-2*i,i)*mint(n-1);
}
for(int sum=0;sum<=m;sum++){
for(int k=0;m-sum-k*(sum+1)>=0;k++){
mint pc=math.binom(n-2,k);
if(k%2==0)pc=-pc;
int a=min({m-sum,sum,m-sum-k*(sum+1)}),b=m-sum-k*(sum+1)+n-3,c=n-3;
mint wc=f(a,b,c);
ans+=pc*wc;
}
}
for(int sum=0;2*sum<=m;sum++){
for(int k=0;m-2*sum-k*(sum+1)>=0;k++){
mint pc=math.binom(n-3,k)*mint(n-2);
if(k%2==0)pc=-pc;
int a=min({sum,m-2*sum,m-2*sum-k*(sum+1)}),b=m-2*sum-k*(sum+1)+n-4,c=n-4;
mint wc=f(a,b,c);
ans+=pc*wc;
}
}
for(int i=1;2*i<=m;i++){
ans-=mint(i)*g(n-2,m-2*i,i);
}
cout<<ans<<'\n';
}
return 0;
}
```
[AC 记录。](https://codeforces.com/contest/2127/submission/333026192)