题解：CF2127F Hamed and AghaBalaSar
Fa_Nanf1204
·
·
题解
分析
很有意思的计数题。
先看懂伪代码在干什么，注意到相当于是把 a 数组分成若干段，每一个 a_i=a_n 作为一段的最后一个元素，总的贡献就是每段的结尾元素减去开头的元素，转化下就是 a_n 出现的次数乘上 a_n 减去 a_1，再减去所有 a_i=a_n 后面的一个数。
考虑如何计算以上的东西，先考虑一个简化问题，长度为 n 的序列，数的和为 m，每个数要求是非负整数且 \le k，求这样的序列的个数。考虑直接容斥，每次钦定 i 个位置是大于 k 的，此时的方案数就是 \binom{m+n-1-i(k+1)}{n-1}，令 S(n,m,k) 表示此问题的答案，得到：
观察到这个式子跑不满，当 $i(k+1)>m$ 时之后的贡献就都是 $0$ 了，可以发现如果对于每个 $k$ 跑一次这个，就只是个调和级数的复杂度，所以我们可以考虑往这个方向想。
将原问题分成两部分来做，先考虑 $a_n$ 出现的次数乘上 $a_n$，我们枚举一个 $k$ 表示 $a_n$ 的值，感觉直接做不太好做，所以拆贡献，对于每一个位置我们计算他的贡献。
- 对于 $i=n$，贡献为 $S(n-1,m-k,k)$。
- 对于 $i \neq n$，贡献为 $S(n-2,m-2k,k)$。
再来考虑 $a_1$ 和所有 $a_i=a_n$ 后面的一个数的和如何计算，还是对每个位置算贡献。
- 对于 $i=1$，我们发现，除了最后一个位置被钦定为 $k$，其他位置的要求都是一样的，故每个位置所有合法方案下的和都相等，所以贡献为 $\frac{(m-k)S(n-1,m-k,k)}{n-1}$。
- 对于 $2 \le i \le n-1$，它们的前一个位置和最后一个位置钦定为 $k$，所以贡献是 $\frac{(m-2k)S(n-2,m-2k,k)}{n-2}$。
- 对于 $i=n$，它的贡献就是 $kS(n-2,m-2k,k)$。
所以时间复杂度 $O(m \log m)$。
### Code:
```cpp
#include<bits/stdc++.h>
#define N 400005
#define ll long long
using namespace std;
const int mod=1e9+7;
int fac[N],inv_fac[N];
int qpow(int a,int b){
int res=1;
while(b){
if(b&1) res=1ll*res*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return res;
}
int T;
int n,m;
int C(int n,int m){
if(n<m or m<0 or n<0) return 0;
return 1ll*fac[n]*inv_fac[n-m]%mod*inv_fac[m]%mod;
}
int ans=0;
int get(int n,int m,int k){
if(m<0 or n<=0 or k<0 or 1ll*n*k<m) return 0;
int res=0;
for(int i=0;i<=n;i++){
if(m<(k+1)*i) break;
int z=1ll*C(n,i)*C(m+n-1-(k+1)*i,n-1)%mod;
if(i&1) res=(res-z+mod)%mod;
else res=(res+z)%mod;
}
return res;
}
int inv(int x){
return 1ll*inv_fac[x]*fac[x-1]%mod;
}
int res=0;
int main(){
cin>>T;
fac[0]=1;
for(int i=1;i<=N-5;i++){
fac[i]=1ll*fac[i-1]*i%mod;
}
inv_fac[N-5]=qpow(fac[N-5],mod-2);
for(int i=N-6;i>=0;i--){
inv_fac[i]=1ll*inv_fac[i+1]*(i+1)%mod;
}
while(T--){
cin>>n>>m;
ans=0;
res=0;
for(int k=1;k<=m;k++){
int z=0;
int y=get(n-1,m-k,k);
int x=get(n-2,m-2*k,k);
z=(z+y)%mod;
z=(z+1ll*x*(n-1)%mod)%mod;
ans=(ans+1ll*z*k%mod)%mod;
res=(res+1ll*(m-k)*y%mod*inv(n-1)%mod)%mod;
res=(res+1ll*(m-2*k)*x%mod)%mod;
res=(res+1ll*k*x%mod)%mod;
//cout<<1ll*(m-2*k)*x<<'\n';
}
cout<<(ans-res+mod)%mod<<'\n';
}
return 0;
}
```