[提高组集训2021] 模拟赛2
操作
题目描述
点此看题
解法
分裂有点难，但是发现分裂第一堆石子就相当于合并第二堆石子，问题就转化为两堆石子都能合并，最后达到相同的状态。
全部合并成一堆石子答案是 \(n+m-2\)，考虑第一堆石子的某个子集和跟第二个子集的某个子集和相等，答案就能减少 \(2\)，那么设计 \(dp[s]\) 表示考虑 \(s\) 最大能划分出的子集个数，\(O(3^{2n})\) 子集枚举即可。
总结
最小化代价 \(=\) 不优代价 \(-\) 调整之后减少的代价，这道题直接最小化代价是困难的。
#include
#include
using namespace std;
const int M = 20;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int T,n,m,sum[1<
等级
题目描述
点此看题
解法
可以写出简单判据：
- \(\max-\min=(r-l)\cdot k\)
- 区间中全部字符都不相等。
- 所有数模 \(k\) 同余。
限制一二都好做，但是限制三根本做不动。因为每次询问 \(k\) 是变化的，所以这个东西根本维护不出来。我们考虑找和 \(k\) 无关的值作为判据，自然就想到了 \(\tt gcd\)，我们维护区间相邻两个数差的 \(\tt gcd\)，判断它是否被 \(k\) 整除即可。
还有一种乱搞是不充分但易于区分的判据，也就是维护区间数的二次方和，和等差数列的二次方和作比较即可。
总结
维护的东西不要由可变量决定，找不由可变量决定但可以和之建立关系的判据。
矩阵
题目描述
点此看题
解法1
本题主要抓住每行每列有两个位置是 \(1\) 这个限制，矩阵可以看成行和列连边的二分图，那么本题就是要在这个图中选出若干条边使得所有点构成若干个环。
设 \(f[i]\) 表示考虑 \(i\times i\) 的矩阵的方案数，转移考虑枚举第一行所在环点的个数（该个数一定是偶数）：
\[f_n=\sum_{i=2}^n{n\choose i}{n-1\choose i-1}A_if_{n-i}
\]组合数的意义是选出 \(i\) 列和剩下的 \(i-1\) 行，\(A_i\) 表示每边点数为 \(i\) 的二分图构成环的个数。我们固定左边的 \(1\) 为起点，左右交替选点匹配，方案数是 \(n!(n-1)!\)，由于起点连出去了两条边，同一个环会被算两次，所以方案数是 \(\frac{n!(n-1)!}{2}\)
这样递推的时间复杂度是 \(O(n^2)\) 的，考虑把全部展开化简：
\[f_n=\sum_{i=2}^n\frac{n!}{i!(n-i)!}\frac{(n-1)!}{(i-1)!(n-i)!}\frac{i!(i-1)!}{2}f_{n-i}
\]\[f_n=\sum_{i=2}^n\frac{n!(n-1)!}{2(n-1)!^2}f_{n-i}
\]\[f_n=\frac{n!(n-1)!}{2}\sum_{i=2}^n\frac{f_{n-i}}{(n-i)!^2}
\]那么令 \(g_n=\frac{f_n}{n!^2}\) 就是一个前缀和的转移了，时间复杂度 \(O(n)\)
解法2
还有一个转化方式是：有 \(n\) 个格子 \(n\) 个操作，格子和操作都不同，每个操作可以让两个格子加 \(1\)，问最后让所有格子都为 \(2\) 的方案数。
设 \(f[n]\) 表示 \(n\) 个格子初始为空的方案数，\(g[n]\) 表示 \(n\) 个格子初始有两个格子有 \(1\)（并且我们已知这两个格子是谁）的方案数，转移考虑用一次操作改变最后一个格子（因为改变格子的顺序不影响方案，我们要钦定一个顺序），所以会涉及到 \(f,g\) 的交替转移：
\[f[n]=(n-1)\cdot n\cdot \frac{g[n]}{2}
\]\[g[n]=(n-1)\cdot f[n-2]+(n-1)(n-2)\cdot g[n-1]
\]\(g[n]\) 的转移就是操作最后一个有 \(1\) 的位置，可以选出前面的 \(n-2\) 个格子的其中之一与之操作，有 \(n-1\) 种操作可供选择；或者操作这两个有 \(1\) 的位置转移到 \(f[n-2]\)
\(f[n]\) 的转移就是枚举前面 \(n-1\) 个格子的其中之一，然后用 \(n\) 种操作淦它和最后一个格子。
这里我最想讲的是 \(g[n-1]\) 转移到 \(f[n]\) 的时候为什么除以二，其实要分两种情况的。对于一次转移，反复操作两个格子的情况操作方案应该是 \({n\choose 2}\)，但是我们算成了 \(n(n-1)\)；操作三个格子的情况格子的枚举方案应该是 \({n\choose 2}\)，但是我们算成了 \(n(n-1)\)，所以要除以二。
总结
注意矩阵和图可以互化，特别是在度数有限制的时候（比如此题度数限制为 \(2\)，自然想到环）
计数的时候，注意什么让方案数不同（用系数表示），什么顺序无关（需要钦定顺序）
我考试时候计数怎么都会重，其实是第一步转化就出了问题（可惜我没有 \(\tt LiHan\) 大佬的转化能力）
#include
#define int long long
const int MOD = 998244353;
const int inv = (MOD+1)/2;
const int M = 10000005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,ans,f[M],g[M];
signed main()
{
//freopen("matrix.in","r",stdin);
//freopen("matrix.out","w",stdout);
n=read();
f[2]=g[2]=1;
for(int i=3;i<=n;i++)
{
g[i]=((i-1)*f[i-2]+(i-1)*(i-2)%MOD*g[i-1])%MOD;
f[i]=(i-1)*i/2%MOD*g[i]%MOD;
}
for(int i=2;i<=n;i++) ans=(ans+f[i])%MOD;
printf("%lld\n",(ans+MOD)%MOD);
}