7.16 ZROI-DAY3 模拟赛

赛时历程

感觉今天的题目名就很鬼畜，矩阵的秩，偶数图，组合方案，每一个看起来都很有难度，前两个听起来高大上，最后一个听起来像是神仙组合题目/kk

矩阵的秩，理解了一大会儿，一开始还不知道他这里说的向量和是哪个(没仔细理解什么mod2的矩阵)，明白后(赛后感觉自己完全没明白，简直是傻掉了)，只能通过dfs写出来23分。过去看T2，T3，感觉T2不好惹，想不到什么暴力做法。T3吧，也是一头雾水，或许能DP，但我不懂。

陷入困境以后，看了看提交，大家都会T1的所有样例和T3的75，也就是(n^2) 了，我现在只会T1的爆搜，有点纳闷，为什么我什么都没想到。自闭了，再次遇到困难睡大觉。上了厕所清醒了一下，但没完全清醒，感觉脑子依然不灵光，看到T2的那个k=2，感觉这个还不错，不过就12分，但现在真的除了这个啥也不会啊，就只好码了。

写完的时候差不多过去了两个半小时，看lk今天的状态，似乎他也没有前两次那么顺利。虽然不管他怎样都与我无关就是了。

最后也没想出来什么东西，但大家的分还都挺好看的？

赛后发现

最后得分35。从两个半小时只后一分未得。

T1 实际上，那个秩，就跟线性基一样，就是说，考虑线性基一样的东西就好，但是因为我在理解上太浅，(太傻了)所以根本没有理解到有DP的做法。

T2 就傻了，线图啥的。

T3 组合方案，为什么我就完全不会啊QAQ DP是类似0/1背包的东西，DP还是要练！

技术总结

T1

没想到是找规律题。

(n^3) DP考虑到了线性基里学到的线性相关与线性无关，新加入一行就会有两种情况，要么是新加一个秩，要么是保留原来的秩，所以可以设置状态，设 (f[i][j]) 为前 (i) 行，已经有了 (j) 个秩的方案数，那么显然，新加入一个秩的情况下，不是新秩的情况有 (2^j) 种，这里利用到了大小为 (j) 的极大线性无关组可以凑出来 (2^j) 种情况的结论，然后就可以转移 (f[i][j]=(2^n-2^j)*f[i-1][j-1]+f[i-1][j]*2^j) ，最后 (f[n][m])就是要求的东西，这个考虑每一个n的时候都需要做一遍 (n^2) 的DP，所以说复杂度是 (O(n^3)) 的。

接下来，正解可以用生成函数，也可以直接找规律。

T2

线图！听都没听过，但myh说这东西 UOJ 里被问烂了。彳亍。

T3

先讲我没有写的暴力吧。0/1背包，枚举双背包里这次放的东西的重量a,b，然后(f[A+a][B+b]) 从 (f[A][B]+1) 可以转过来，取max即可。考场太sb。

然后正解是二分答案，虽然我也朝这个方向想过，但是我二分 (k) 之后根本不会check，多暴力的判断都不会，自闭(突然忘了这里是技术总结)。

感觉今天的题好难顶。