首页 > 其他分享 >LY1165 [ 20230324 CQYC省选模拟赛 T3 ] 迷雾

LY1165 [ 20230324 CQYC省选模拟赛 T3 ] 迷雾

时间:2024-03-18 15:14:40浏览次数:27  
标签:20230324 include 省选 T3 tp int 1ll Mod mod

题意

求有多少种长度为 \(N\) 的满足以下条件的序列。

  • 是一个 \(1 \sim N\) 的排列。
  • 至少 进行 \(K\) 次操作后,该序列才含有一个元素。

\(N \le 1000\)

Sol

首先因为序列是一个排列,所以操作次数不会太多。

操作次数大概在 \(\log N\) 的级别。

不难注意到对于一个数列,剩下的只会是 \(N\)。

考虑枚举 \(N\) 所在的位置,发现左右两边的贡献互不影响。

动态规划。设 \(f_{i, j, 0 / 1 / 2}\) 表示当前排列的长度为 \(i\),操作 \(j\) 次后清空 只剩下 \(N\)(在无法清空的情况下)。\(0 / 1 / 2\) 分别表示当前序列两边都没有限制、有一边为 \(\infty\)、两边都为 \(\infty\)。

对于当前的状态,枚举 \(N\) 的位置,不难发现左右两边需要有一边顶满操作 \(j\) 次的限制。

直接跑一遍 dp 即可。

复杂度:\(O(n ^ 2 \log n)\)。

Code

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#define ll long long
#define il inline
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
il int read() {
	int p = 0, flg = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flg = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getchar();
	}
	return p * flg;
}
void write(int x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}
bool _stmer;

const int N = 1e3 + 5, M = 21;

array <array <array <int, 3>, M>, N> f, g;

int pow_(int x, int k, int p) {
	int ans = 1;
	while (k) {
		if (k & 1) ans = 1ll * ans * x % p;
		x = 1ll * x * x % p;
		k >>= 1;
	}
	return ans;
}

int mod;

array <int, N> fac, inv;

il void init(int n) {
	fac[0] = 1;
	for (int i = 1; i <= n; i++)
		fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[n] = pow_(fac[n], mod - 2, mod);
	for (int i = n; i; i--)
		inv[i - 1] = 1ll * inv[i] * i % mod;
}

il int C(int n, int m) {
	if (n < m) return 0;
	return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}

il void Mod(int &x) {
	if (x >= mod) x -= mod;
	if (x < 0) x += mod;
}

