Day1

T1

只与约数有关，而看100以内的测试点，最多10个约数，(m leq 3)，本来想把(2m)个约数分成对应的小部分和大部分，然后，枚举小部分，统计可行的贡献，出了些问题吧

然后发现如果我暴力枚举所有情况好像也不是很多的样子，然后写了个dfs记录合法的方案数，不过看其他同学写的都是dp（和正解比较靠近），虽然分数一样，我还是太浅薄了

正解：

设(F(x) = prodlimits_{i = 1}^{2m} x_i) 且(F(x) < n^m)其中(x_i)都假设满足题目中的条件，当我把其中的x都替换成他对应的n/x，就会发现我新得到的(F(x') > n^m)

综上所述，每一个 < (n^m)的F(x)都会对应一个 > (n^m)的F(x')

假设所有(x)中，(F(x) < n^m)的有(s_1)个，(F(x) = n^m)的有(s_2)个，(F(x) > n^m)的有(s_3)个

(s1 = s3,s_1+s_2+s_3 = {sigma (n)}^{2m})，所以(s_1 = dfrac{sigma (n)^{2m}-s_2}{2})，这样问题就转化成了求(s_2)

因为一个数可以由多个质因子组成我们可以把(n)进行质因数分解，然后对于每一个质因数，把他的指数分配给这(2m)个位置

dp方程就出来了(dp[i][j] += dp[i-1][j-k])其中(k leq w)，w为枚举到的质因子的指数，还可以滚动数组优化掉一维

T2

定义题，每次删除一个最长的单调子序列，直到把整个序列清空，这样我用线段树优化求最长上升/下降子序列，其实就是维护前缀dp最大值

不过也算是这么长时间以来的第一次模拟，写的我有点懒，断断续续卡着时间写完的，然后就直接交了，主要是处理位置的时候0出了点问题就挂了

然后改了改交上去被卡常了，最后12秒跑出的100分，不过换成树状数组就能A……常数问题，问题不大

T3

推式子，写矩乘？？？？

Day2

T1

发现方案数只有2或-1（只有最大和次大值可能互换位置），相同数字的横纵坐标的交会确定这个数的位置（一个数确定好就不能再确定下一次）

暴力确定最后判断一下正确性就好了，不过我好像写的比较麻烦，也出了点问题，szq(shen) 重构了一部分，最后还有点小细节，也算是过了

T2

暴力递归切分然后判断是否相似，期望复杂度好像是对的，定义的比较类似的变量名搞混了，就爆零了……

T3

状压dp，dp[i][j]表示i这个状态组成的数，膜m的为j的方案数

状态总数为0-9数字出现次数的连乘，转移：f[i][k] = (f[i][k] + f[i-a[j]][((k-p[g[i]-1]*j)%m+m)%m]) % mod;

Day 3

今天写题的手感不是特别好

T1

铺路问题输出方案

T2

manaher+SA+ST+前缀和，写的时候还算顺畅，思路还是比较清晰，各个部分分开写分开调，体验感还不错

然后最后统计答案的时候出了点小问题，还没开longlong，调完了，但还没测，不过大样例过了，只是不知道时间和空间怎么样

后续：爆空间了，把st表改成线段树就好了，不过st表256也能过，128就离谱……第二次换数据结构

T3

最简单的暴力找每个路径然后统计答案，也许还能再写一点吧，不过也没什么时间了，也没往下写

总体来说写的让我还是比较满意，可能因为第二题比较复杂还写出来了比较开心

Day4

T2

n方dp:

f1[i][j]表示i位置为上升子序列的尾，j位置为下降子序列的尾

f2[i][j]表示i位置为下降子序列的尾，j位置为上升子序列的尾

这样列出转移方程：

if (f1[i-1][j] != 0){
	if (a[i-1] < a[i]) (f1[i][j] += f1[i-1][j]) %= mod;
	if (j > a[i]) (f2[i][a[i-1]] += f1[i-1][j]) %= mod;
}
if (f2[i-1][j] != 0){
	if (a[i-1] > a[i]) (f2[i][j] += f2[i-1][j]) %= mod;
	if (j < a[i]) (f1[i][a[i-1]] += f2[i-1][j]) %= mod;
}

发现是一个只与i-1有关且是一段连续区间和的方程，可以线段树优化求区间和

值得注意的是如果不满足条件需要清空线段树，但是暴力清空会T，所以我们可以在根节点打个懒标记

T3

难得的写Hash，但是少取模，爆longlong了，不过暴力(n^3)也可以过

然后对于数据随机的部分可以暴力向后判断500位，能得到50分的好成绩