bzoj 4735 你的生命已如风中残烛

Posted on | Views:

一道短小精悍(指代码)的数学题.

  • 把每个位置上的数都 $-1$ ,于是要求就变为每个位置的前缀和都是非负数.
  • 如果在最后再加入一个 $-1$ ,那么就只有最后一个位置前缀和为 $-1$ ,其他位置都是非负数.
  • 这样就可证明,对于一个序列的所有循环同构,有且仅有一种序列是合法的.
  • 因为只有把多出来的 $-1$ 放在最后才合法.因为总和为 $-1$ ,若最后一个位置不是 $-1$ ,那么前面一个位置的前缀和一定为负.
  • 而这个 $-1$ 可以是原有的与新加的共 $m-n+1$ 个 $-1$ 中的任意一个,所以应除去.

$$
ans=\frac {m!} {m-n+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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=998244353;
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
int main()
{
	int n=read(),m=0;
	for(int i=1;i<=n;++i)
		m+=read();
	int ans=1;
	for(int i=2;i<=m;++i)
		ans=mul(ans,i);
	ans=mul(ans,fpow(m-n+1,P-2));
	cout<<ans<<endl;
	return 0;
}