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

2021年7月20日 9点热度 0条评论 来源: 微笑是糖゛甜到忧伤づ

小兔的话

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

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("%lld\n", ans);
	return 0;
}

    原文作者:微笑是糖゛甜到忧伤づ
    原文地址: https://www.cnblogs.com/DONGJIE-06/p/15032628.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。