链接
https://ac.nowcoder.com/acm/contest/9985/B
题意
给定 $n,m$，定义一种序列，构造方法如下：
- 在 $[1,n]$ 中任意选择 $m$ 次，得到了 $m$ 个整数（显然数字可能相同）;
- 将选出的 $m$ 个数字排序之后得到一个序列 ${ a_{1},a_{2},…,a_{m} }$
定义一个序列的贡献为 $\max{ a_{1},a_{2},…,a_{m} }-\min{ a_{1},a_{2},…,a_{m} }$，求所有不同的序列的贡献和。
思路
本题顺序不同元素相同的序列是等价的，所以直接考虑非降序列。
枚举差值 $d$，最小数有 $n-d$ 种取法，考虑查分序列。
我们要求的是从$0\sim d$ 中选出 $m-1$个数（可相同），使差分序列前缀和等于 $d$ 的方案数 ，
即将 $d$ 个相同的球放入 $m-1$ 个不同的盒子，并允许空盒子的方案数 ，
等价于将 $d+m-1$ 个相同的球放入 $m-1$ 个不同的盒子，不允许空盒子的方案数 ，
所以 $f(d,m-1)=\binom{d+m-2}{m-2}$，$res=\sum_{d=0}^{n-1}{d*(n-d)*f(d,m-1)}$。
代码
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
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const LL MOD=998244353;
const int N=1e6+5;
LL fac[N],invfac[N];
LL qpow(LL a,LL b) {
LL ret=1;
while(b) {
if(b&1) ret=ret*a%MOD;
a=a*a%MOD;
b>>=1;
}
return ret;
}
void init_invfac(int n) {
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
invfac[n]=qpow(fac[n],MOD-2);
for(int i=n-1;~i;i--) invfac[i]=invfac[i+1]*(i+1)%MOD;
}
LL C(int a,int b) {
return fac[a]*invfac[b]%MOD*invfac[a-b]%MOD;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
init_invfac(n+m);
LL res=0;
for(int i=0;i<n;i++) res=(res+(n-i)*i%MOD*C(i+m-2,m-2)%MOD)%MOD;
cout<<res<<'\n';
return 0;
}
|