7.23集训
上午
考试了 \(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\)?
就很不舒服嘛....
下面说一说关于这道题，我是怎么推的式子吧
1 | 48 |
我们设最左边一列为\(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\)
给出代码: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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 << '\n';
else cout << (n+1)%mod*ksm(2, n-2)%mod <<'\n';
}
return 0;
}
第二题
这题他娘的...某谷数据太水...
说说整体思想吧:
首先我们可以想到，如果确定了一张牌作为某同花顺的结尾，那么整个同花顺是确定的
其次，如果有n张牌，那么最终组成的同花顺一定有n张，另外，对于两张完全相同的牌，一定会更换至少一张
有了以上结论，思路就显而易见了
首先将所有的牌按照花色分开，去重，排序，然后对于相同的花色，用一个队列去维护以每一张牌作结尾时能在序列中的所有牌（即维护首尾指针）
然后统计出这些牌的数量，取较大值，答案就是牌的总数与这个值得差值
其实我也不太明白这个过程...以后要补上这个锅
第三题
正解是他娘的珂朵莉树套\(01Trie\) 老子不会
打个暴力吸口氧就80分
这还是道省选题，省选自带吸氧，多少感觉这道题作为省选题不太合适