• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

「 题解」NOIP2021模拟赛(2021-07-19)

开发技术 开发技术 1周前 (07-19) 7次浏览

小兔的话

欢迎大家在评论区留言哦~


D – 矩阵

简单题意

一个 (i * i)(01) 矩阵,若满足 每一行每一列 都满足 恰好(2) 个位置是 (1) 时,称为 (i) 级配对矩阵
(i) 级配对矩阵的个数为 (f_i);请求出:(sum_{i = 1}^n f_i),答案对 (998244353) 取模

数据范围

(1 leq n leq 10^7)

知识点

  • 动态规划((dp)

分析

题意转换

这个题目有点复杂,换成一个能更好理解题目解析的:
有一个长度为 (i) 的序列,初始状态时全部的数都为 (0)
(i) 次操作,每一次操作需要选择 (2) 个不同的位置,并把其所对应的数 (+1)
(f_i) 定义为能使原序列的数全部变成 (2) 的操作方案数;请求出:(sum_{i = 1}^n f_i),答案对 (998244353) 取模

  • 矩阵有 (i)(to) 长度为 (i) 的序列
  • 每一行的 (1)(2) 个位置 (to) 选择 (2) 个位置 (+1)
  • 矩阵有 (i)(to) (i) 次操作
  • 每一列都恰好满足有 (2) 个位置是 (1) (to) 使原序列的数全部变成 (2)
  • 每一列的 (1)(2) 个位置 (to) 该位置对应的 (2)(+1) 操作

题目解析

  • 特殊说明:(dp_i) 表示原题目中的 (f_i)(A) 表示排列数;(C) 表示组合数
  • 特殊说明:(F_i) 表示序列中已经进行了 (1) 次操作的方案数(即有 (2) 个位置已经是 (1) 了,剩下 (i-1) 次操作)

对于一个长度为 (i) 的空序列,考虑某个位置的 (2) 次操作
不妨考虑位置 (1)(任意一个都可以)的 (2) 次操作,这 (2) 次操作对位置 (1) 的总贡献是一样的(使位置 (1) 的数变为 (2)),就可以转换为其余 (i-1) 个位置中 (2) 个位置(可以相同)的 (+1) 操作,接下来讨论操作的位置(其余的 (i-1) 个)及其贡献((dp)):

  • (2) 次操作影响相同位置:(dp_{i-2} times (i-1) times C_i^2)
    • (dp_{i-2}):因为 (2) 次选择的是相同位置,那么就需要考虑剩下的 (i-2) 个位置的贡献
    • (i-1):位置的可能性,有 (i-1) 个位置可选择操作
    • (C_i^2):因为操作的顺序是会影响结果的,所以需要计算 (2) 次操作的可能性;有 (i) 个操作位置,选择其中的 (2) 次,又因为这 (2) 次操作是等价的所以是 (C_i^2)
  • (2) 次操作影响不同位置:(F_{i-1} times C_{i-1}^2 times A_i^2)
    • (F_{i-1})(2) 次操作影响不同位置,相当于 (i-1) 个位置中有 (2) 个已经 (+1)
    • (C_{i-1}^2):在 (i-1) 个位置中选 (2) 个(不计顺序)
    • (A_i^2):在 (i) 次操作选择 (2) 次进行不等价操作

接下来分析 (F)

  • (1) 次操作把 (1) 对应的 (2) 个位置变成 (2)(dp_{i-2} times (i-1))
    • (dp_{i-2}):除去这 (2) 个位置的方案数
    • (i-1):在 (i-1) 次操作中选择 (1)
  • (2) 次操作把 (1) 对应的 (2) 个位置变成 (2),同时把另外 (1) 个位置变为 (2)(dp_{i-3} times (i-2) times A_{i-1}^2)
    • (dp_{i-3}):除去这 (3) 个位置的方案数
    • (i-2):另外 (1) 个位置可能有 (i-2) 中可能
    • (A_{i-1}^2):在 (i-1) 次操作中选择 (2) 次进行不等价操作
  • (2) 次操作把 (1) 对应的 (2) 个位置变成 (2),同时把另外 (2) 个位置变为 (1)(F_{i-2} times A_{i-2}^2 times A_{i-1}^2)
    • (F_{i-2}):剩下 (i-2) 个中有 (2) 个已经位 (1) 的方案数
    • (A_{i-2}^2):在 (i-2) 个位置中选择 (2) 个变成 (1),与现在的 (2) 个位置匹配是不等价的,所以是 (A)
    • (A_{i-1}^2):在 (i-1) 次操作中选择 (2) 次进行不等价操作

初始化:(dp_0 = 1, dp_2 = 1, F_2 = 1),其余值为 (0)
循环枚举 (i),进行状态转移,顺便求出 (sum_{i=1}^n dp_i) 就可以了(这种做法似乎常数很大,不建议使用 C++(NOI)

代码

#include <cstdio>

#define int long long

int rint()
{
	int x = 0, fx = 1; char c = getchar();
	while (c < '0' || c > '9') { fx ^= (c == '-'); c = getchar(); }
	while ('0' <= c && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
	if (!fx) return -x;
	return x;
}

int qpow(int u, int v, int Mod)
{
	int res = 1;
	while (v)
	{
		if (v & 1LL) res = res * u % Mod;
		u = u * u % Mod; v >>= 1;
	}
	return res;
}

const int MOD = 998244353;
const int MAX_n = 1e7;

int ans, dp[MAX_n + 5], F[MAX_n + 5];
int FAC[MAX_n + 5], inv[MAX_n + 5];

int A(int n, int m) { return FAC[n] * inv[n - m] % MOD; }
int C(int n, int m) { return A(n, m) * inv[m] % MOD; }

signed main()
{
	freopen("matrix.in", "r", stdin);
	freopen("matrix.out", "w", stdout);
	int n = rint();
	FAC[0] = 1;
	for (int i = 1; i <= n; i++)
		FAC[i] = FAC[i - 1] * i % MOD;
	inv[n] = qpow(FAC[n], MOD - 2, MOD);
	for (int i = n; i >= 1; i--)
		inv[i - 1] = inv[i] * i % MOD;
	dp[0] = 1; dp[2] = 1; F[2] = 1;
	for (int i = 3; i <= n; i++)
	{
		dp[i] = (dp[i] + dp[i - 2] * C(i, 2) % MOD * (i - 1) % MOD) % MOD;
		dp[i] = (dp[i] + F[i - 1] * A(i, 2) % MOD * C(i - 1, 2) % MOD) % MOD;
		F[i] = (F[i] + dp[i - 2] * (i - 1) % MOD) % MOD;
		F[i] = (F[i] + F[i - 2] * A(i - 1, 2) % MOD * A(i - 2, 2) % MOD) % MOD;
		F[i] = (F[i] + dp[i - 3] * A(i - 1, 2) % MOD * (i - 2) % MOD) % MOD;
	}
	for (int i = 1; i <= n; i++) ans = (ans + dp[i]) % MOD;
	printf("%lldn", ans);
	return 0;
}



程序员灯塔
转载请注明原文链接:「 题解」NOIP2021模拟赛(2021-07-19)
喜欢 (0)