bool _edmer;
signed main() {
	cerr << (&_stmer - &_edmer) / 1024.0 / 1024.0 << "MB\n";
#ifndef cxqghzj
	freopen("misty.in", "r", stdin);
	freopen("misty.out", "w", stdout);
#endif
	int n = read(), k = read(), p = read();
	::mod = p, init(1000);
	if (k > 12) return puts("0"), 0;
	f[0][0][0] = f[0][0][1] = f[0][0][2] = 1, g = f;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= 12; j++)
			for (int p = 0; p <= 2; p++)
				g[i - 1][j][p] = g[i - 1][j - 1][p] + f[i - 1][j][p], Mod(g[i - 1][j][p]);
		/* if (i == 2) */
			/* write(g[1][1][1]), puts(""); */
		for (int j = 1; j <= 12; j++) {
			for (int k = 1; k <= i; k++) {
				int tp = 0;
				tp += (1ll * f[k - 1][j][1] * g[i - k][j][1] % mod), Mod(tp);
				tp += (1ll * f[i - k][j][1] * g[k - 1][j - 1][1] % mod), Mod(tp);
				f[i][j][0] += 1ll * tp * C(i - 1, k - 1) % mod, Mod(f[i][j][0]);

				tp = 0;
				tp += (1ll * f[k - 1][j - 1][2] * g[i - k][j][1] % mod), Mod(tp);
				/* if (i == 2 && j == 1) */
					/* write(g[i - k][j][1]), puts("@"); */
				if (j > 1)
					tp += (1ll * f[i - k][j][1] * g[k - 1][j - 2][2] % mod), Mod(tp);
				f[i][j][1] += 1ll * tp * C(i - 1, k - 1) % mod, Mod(f[i][j][1]);

				tp = 0;
				tp += (1ll * f[k - 1][j][2] * g[i - k][j - 1][2] % mod), Mod(tp);
				tp += (1ll * f[i - k][j][2] * g[k - 1][j - 1][2] % mod), Mod(tp);
				tp += (1ll * f[k - 1][j - 1][2] * f[i - k][j - 1][2] % mod), Mod(tp);
				f[i][j][2] += 1ll * tp * C(i - 1, k - 1) % mod, Mod(f[i][j][2]);
			}
		}
	}
	/* for (int i = 0; i <= n; i++) */
		/* for (int j = 0; j <= 20; j++) */
			/* write(f[i][j][1]), putchar(" \n"[j == 20]); */
	int ans = 0;
	for (int i = k; i <= 12; i++)
		ans += f[n][i][0], Mod(ans);
	write(ans), puts("");
	return 0;
}
`

标签:20230324,include,省选,T3,tp,int,1ll,Mod,mod
From: https://www.cnblogs.com/cxqghzj/p/18080430

相关文章

  • NCV1117ST50T3G线性稳压器芯片中文资料规格书PDF数据手册引脚图图片价格参数
    产品概述:NCP1117系列为低压差(LDO)正向线性电压稳压器,能够提供超过1.0A的输出电流,800mA时温度范围内最大压差为1.2V。这一系列包括八个固定输出电压:1.5V、1.8V、2.0V、2.5V、2.85V、3.3V、5.0V和12V,保持稳压没有最低负载要求。另外还包括可调节输出版本,使用两个外部电阻,实现从......
  • springboot3使用validation进行参数验证
    前言  今天学习了使用validation整合springboot进行字段的校验,体验下来感觉很不错,有了validation可以省下一大堆控制器里面的数据校验,例如前端发送了一个请求到我们后端,请求中包含的数据字段一般情况下都是通过前端校验过的然后发送到后端进行处理,但是考虑到整体后端代码的可靠......
  • APT32 RTC+低功耗调试笔记
    1、项目需求   采用APT32F1023单片机,内部27K时钟驱动RTC,内部6M定时器作为主频。周期检测外部供电是否恢复,如果恢复则使用正常工作模式,否则仅开启RTC,关闭其他外设,进入低功耗待机模式。2、存在问题    A:开启看门狗后,会周期触发看门狗复位     B:进入低功耗模式后,......
  • YC260A [ 20240317 CQYC省选模拟赛 T1 ] 伙伴(aka)
    题意给定一张无自环、重边的不连通图。让你把这个图加上一些边成为若干个环。每个节点的权值为相邻两条边为原图上的边的个数-1。求所有点的权值和最大的权值。Sol考虑拆点。集中注意力,发现连边后形成一个二分图。既然要权值最大,肯定要让原图的边留下最多。直接做最大......
  • P10218 [省选联考 2024] 魔法手杖 题解
    Description给定\(a_1,a_2,\dots,a_n\)以及\(b_1,b_2,\dots,b_n\),满足\(a_i\in[0,2^k-1]\)以及\(b_i\geq0\),你需要给出\(S\subseteq\{1,2,\dots,n\}\)以及\(x\in[0,2^k-1]\)满足以下条件:\(\sum\limits_{i\inS}b_i\leqm\);满足以上条件的前提下,最大化\......
  • LibreOJ 4114 「联合省选 2024」迷宫守卫
    因为最后的比较方式是字典序,可以明确肯定是贪心的先让第一个数尽量大,然后是第二个数尽量大,以此类推。考虑到如果选出了第一个数,那么按照其\(\text{dfs}\)的方式,相当于是把根到这个树的链删掉了,变成了许多颗子树,然后在按照\(\text{dfs}\)遍历这几个子树的顺序依次在子树中类似......
  • 省选联考 2024
    省选联考2024前言有的题没必要一定要推到满分才可以,比较阴间的写个八九十的分就很不错了,特别阴间的写个暴力就算了,没必要一定要全学懂是不是/fad[省选联考2024]季风传送门讲题目转化为在\((0,0)\),求最小\(m\)使\(|x-\sum\limits_{i=0}^{m-1}x_{i\modn}|+|y-\sum\limi......
  • 联合省选 2024 游记
    Day0写了一堆板子。但是不希望能用上。怕考场上紧张写挂。Day16:50起床。感觉进考场前有一点点困啊,不过不要紧,优势在我!8:2?开题,wind,xor,wormhole!wind看起来是一个不难的数学题,xor看上去可以拼很多暴力,wormhole应该是一个防AK的计数。正常操作,先做wind,想起去......
  • 【Nut3】nuxt.config.ts项目nuxt配置文件介绍
    简言记录下nuxt3的nuxt.config.ts文件的介绍和使用。NuxtConfigurationnuxt.config.tsNuxt可以通过一个单独的nuxt.config文件进行简单配置。配置文件创建nuxt.config文件的扩展名可以是.js、.ts或.mjs。然后默认导出全局函数defineNuxtConfig的返回值,defineNuxtCo......
  • LY1168 [ 20230325 CQYC省选模拟赛 T3 ] 游戏
    题意给定\(n\)个区间\(l_i,r_i,k_i\)。\(k_i\)表示解锁当前点当且仅当\(l_i\tor_i\)的区间内至少有\(k_i\)个点被解锁。问一共能解锁多少点。Sol直接暴力跑是\(n^2\)的。不难想到优化建图,复杂度:\(O(nk\log)\)这样明显是过不去的。集中注意力。注意到操......