[hdu6432]Problem G. Cyclic

发布时间：2020-12-14 03:45:40 所属栏目：大数据来源：网络整理

导读：题目大意：给你$n$，一种合法的排列为，排列中没有$s[i%n+1]-s[i]==1$，求合法方案数题解：容斥，令$f_{i,j}$表示有$i$个元素，至少包含$j$个$s[i%n+1]-s[i]==1$的方案数，发现$f_{n,1}=binom n 1(n-2)!$个推广$f_{n,k}=binom n k(n-k-1)!$（令$(-1)

题目大意：给你$n$，一种合法的排列为，排列中没有$s[i%n+1]-s[i]==1$，求合法方案数

题解：容斥，令$f_{i,j}$表示有$i$个元素，至少包含$j$个$s[i%n+1]-s[i]==1$的方案数，发现$f_{n,1}=binom n 1(n-2)!$个

推广$f_{n,k}=binom n k(n-k-1)!$（令$(-1)!==1$）

$therefore ans = (-1)^n + sum_{k = 0}^{n - 1} (-1)^k binom{n}{k} (n - k - 1)!$

卡点：无

C++ Code：

#include <cstdio>
#define maxn 100010
const long long mod = 998244353;
int Tim,n;
long long FAC[maxn + 1],inv[maxn],*fac = &FAC[1],ans;
long long C(long long a,long long b) {
	if (a < b) return 0;
	return fac[a] * inv[b] % mod * inv[a - b] % mod;
}
int main() {
	scanf("%d",&Tim);
	fac[-1] = fac[0] = fac[1] = inv[0] = inv[1] = 1;
	for (int i = 2; i <= 100000; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = inv[mod % i] * (mod - mod / i) % mod;
	}
	for (int i = 2; i <= 100000; i++) inv[i] = inv[i] * inv[i - 1] % mod;
	while (Tim --> 0) {
		scanf("%d",&n);
		ans = 0;
		for (int i = 0; i <= n; i++) {
			ans = (ans + ((i & 1) ? -1ll : 1ll) * C(n,i) * fac[n - i - 1] % mod) % mod;
		}
		if (ans < 0) ans += mod;
		printf("%lldn",ans);
	}
	return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!