上午
考试了
(rank)再次倒数
下午
讲了一些关于矩阵乘法的东西
(n leq 1e18)一看数据范围，一点都不大，才(1e18)嘛
直接搞矩阵！
其实说实话这题我还是不太熟悉
先埋下一个坑 日后补上
对于这个题，我们首先简化问题，假如底下没有鳄鱼，问题就可以转化为，给你(n)个点，(m)条边，起点和终点，问你有多少种方案通过恰好走(k)步可以到达终点
其中(n leq 100, k leq 1e18)
乍一看像最短路问题，但是邻接矩阵的思想，我们可以搞一个矩阵，(ta)自乘两次，意为着走了两步
关于这个前进的问题，我还是不很清晰，等以后做矩阵乘法的题的时候，再来补上这个坑
关于鳄鱼的话，通过观察发现，鳄鱼的周期只有(2,3,4)所以我们可以找出他们的公倍数(12)来
还讲了一些计数问题的dp
第一二类斯特林数
组合数
环形染色
不相邻染色
其实我真的没有听懂多少关于计数问题dp的东西，我连斯特林数这样的计数问题都搞不明白，更别提在计数问题上再进行动规了
晚上
改上午考试的题
分别为:
第一题
(Description)
(WJQ)发现这是一个(n)行的数塔，第(n)行有(n)个数。最后一行依次为(1,2,3...n)，第(i)行的第(j)个数等于第(i+1)行第(j)个数和第(j+1)个数的和。他觉得塔顶可能有宝贝，但是太高了他看不见。于是它请你帮忙算算塔顶的数字是多少。
(Input)
一行一个数字(T)表示数据组数接下来(T)行，每行一个数字，表示(n)。
(Output)
输出(T)行，每行一个数字表示答案。由于答案可能过大，又考虑到各位选手可能对高精充满抵触，因此我们的答案对(998244353)取模
(Sample Input)
2
2
4
(Sample Output)
3
20
(HINT)
(30%)的数据，(n leq 100) ,(T leq 10)
(50%)的数据，(n leq 10000)
(100%)的数据，(n < 1e18)，(T leq 1000)
对于这道题吧，假设(T)只为(1)，那就是很好做的模拟题，又看到(n)比较大
我们考虑滚动数组...然后(3min)写出来了....自我感觉良好，感觉自己貌似很(nb)，轻松打暴力能得(50pts).
于是开始信心十足的开始推式子找规律
...
经过一番操作找出来了，写上，交！ (30pts)....我tm暴力都能得(50pts)呢！我自认为的正解才他娘的(30pts)?
就很不舒服嘛....
下面说一说关于这道题，我是怎么推的式子吧
48
20 28
8 12 16
3 5 7 9
1 2 3 4 5
我们设最左边一列为(f)数组，紧靠着(f)数组那一列为(g)数组
显然 我们的答案就是(f)数组，紧接着开始打表找规律
(f[1] = 1, g[1] = 2)
(f[2] = 3, g[2] = 5)
(f[3] = 8, g[3] = 12)
(...)
可以观察到，(f[n] = f[n-1]+g[n-1])。但是(g)数组怎么求？我们考虑像求(f)数组一样，从下往上转移，但是寻寻觅觅发现终究没有办法。于是开始观察(g)数组的周围
...
观察发现(f)数组貌似与(g)数组有些关系
(g[1] - f[1] = 2 - 1 = 1 = 2^0)
(g[2] - f[2] = 5 - 3 = 2 = 2^1)
(g[3] - f[3] = 12 - 8 = 4 = 2^2)
(...)
得出结论：
(f[n] = f[n-1] + g[n-1])
(f[n] = f[n-1] + f[n-1] + 2^{n-2})
(f[n] = 2*f[n-1] + 2^{n-2})
然后通过递归函数与快速幂就可以做了，在(n leq 10000) 以内贼快
上面就是我三十分代码的原因...！！！
考完试之后，在讲题的过程中，我意识到我距离正确答案只差一步
其实我们可以再往下推一步，我们令这个式子左右两边同时除以(2^n)
魔改过程:
(dfrac {f[n]} {2^n} = dfrac {2*f[n-1]} {2^n} + dfrac {2^{n-2}} {2^n})
(dfrac {f[n]} {2^n} = dfrac {f[n-1]} {2^{n-1}} + dfrac {1} {4})
我们设(a_n = dfrac {f[n]} {2^n})，故(a_1 = dfrac {f[1]} {2^1} = dfrac 1 2)
故原来的式子可以继续魔改:
(a_n = a_{n-1} + dfrac 1 4)
(a_n = a_1 + (n-1)* dfrac 1 4)
算到这一步之后，于是我们开开心心的去写代码，却发现系统提示你(double)类型不能去模
因此我们还要继续改，直到没有分数为止
(4*a_n = 4*a_1 + (n-1))
(4*a_n = 4*dfrac 1 2+n-1 = n+1)
(a_n = dfrac {n+1} 4)
又因为(a_n = dfrac {f[n]} {2^n})
(f[n] = dfrac {n+1} 4 * 2^n)
(f[n] = (n+1)*2^{n-2})
于是我们历经千难万险 终于搞出来一个正常的式子，然后就可以(AC)了（注意特判(n)为(1)的情况）
时间复杂度为(log_n)
给出代码:
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL mod = 998244353;
LL T, n;
inline LL ksm (LL a, LL b) {
if (b == 0) return 1%mod;
if (b&1) return a*ksm(a,b-1)%mod;
LL tmp = ksm(a,b/2)%mod;
return tmp*tmp%mod;
}
int main () {
scanf ("%lld", &T);
while (T --> 0) {
scanf ("%lld", &n);
if(n == 1) cout << 1 << '
';
else cout << (n+1)%mod*ksm(2, n-2)%mod <<'
';
}
return 0;
}
第二题
这题他娘的...某谷数据太水...
说说整体思想吧:
首先我们可以想到，如果确定了一张牌作为某同花顺的结尾，那么整个同花顺是确定的
其次，如果有n张牌，那么最终组成的同花顺一定有n张，另外，对于两张完全相同的牌，一定会更换至少一张
有了以上结论，思路就显而易见了
首先将所有的牌按照花色分开，去重，排序，然后对于相同的花色，用一个队列去维护以每一张牌作结尾时能在序列中的所有牌（即维护首尾指针）
然后统计出这些牌的数量，取较大值，答案就是牌的总数与这个值得差值
其实我也不太明白这个过程...以后要补上这个锅
第三题
正解是他娘的珂朵莉树套(01Trie) 老子不会
打个暴力吸口氧就80分
这还是道省选题，省选自带吸氧，多少感觉这道题作为省选题不太合适