【JZOJ4786】小a的强迫症【数论，数学】

题目大意：

题目链接：https://jzoj.net/senior/#main/show/4786
有$n$n种珠子，要求把这些珠子放在一条直线上，且第$i$i种珠子的最后一个的位置$last_i$lasti​满足$last_1&lt;last_2&lt;...&lt;last_n$last1​<last2​<...<lastn​。求满足要求的方案数。

---

思路：

假设我们求完了前$i$i种珠子按要求摆放的方案数，现在要求第$i+1$i+1种珠子的方案数。
设$sum[i-1]$sum[i−1]表示前$i-1$i−1种珠子的总个数，那么第$i$i种珠子的最后一个就应该放在这$sum[i-1]$sum[i−1]个珠子后面，剩余的第$i$i种珠子就应该全部放在这颗珠子的前面。

那么如果总共有$a[i]$a[i]个第$i$i种珠子，那么剩余的$a[i]-1$a[i]−1个珠子都要放在上图蓝色珠子的前面。
而放置的空隙总共是有$sum[i-1]+1$sum[i−1]+1个的（如下图）

$A:$A: 所以放置方案数是$sum[i-1]^{a[i]-1}$sum[i−1]a[i]−1吗？

不是！
如果我们有$3$3个珠子要放，那么就有可能为以下6种情况（$x-y$x−y表示第$x$x颗珠子放第$y$y个位置）

• $1-2,2-5,3-6$1−2,2−5,3−6
• $1-2,2-6,3-5$1−2,2−6,3−5
• $1-5,2-2,3-6$1−5,2−2,3−6
• $......$......

而这6种情况实质上是一模一样的，这样就会计算重复的。

$A:$A: 所以放置方案数是$\frac{sum[i-1]^{a[i]-1}}{sum[i-1]!}$sum[i−1]!sum[i−1]a[i]−1​吗？

依然不是。
虽然有一些排列方案会重复$sum[i-1]!$sum[i−1]!次，但是也有一些方案重复的次数小于$sum[i-1]!$sum[i−1]!，同时也有一些方案是不会重复的。
例如$1-3,2-3,3-3$1−3,2−3,3−3这种情况它就只会算一次。
很显然，这种计算是因为选择的位置本身的重复而导致的。例如上例选择的位置3就重复了，但是3,3,3的全排列只有3,3,3一种情况，所以就只会出现一次。
而$1-4,2-1,3-1$1−4,2−1,3−1就会出现3次，因为4,1,1的全排列有$(1,1,4),(1,4,1),(4,1,1)$(1,1,4),(1,4,1),(4,1,1)三种。

所以放置$a[i]-1$a[i]−1个珠子的方案数还需要分类讨论一下。

• 如果$a[i]-1$a[i]−1个珠子位置各不相同，那么就相当于从$sum[i-1]$sum[i−1]个空位种选择$a[i]-1$a[i]−1个的方案数，所以就是$C^{a[i]-1}_{sum[i-1]}$Csum[i−1]a[i]−1​
• 如果$a[i]-1$a[i]−1个珠子位置有1个相同，那么就相当于从$sum[i-1]$sum[i−1]个空位种选择$a[i]-2$a[i]−2个的方案数，但是这个相同的位置可能是选择的位置中的任意一个，所以就是$C^{a[i]-2}_{sum[i-1]}\times C^{1}_{a[i]-2}$Csum[i−1]a[i]−2​×Ca[i]−21​$**
• 以此类推。

所以第$i$i中珠子的方案数是
$\sum^{a[i]-1}_{j=2} C(sum[i-1]+1,j)\times C(a[i]-2,j-1)$j=2∑a[i]−1​C(sum[i−1]+1,j)×C(a[i]−2,j−1)

最终答案就是
$\sum^{n}_{i=2}\sum^{a[i]-1}_{j=2} C(sum[i-1]+1,j)\times C(a[i]-2,j-1)$i=2∑n​j=2∑a[i]−1​C(sum[i−1]+1,j)×C(a[i]−2,j−1)

均摊思想得时间复杂度为$O(\sum^{n}_{i=1} a[i])$O(∑i=1n​a[i])（即$O(sum[n])$O(sum[n])）,由于题目中说了所有珠子数量和小于$5\times 10^5$5×105，所以是可以过去的。

$\color{white}\texttt{吐槽：这道题卡了我1.5h woc}$吐槽：这道题卡了我1.5h woc

---

代码：

#include <cstdio>
using namespace std;
typedef long long ll;

const int N=100010,MOD=998244353;
ll a[N],sum[N],fac[N*5],inv[N*5],ans,s;
int n;

ll power(ll x,ll y)
{
	ll ans=1;
	while (y)
	{
		if (y&1) ans=ans*x%MOD;
		x=x*x%MOD;
		y>>=1;
	}
	return ans;
}

ll C(ll x,ll y)
{
	return fac[x]* inv[y] %MOD *inv[x-y] %MOD;
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	fac[0]=1; inv[0]=1;
	for (int i=1;i<=500000;i++)
	{
		fac[i]=fac[i-1]*i%MOD;
		inv[i]=power(fac[i],MOD-2);
	}
	ans=1;
	for (int i=2;i<=n;i++)
	{
		s=0;
		for (int j=1;j<a[i];j++) 
			s=(s+C(sum[i-1]+1,j)*C(a[i]-2,j-1))%MOD;
		if (!s) s=1;
		ans=ans*s%MOD;
	}
	printf("%lld",ans);
	return 0;
}