首页 > 其他分享 >AtCoder Beginner Contest 309 G Ban Permutation

AtCoder Beginner Contest 309 G Ban Permutation

时间:2023-07-11 20:34:12浏览次数:43  
标签:AtCoder typedef Beginner Contest int long maxn 309

洛谷传送门

AtCoder 传送门

前置知识:[ARC132C] Almost Sorted

看 \(\ge X\) 不顺眼,怎么办呢!直接容斥!

钦定 \(j\) 个位置满足 \(|P_i - i| < X\),其余任意,就转化成了 [ARC132C] Almost Sorted

具体一点就是,你设 \(f_{i, j, S}\) 表示前 \(i\) 位有 \(j\) 个位置满足 \(|P_i - i| < X\),然后 \(i - (X - 1) \sim i + (X - 1)\) 的覆盖情况为 \(S\)(状压),作用是你填 \(P_i\) 时知道哪些数已经被填过了。转移讨论是否钦定 \(|P_i - i| < X\) 即可,若钦定 \(|P_i - i| < X\) 还要枚举 \(P_i\)。注意一些边界的处理。

答案是 \(\sum\limits_{i = 0}^n \sum\limits_S f_{n, i, S} \times (-1)^i \times (n - i)!\),\((-1)^i\) 是容斥系数,还要乘 \((n - i)!\) 是因为除这 \(i\) 个数以外的所有数可以随便排。

时间复杂度 \(O(n^2 4^{X} X)\)。

code
// Problem: G - Ban Permutation
// Contest: AtCoder - Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309)
// URL: https://atcoder.jp/contests/abc309/tasks/abc309_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 110;
const int mod = 998244353;

int n, m, f[maxn][maxn][maxn * 10];
ll fac[maxn];

inline void upd(int &x, int y) {
	x += y;
	(x >= mod) && (x -= mod);
}

void solve() {
	scanf("%d%d", &n, &m);
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) {
		fac[i] = fac[i - 1] * i % mod;
	}
	--m;
	f[0][0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < i; ++j) {
			for (int S = 0; S < (1 << (m * 2 + 1)); ++S) {
				if (!f[i - 1][j][S]) {
					continue;
				}
				int T = (S >> 1);
				upd(f[i][j][T], f[i - 1][j][S]);
				for (int k = 0; k <= m * 2; ++k) {
					if ((~T) & (1 << k)) {
						if (i + k - m < 1 || i + k - m > n) {
							continue;
						}
						upd(f[i][j + 1][T | (1 << k)], f[i - 1][j][S]);
					}
				}
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i <= n; ++i) {
		for (int S = 0; S < (1 << (m * 2 + 1)); ++S) {
			ll t = (i & 1) ? (mod - f[n][i][S]) : f[n][i][S];
			ans = (ans + t * fac[n - i] % mod) % mod;
		}
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

标签:AtCoder,typedef,Beginner,Contest,int,long,maxn,309
From: https://www.cnblogs.com/zltzlt-blog/p/17545830.html

相关文章

  • atcoder绿题选做
    ABC305:E  https://atcoder.jp/contests/abc305/tasks/abc305_e题意:给定一个无向图,给定k个守卫,每个守卫有h[i]的耐力值,如果是一个在图中是被保护的要满足和守卫的距离至少为h[i],让你升序打印所有被守卫的点解题思路:可以从守卫出发,看守卫在可以走的情况下最远走到哪,最后统计......
  • Atcoder ABC308H Make Q
    考虑枚举唯一一个度数为\(3\)的点\(u\),即既在环上又与非环上一点相连的那个点。接下来考虑先处理环,那可以先把\(u\)从图上删掉,环的最短距离便是与\(u\)有连边的\(2\)个点在图上最短路长度加上\(2\)个点与\(u\)连边的长度,即\(\min\{w_{u,i}+w_{u,j}+\operator......
  • 人工智能课程:AI For Beginners
    背景介绍随着人工智能技术的快速发展,许多人对于如何入门人工智能感到困惑。针对这个问题,微软推出了开源项目AI-For-Beginners,提供一个为期12周、共24课的人工智能课程,旨在让所有人都能轻松学习人工智能知识!GitHub开源项目microsoft/AI-For-Beginners,该项目在GitHub有超过8......
  • Atcoder ARC164B Switching Travel
    称\(c_u\not=c_v\)的边\((u,v)\)为普通边,\(c_u=c_v\)的边\((u,v)\)为特殊边。能发现若满足条件则这个环应该是由一条特殊边和若干条普通便组成的(从特殊边的一个顶点出发一直经过普通边,最后走到特殊边的另一个顶点再走回来)。于是若这个特殊边的两个顶点能只通过普通......
  • AtCoder Regular Contest 164 (A-C)
    A.TernaryDecomposition思维难度其实可以作为第二题思路先考虑最优情况下需要多少个数来组成(不够就No)在考虑全部为1的情况下是否可行(N<K这种情况不行)剩下的情况,考虑每次把高位的1向下挪变为3,所需的数字+2那么即三进制拆分后,在[min,max]范围内,且与最优情况差值为......
  • Atcode Beginner Constest 309 E
    e题的题意又理解错了(E.FamilyandInsurance题意给定一棵或者若干棵树,以及\(m\)次操作。每次操作将一个节点后面几层的儿子节点的权值加1,求最后有多少节点的权值至少为1。思路设\(dp[i]\)为节点\(i\)后面有几个节点被覆盖,若没有覆盖为-1。DFS一遍维护每个\(dp[i]\)的最大值,......
  • Atcoder ARC159C Permutation Addition
    设\(s=\sum\limits_{i=1}^na_i\),考虑加上排列\(p\),那么\(s\leftarrows+\frac{n\times(n+1)}{2}\)。当有解时,因为\(a_i\)相等,所以有\(s\bmodn=0\)。考虑\(n\bmod2=1\)时,\(\frac{n\times(n+1)}{2}\bmodn=0\),所以\(s\bmodn=0\)时才会有解。......
  • AtCoder Beginner Contest 309
    A:1#include<cstdio>2#include<cstring>3#include<algorithm>4#include<iostream>5#include<string>6#include<vector>7#include<stack>8#include<bitset>9#include<cstdlib>10#include......
  • AtCoder Beginner Contest 273 ABCD
    AtCoderBeginnerContest273A-ARecursiveFunctionProblemStatement题意:给你一个函数\(f(x)\)\(f(0)=1\)对于所有正整数\(k\),有\(f(k)=k*f(k-1)\)找到\(f(N)\)Solution思路:数据范围只有\(10\),直接递归。#include<bits/stdc++.h>usingnamespacestd;typede......
  • abc309e <dfs>
    E-FamilyandInsurance//https://atcoder.jp/contests/abc309/tasks/abc309_e//<dfs>//关键在于意识到,每个结点保留最大后代数即可#include<iostream>#include<algorithm>#include<vector>usingnamespacestd;typedeflonglongLL;constintN=3......