2018.10.30 uoj#273. 【清华集训2016】你的生命已如风中残烛（组合数学）

传送门

组合数学妙题。

我们把这mmm个数都减去111。

然后出牌的地方就变成了−1-1−1。

然后发现求出每个位置的前缀和之后全部都是非负数。

考虑在最后加入一个−1-1−1构成一个m+1m+1m+1个数的序列。

那么对于这个序列的所有循环同构。

只有当前这种是合法的。

原因很简单。

最后一个位置的前缀和是−1-1−1，因此除了当前这种之外的循环同构必定有一个前缀和是负数。

反过来发现对于每一个不合法的，它一定有一个循环同构是合法的。

对于这个序列的总方案数只有m!m!m!种。

然后最后一个数种类是定了的。

因此总方案数：m!m−n+1\frac {m!} {m-n+1}m−n+1m!

代码：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
const int mod=998244353;
int n,ans=1,m=0;
int main(){
	n=read();
	for(int i=1;i<=n;++i)m+=read();
	for(int i=1;i<=m;++i)if(i^(m-n+1))ans=(long long)i*ans%mod;
	cout<<ans;
	return 0;
}

巴特西

2018.10.30 uoj#273. 【清华集训2016】你的生命已如风中残烛（组合数学）

最新文章

热门文章