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

题目大意:

题目链接:https://jzoj.net/senior/#main/show/4786
nn种珠子,要求把这些珠子放在一条直线上,且第ii种珠子的最后一个的位置lastilast_i满足last1<last2<...<lastnlast_1<last_2<...<last_n。求满足要求的方案数。


思路:

假设我们求完了前ii种珠子按要求摆放的方案数,现在要求第i+1i+1种珠子的方案数。
sum[i1]sum[i-1]表示前i1i-1种珠子的总个数,那么第ii种珠子的最后一个就应该放在这sum[i1]sum[i-1]个珠子后面,剩余的第ii种珠子就应该全部放在这颗珠子的前面。
在这里插入图片描述

那么如果总共有a[i]a[i]个第ii种珠子,那么剩余的a[i]1a[i]-1个珠子都要放在上图蓝色珠子的前面。
而放置的空隙总共是有sum[i1]+1sum[i-1]+1个的(如下图)
在这里插入图片描述

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

不是!
如果我们有33个珠子要放,那么就有可能为以下6种情况(xyx-y表示第xx颗珠子放第yy个位置)

  • 12,25,361-2,2-5,3-6
  • 12,26,351-2,2-6,3-5
  • 15,22,361-5,2-2,3-6
  • ............

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

A:A: 所以放置方案数是sum[i1]a[i]1sum[i1]!frac{sum[i-1]^{a[i]-1}}{sum[i-1]!}吗?

依然不是。
虽然有一些排列方案会重复sum[i1]!sum[i-1]!次,但是也有一些方案重复的次数小于sum[i1]!sum[i-1]!,同时也有一些方案是不会重复的。
例如13,23,331-3,2-3,3-3这种情况它就只会算一次。
很显然,这种计算是因为选择的位置本身的重复而导致的。例如上例选择的位置3就重复了,但是3,3,3的全排列只有3,3,3一种情况,所以就只会出现一次。
14,21,311-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]1a[i]-1个珠子的方案数还需要分类讨论一下。

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

所以第ii中珠子的方案数是
j=2a[i]1C(sum[i1]+1,j)×C(a[i]2,j1) sum^{a[i]-1}_{j=2} C(sum[i-1]+1,j) imes C(a[i]-2,j-1)

最终答案就是
i=2nj=2a[i]1C(sum[i1]+1,j)×C(a[i]2,j1) sum^{n}_{i=2}sum^{a[i]-1}_{j=2} C(sum[i-1]+1,j) imes C(a[i]-2,j-1)

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

吐槽:这道题卡了我1.5h woccolor{white} exttt{吐槽:这道题卡了我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;
}
原文地址:https://www.cnblogs.com/hello-tomorrow/p/11998170.html