题意
给出
n
n
n种颜色的球以及它们的个数，把它们排成一排，排列中第
i
i
i种颜色的珠子一定要排在第
i
+
1
i+1
i+1种颜色的最后一个珠子颜色之前，求出排列总数。
思路
按珠子的颜色分别处理。 当前珠子有
x
x
x个，那么除了最后一个，其他的珠子都可以在前面
s
u
m
−
1
sum-1
sum−1个位置中随便排。
代码
#include<cstdio>
#include<algorithm>
#define M 998244353
long long f
[500001], ans
=1;
int n
, x
, sum
;
int power(int a
, int b
) {
int res
= 1;
for (; b
; b
>>= 1) {
if (b
& 1) res
= (long long)res
* a
% M
;
a
= (long long)a
* a
% M
;
}
return res
;
}
int C(int n
, int m
) {
return f
[n
] * power(f
[n
- m
], M
- 2) % M
* power(f
[m
], M
- 2) % M
;
}
int main() {
scanf("%d", &n
);
f
[0] = 1;
for (int i
= 1; i
<= 500000; i
++)
f
[i
] = f
[i
- 1] * i
% 998244353;
for (int i
= 1; i
<= n
; i
++){
scanf("%d", &x
);
sum
+= x
;
ans
= ans
* C(sum
- 1, x
- 1) % M
;
}
printf("%lld\n", ans
);
}
