生活还得继续.

12省联考D2T2

首先看到链的部分分秒切了之后应该想想怎么启发正解啊。。。

结论：将两条链（去掉根）从大到小排序，让$a_i$和$b_i$匹配。

证明可以用调整法（微扰法？）。

然后就得到15分。

然后想想如何把这种做法推广到树上。

然后我一开始想把根到叶子的每条链都排个序，后来想想不大对。

应该先把子树合并成一条链（然后可以得到一个结论就是一个子树需要的块数是它的最大深度）。

合并的顺序是从下往上，时间复杂度是$O(n^2)$

P3711 仓鼠的数学题

题目背景

请注意本题时限1s，开启O2优化，你可能需要输入输出优化

题目描述

仓鼠在某oj上看到了一个问题，设$Sk(x)=\sum{i=0}^x i^k$，这个题输入$a0,a_1…a_n$，假设$0^0=1$，要求计算$\sum{k=0}^{n}S_k(x)a_k$。

仓鼠想了两秒就秒了这个题，他发现数据范围居然只有1000，就顺手加了两个0。

但是仓鼠懒得造数据了，就把这道题丢给了你。

输入输出格式

输入格式：

第一行输入一个整数$n$。

第一行输入$n+1$个空格分隔的非负整数。分别是$a_0 \cdots a_n$。

输出格式：

输出n+2n+2个空格分隔的整数，表示答案多项式的各项系数$c0…c{n+1}$，表示答案多项式为$\sum_{i=0}^{n+1}c_ix^i$。多项式的系数对$998244353$取模。

可以证明多项式的次数$\leq n+1$。

输入输出样例

输入样例#1：

1
2

2
3 3 3

输出样例#1：

3 5 3 1

说明

对于100%的数据，$1 \leq n \leq 250000$

输入和输出多项式系数均为模$998244353$意义下，为$[0,998244352]$的非负整数。

题解

~~一开始由于数学差没看出是个多项式~~

然后发现就是$n$个等幂求和，我以前推导过。如果不会Bernulli数的推导可以使用前面项来递推计算。

然后$n$个多项式相加。

计算复杂度是$O(n^3)$

多项式算法优化一个$n$没有用。

大概是个生成函数？？？

想5分钟想不出来就看看题解吧qwq。

看了看题解发现数学太差不可做.jpg

算了，我开始研究怎么搞定删除大文件吧。

好像有两种方法，一种是使用自带的git-filter-branch，看上去非常麻烦的样子。

另一种是使用BFG工具，需要安装JAVA。。。

这玩意干嘛整删除都这么困难啊。。。

先复习一下git基本操作，新建一个库，链接到我的一个小号，然后自己瞎几把试了试终于连上了可以push。

然后放了个大于100MB的等待被拒绝后试试删除.（传的很慢。。。github为啥限制速度这么过分啊）

Java是真的麻烦，不用了现在开始看git自带的。。

试了试可以了https://www.hollischuang.com/archives/1708

1	git rev-list --objects --all

看看里面的大文件~~（自己知道就得了）~~

1	git filter-branch --force --index-filter 'git rm -rf --cached --ignore-unmatch <BIG FILE>' --prune-empty --tag-name-filter cat -- --all

是参数，好像必须得写文件名。

如果显示 xxxxx unchanged, 说明repo里没有找到该文件, 请检查路径和文件名是否正确，重复上面的脚本，把所有你想删除的文件都删掉。

然后就可以

1	git push <NAME> master

最后为了释放空间

rm -rf .git/refs/original/

git reflog expire --expire=now --all

git gc --prune=now

对于普通库算是比较简单的解决方案了，不知道对于hexo行不行哦。（提早回去半小时修一修）

哦对了，hexo下如果我是想删掉download目录下的大文件，还是要测试一下才可以。

再进行10分钟测试就干点别的。比如做做题什么的。

发现一个问题，如果是删除一个文件夹里的东西它会把整个文件夹给删了？？不知到是不是因为文件夹里没有其它文件？
还得再测试一次，真烦。

我这次再download里放两个文件，假如我删除其中一个会导致另一个也被删除那这个恐怕就太危险了!

突然发现github现在跑的飞快，可由于某些原因我还是感觉挂SS有安全感，尽管慢10倍。。。。

然后回家成功修好了~~（忘了关电脑放了一晚上）~~