正题
题目大意
n
n
n个颜色第
i
i
i个个数为
n
u
m
i
num_i
numi个，然后要求第
i
i
i种颜色的最后一个一定在第
i
+
1
i+1
i+1种的最后一个前面。求方案总数。
解题思路
首先先定义一个
1
∼
n
1\sim n
1∼n的序列，然后依次将剩下的数插入。
第
i
i
i个颜色有
z
=
(
∑
j
=
1
i
−
1
n
u
m
j
)
+
1
z=(\sum_{j=1}^{i-1}num_j)+1
z=(∑j=1i−1numj)+1个位置。那么方案数就是
C
z
+
n
u
m
i
−
1
z
−
1
C_{z+num_{i}-1}^{z-1}
Cz+numi−1z−1
那么答案就是
∑
i
=
1
n
C
z
+
n
u
m
i
−
1
z
−
1
(
z
=
(
∑
j
=
1
i
−
1
n
u
m
j
)
+
1
)
\sum_{i=1}^n C_{z+num_{i}-1}^{z-1}(z=(\sum_{j=1}^{i-1}num_j)+1)
i=1∑nCz+numi−1z−1(z=(j=1∑i−1numj)+1)
c
o
d
e
code
code
#include<cstdio>
#define ll long long
using namespace std
;
const ll XJQ
=998244353,N
=600100;
ll n
,z
,ans
,jc
[N
],jcinv
[N
];
ll
power(ll x
,ll b
)
{
ll ans
=1;
while(b
){
if(b
&1) ans
=ans
*x
%XJQ
;
b
>>=1;x
=x
*x
%XJQ
;
}
return ans
;
}
ll
C(ll n
,ll m
)
{return jc
[n
]*jcinv
[m
]%XJQ
*jcinv
[n
-m
]%XJQ
;}
int main()
{
jc
[0]=1;jcinv
[0]=1;
for(ll i
=1;i
<=600000;i
++)
{
jc
[i
]=jc
[i
-1]*i
%XJQ
;
jcinv
[i
]=power(jc
[i
],XJQ
-2);
}
scanf("%lld",&n
);z
=ans
=1;
for(ll i
=1;i
<=n
;i
++)
{
ll num
;
scanf("%lld",&num
);num
--;
(ans
*=C(num
+z
-1,z
-1))%=XJQ
;
z
+=num
+1;
}
printf("%lld",ans
);
}
