专栏文章

CF2127F题解

wwrkwrkwrk
CF2127F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miofd0p6
此快照首次捕获于
2025/12/02 18:18
3 个月前
此快照最后确认于
2025/12/02 18:18
3 个月前
查看原文
先考虑答案的形式：这个东西很像是 an−a1a_n-a_1，但是看到样例发现不对，[2,0,2][2,0,2] 是分段的值，于是答案是每段的 an−a1a_n-a_1 之和（nn 是段长。）。
考虑最基本的分析：枚举 max\text{max}，枚举出现次数得到 ++ 的和，然后需要知道 −- 的和，考虑枚举这样的位置数量，然后考虑 −- 的和是啥，这样可以得到一个 O(n3)O(n^3) 的做法。
我们考虑分析更深层次的东西。考虑之前的东西等价于枚举统计所有的方案求和。但是“和” 里面的东西是可以拆开的。我们发现：
  • 每个和都可以写成 ∑fiai\sum f_ia_i 的形式，其中 fi∈{−1,0,1}f_i \in \{-1,0,1\}。
  • 答案是 ∑A∑i=1nfAiAi\sum_{A}\sum_{i=1}^n f_{Ai}A_i，可以写成 ∑i=1n∑f,xf⋅x⋅∑A[fAi=f,Ai=x]\sum_{i=1}^n \sum_{f,x} f \cdot x \cdot \sum_{A}[ f_{Ai} = f, A_i = x]，简而言之，就是可以枚举这一项系数和值求有多少个方案是这样的和。
考虑所谓“和” 有啥：+ 和 -。
aia_i 是统计到 + 的当且仅当 aia_i 是某一段的末尾，就是 aia_i 最大且 ai=ana_i=a_n，这个定义包括 nn。
aia_i 是统计到 - 的当且仅当 aia_i 是某一段的开头，就是 i=1i=1 或者前一项是最大值且 ai−1=ana_{i-1}=a_n。注意 i=ni=n 的时候是 ai−1=aia_{i-1}=a_i 且最大。
先算第一项：我们发现本质不同的答案东西是 =n=n 位置和 ≠n\neq n 的位置。考虑枚举这个值是啥，对于 ≠n\neq n，答案是 ∑i=1mig⁡(n−2,m−2i,i)\sum_{i=1}^m i\operatorname{g}(n-2,m-2i,i)。对于 =n=n 则是 ∑i=1mig⁡(n−1,m−i,i)\sum_{i=1}^m i\operatorname{g}(n-1,m-i,i)。其中 g⁡(x,y,z)\operatorname{g}(x,y,z) 是长度为 xx 的序列中最大值不超过 zz，和为 yy 的方案数，通过容斥多少不满足条件的容易知道是：
∑k=0y−k(z+1)≥0(nk)(−1)k(y−k(z+1)+x−1x−1)\sum_{k=0}^{y-k(z+1)\geq 0}\binom n k (-1)^k\binom {y-k(z+1)+x-1} {x-1}
单次计算的运算量是 yz+1\frac y {z+1} 的，注意到在上面的求和中这个的和是不超过 ∑mi\sum \frac m i 就是 mlog⁡mm\log m 的，然后是前面 n−1n-1 和最后 nn 两次算，因此直接计算即可。
现在考虑 - 的贡献，对于第一个数，就是要求最后一个数比它大。枚举最后一个数是啥，这个的式子是：
∑i=1mi∑j−ij≤m−ig⁡(n−2,m−i−j,j)\sum_{i=1}^m i\sum_{j-i}^{j\leq m-i} \operatorname{g}(n-2,m-i-j,j)
显然不能直接算，展开 g⁡\operatorname{g} 得到：
∑i=1mi∑j=ij≤m−i∑k=0(n−2k)(−1)k(m−i−j−k(j+1)+n−3n−3)=∑j=0m∑k=0m−j−k(j+1)≥0(n−2k)(−1)k∑i=1i≤min⁡(j,m−j−k(j+1))i(m−i−j−k(j+1)+n−3n−3)\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−3a=\min(j,m-j-k(j+1)),b=m-i-j-k(j+1)+n-3,c=n-3
则变成：
∑j=0m∑k=0m−j−k(j+1)≥0(n−2k)(−1)kh⁡(a,b,c)\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)
其中 h⁡\operatorname{h} 是 ∑i=1a(b−ic)\sum_{i=1}^a \binom {b-i} c，其值为 (b+1)[(bc+1)−(b−ac+1)]−(c+1)[(b+1c+2)−(b−a+1c+2)](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]。推导细节。
对于中间位置的数，存在前面的数了也要被算进去，则式子是：
∑i=1mi∑j=ij≤m−ig⁡(n−3,m−i−2j,2j)\sum_{i=1}^m i\sum_{j=i}^{j\leq m-i} \operatorname{g}(n-3,m-i-2j,2j)
也可以推导出：
∑j=0m∑k=0m−2j−k(j+1)≥0(n−3k)(−1)kh⁡(a,b,c)\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−4a=\min(j,m-2j-k(j+1)),b=m-2j-k(j+1)+n-4,c=n-4。当然别忘了乘以 n−2n-2。
最后是最后一个数的和，直接算 ∑i=1m2ig⁡(n−2,m−2i,i)\sum_{i=1}^{\frac m 2} i \operatorname{g}(n-2,m-2i,i) 即可。
其实题解中提到更好的方法是：注意到两个数相邻的限制是即使不相邻也是这个答案，因此对于所有非最大位置的答案相同，因此求和后除法可行。
因此可以直接枚举 ana_n，对于第一个数，答案是 ∑i=1mm−in−1g⁡(n−1,m−i,i)\sum_{i=1}^m \frac {m-i}{n-1}\operatorname{g}(n-1,m-i,i)，对于中间项，答案是：∑i=1m2m−2in−2g⁡(n−2,m−2i,i)\sum_{i=1}^{\frac m 2} \frac {m-2i}{n-2}\operatorname{g}(n-2,m-2i,i)。
时间复杂度 O(mlog⁡m)O(m \log m)，注意可能需要特判 n=2n=2，因为可能会算出 (−1−1)=1\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 记录。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...