mingw连接顺序
MinGW使用-lxxx来链接库的时候，搜索库的顺序如下：
libxxx.dll.a
xxx.dll.a
libxxx.a
cygxxx.dll (*)
libxxx.dll
xxx.dll
leenldk 发布的文章
OI回忆录
好久以来一直想去填这个坑，苦于作文水平一直拖到现在。这大概是我写的第一篇回忆OI的文章吧。
或许我已经退役了吧，不然也谈不上回忆。这必定是一篇充斥着感情的文章。因为两年，哦不，到现在已经有三年了，其中所发生的事必定不能轻描淡写的一笔带过。这三年间发生了太多的事，使我无法用轻松的心情去写这篇文章。
从三年前的暑假开始，我和其他一些同学提前一年进入高中学习，分叉在各个班级中。
三年前的寒假，我在学了一个学期数学竞赛后最终决定选择OI。放弃的理由？对OI更感兴趣，仅此而已。
巨大的机房中在前几排坐着十几个人，显得有些空旷。漆黑的走廊，老旧的XP系统，踩上去会发出响声的防静电地板，小屋中嗡嗡作响的交换机。我的OI生涯这样开始了。
正值寒假，白天时如果有时间，我便会到机房中去做语法基础题。有时会有些高一的同学在，应该叫学长吧。他们便会探讨一些我根本不懂的题目。刚开始接触新鲜事物时，一切都是那么令人着迷。我梦想着有一天能达到他们的水平。不过想来当时的我过于naive，急于求成，遇到问题时不想着自己解决而是去问别人。把同学包括老师都问得很烦（绝对是我自己的锅，换成现在的我也会很烦的）。OI教会了我发问之前要先试图去自己解决。
假期结束，高中的基础课开始了。我同时兼顾着OI和课内，稍感力不从心。令人感到安慰的是，我们的班主任很支持我们学习OI。中午和小科课时，我会和几个同学去机房做题，没有受到什么阻挠（虽然不午睡的代价是下午第一节课梦游）。此时我们已经转到了高二真 $\cdot$学长们正在使用的小机房。xjk当时是高一，但已经拿了数学联赛和NOIP的一等奖。当时和高二学长们一起脱产学习OI。也许他选择OI的理由和我类似吧。
有时会有一些考试，几乎每次我都被高一的同学碾压。我一直在努力地试图去缩小我和他们的差距。晚上当周老师讲课的时候，有三个人是没有在听的：wfy和wzq——他们在我刚来时已经在学最短路了，和我——进度落后了一个学期，同时在听课的还有crh——一个和我同届的妹子。
在四月，我经历了第一次大型OI考试：JLOI2015。试想一个刚接触OI 2个月的人省选时的心情吧。在那场考试中，wty学长在第一天现场切掉了两题，而我两天加起来只有30。
学期过半时，另一个问题出现了，其实问题一直都在，只是被忙于文化课和OI的我忽略了而已——中考。再次回到初中的枯燥乏味的东西，我不太甘心。因此一直没有放弃OI，中考也恰好可以作为文化课不写作业的理由。
想来我对应试教育的不满从初中时就已经开始了。所谓中考与高考不知扼杀了多少人的梦想，我想如果每个有梦想的人都有实现梦想的机会，或许此刻在写这篇文章的就是另一个人了吧。（如果对应试教育没有偏见请将以上以及以后出现的此类言论当成一个失败者的借口）
我想我一定是幸运的吧，可以不再拼死拼活的去争取高考的一点分数。如果有人问我没有完整的高中生活是否有遗憾，至少现在我的答案是没有。
中考结束，一切有惊无险。我终于成为了一名高中生。那个暑假，我每天都从早到晚在机房中做题。假期作业保持着刚发时的空白。感觉自己终于有了一点进步，考试时终于不再垫底了。这让我稍微有了一点信心。
这个假期我经历了第一次外出培训，培训时讲了一些我当时觉得很厉害的算法。培训恰逢国赛。我听说了wty学长和wyf学长进入集训队的消息，ygy获得了银牌，xjk拿了D类铜牌。他们是学校OI史上第一届集训队，这对我来说是很大的激励。
假期再次结束，wzq和wfy在学期开始时脱产了。我感到有些寂寞，从教室向机房的队伍中少了一个人（wfy当时和我不是同班）。而我也更加地感到力不从心。有一段时间我晚上从机房回家就会很困，然后第二天早晨3点起来写一些作业（这个三点的闹钟还在培训时把周老师吵醒过一次）。白天在学校有一半的课上会困。我觉得我无法再同时兼顾OI和文化课了。因此我决定脱产。由于老师们的支持，最终父母也同意了我的决定。
我曾经好多次幻想过脱产之后的时光，像梦一般的时光。每天可以没有文化课的苦恼，可以有充足的睡眠，可以全身心投入到OI之中。但这同样有着极大的风险：如果最终没有取得任何成果，那么等待着的将是文化课和高考，而长期停止文化课的学习，试图把落下的补回来付出的代价可想而知。
一边是梦想，一边是煎熬。我能做的只有尽我所能去靠近那个遥不可及的梦想。
脱产后的我接触到了省选级别的知识点，平衡树，树套树，一道稍有难度的题就可能耗费我一天的时间。调试的过程是艰难的。一处随手犯下的错误，找出却需要百倍的努力。思路上的一点错误，可能需要将整个代码写完后才能发现。
我脱产不久后，LLX也脱产了。和我一样从省选知识点学起。11月的深秋是NOIP的时间。NOIP一个月之前机房中迎来了新的一员，或许应该说是最老的一员回归了吧。dzn和我一样提前一年进入高中，是我的上一届。在15年的省选中没能进入省队，NOIP前重新回到机房准备新的一轮。
NOIP一周前其他高一的同学也脱产来准备NOIP。机房的白天也变得热闹起来。但我内心中知道这热闹无法延续。对很多人来说，NOIP的结束就是OI生涯的结束吧。
NOIP开始，我的第一场NOIP。day1前两个题做得比较容易，T3见过一道类似的搜索，如果出到模拟赛里就好了呢，我这样想。但代码能力有限，最终没有调出来。day2T1很容易，T2的dp没有想出来，写了一个70分的暴力（然而访问了负索引其实只有40），然后T3同样最终没有调出来。第一场NOIP，最终以435分这样的分数告终了。wzq在NOIP中发挥失常，我想是紧张导致的吧。
在决定命运的时刻，谁不会紧张呢？越告诉自己不要紧张，反而却越紧张，而OI考试又偏偏是一个需要静下心来的地方，思考题目需要静下心来，写题和调试时更需要静下心来。但这往往是不可能的。旁边人敲击键盘的声音，不停流逝的时间，没有通过的样例，对拍中的一组错误。时刻面临着选择，放弃当前正在调试的题相当于放弃之前一小时甚至几小时的成果，而其他题目又未必会有什么进展。但如果不放弃呢？在你调试的时候别人可能已经在其他题目上有了进展，继续调试不知会花费多长时间，甚至如果到考试结束还没有完成，结果可想而知。即使过了样例，一个隐藏的错误可能会使所有努力付之东流。正因如此，几乎所有考试中，或多或少都会有失误或后悔的地方。
wzq最终选择了退役，他一定是不甘和无奈的吧，毕竟一年半的努力，换来了这样的结果。这是我第一次经历OI中的告别。我也许在内心中知道以后还要经历很多这样的告别。
但这只是暂别呢，是吧？也许在大学，也许在更远的未来，我们还会相遇。
相逢是问候，分手是祝愿。
因为NOIP的成绩不错，而省队有一个女生的名额，因此QT加入了脱产的队伍。
接下来是WC。讲的东西根本没有听懂，更多的时候是看wfy打东方或和LLX玩一个解迷游戏。最终JDFZ所有人的成绩巧合般地组成了一个30到90公差为10的等差数列。没错，我就是那个30。90分的dzn拿到了Au。
接下来的时光在做题与考试中度过。每周六上午是考试，考完试后所有人会一起去桂林路吃饭。那是一段令人怀念的时光。汉堡王，生煎，米伴（这个只有我比较喜欢）。饭后大家一起聊天走回学校。
那段时间的考试，我偶尔可以靠一些奇怪的做法过掉一些题。到了互策的时候就完全变成了互相伤害。而在不知不觉中，省选临近了。
脱产的男生有五个人，而其中最多只有四个人能进入省队。而由于吉林省的强校只有两所，因此对于我们两所学校来说省选完全是校内的竞争。两所学校之间只有AB名额的竞争。我一直认为那个不能进入省队的人应该是我。因为按理来讲，我的水平在五人中最低，并且学籍是高一，还有一年的时间。大概所有人都是这样想的吧，因此学校并没有申请C类名额。
省选day1，我全程在写T2，在考试快要结束的时候调了出来，但最终因为没开long long只有40分。wfy是全场rank1，而dzn却由于失误只有30分。day2我决定不去刚一道题，因此每道题写了一些暴力。最后加起来有一百多分。wfy又是rank1，获得称号万队长。而dzn再次失误还是只有30分。我竟然进了省队。但我很清楚这不是因为我有进入省队的实力，而只是因为实力在我之上的dzn的失误。我所能做的只有继续努力。
接下来是APIO和CTSC。这几场考试对我来说就是暴力大赛而已。晚上我们在五星级宾馆里玩三国杀，很开心。我在APIO卡线拿了银牌，CTSC铜牌。
省选之后的时间过得飞快，紧接着就是清北夏令营。我，xjk，wfy，LLX去了清华，而QT和dzn去了北大。我当时是抱着今年先感受一下的想法参加的夏令营。但题格外顺手。考试时先看了一下T1，感觉不太会，于是去看T2，发现T2很简单，这给了我一些信心，T3是提答。写完T2后回头看T1，想了一个dp，虽然复杂度比较高但常数挺小的。写完之后去做了一下提答。想来这可能是我OI生涯省选级别考试中做得最顺的一次。最后我，xjk，wfy拿到了一本线，而LLX因为没有做上T1只拿到了国赛前一百名降60。
dzn在北大夏令营拿到了rank1，但最终由于是D类，只有降60分和国赛前一百名降一本。QT拿到了前150降20。
想来这次的确算是JDFZOI的辉煌了吧。在一个一本率92%的学校，考上一本线不是一件难事。当时的确感觉一年多的努力没有白费。
但我的目标仅仅是上一所大学吗？我深知自己现在并没有一本线的实力，拿到一本线可以说是因为努力但更多的应该是运气的因素。我需要证明自己，证明自己的确有这样的实力。不然到了大学以后仍然别无所长。我这样告诉自己，但仍然比以前松懈了不少。
接下来到国赛前的一个月中，我们一起到安徽培训。培训基本就是每天考一场试。可能是由于夏令营的成绩比较好吧，培训的时候我们比较松懈，并没有国赛前的紧张气氛。晚上和xjk一起看GOT，LLX一个人玩游戏。隔壁wfy打dota，dzn看番。半夜声音太大时还会吵到周老师。
最后到了16年国赛，省选时的一切再次重演，D1T1所有人都拿了95分然后跑路，T2当场想了一个做法，很迷，也不太好写，但还是勇敢地硬着头皮去写，最后没调过大样例。T3根本没碰。最后发现T2，T3暴力写全每道是70+。D2没管太多写了两题暴力去搞提答。最后193分跑路。
我一直以为在国赛中必须切题才能拿到一个比较好的名次，其实在所有比赛中，如果能做到没有遗憾，那么最终一定可以得到一个理想的结果。
xjk进了集训队，dzn进了前一百，QT拿到了武大一本，wfy差一点没有拿到金牌，LLX没有进到前一百名，而我只拿到了铜牌。
一切尘埃落定，大概每个人都有或多或少的遗憾吧。这就是考试的常态吧。我面对学文化课或是继续脱产的选择没有犹豫。今年我只是没有足够的实力，但我相信再经过一年的努力，我可以证明自己。并且，我还是不想学文化课的。只是觉得太忙，也有些枯燥。
和大家在长江坐船玩了几天。回到学校后，新的一轮OI年开始了。
每天的脱产生活还算愉快，白天在学校做一些题，晚上回家之后就干些别的事情。但是总觉得水平没有太大的提升。
渐渐的，脱产的人多了起来。crh，wyx，lhy，mrc。我还在我的老位置上，而机房渐渐重新热闹起来。而这又能持续多久呢？每天在学校做一些题，用来给自己的空虚一点安慰。我或许有些厌倦了呢。功利地去做一件事情，不免会心生厌倦。而如果没有了功利，又如何坚持呢？当当初的热情消失的时候，对坚持的事物，又剩下些什么呢？
我给自己的理由是，我不想回到教室，回到繁多的课业。我想有属于自己的时间，我想证明自己的能力。于是我坚持着，没有了那份热情，也缺了几分斗志。
又是一年的NOIP。没有顾虑，也没什么压力，两天考完之后感觉没什么问题。出成绩时一点小担心吧。D2T3没清数组挂了90。算是个遗憾吧，但又哪有没有遗憾的考试呢？我更庆幸的是没有更大的遗憾。
今年学校的成绩有些惨淡。lhy第二天文件名写错爆零了。其他人还在继续脱产。一天好像是前一天的重复，一周好像是前一周的重复。在做题，考试，讲课间重复。中间考了一场WC，还是老样子吧。讲课时开始尝试听一听，听不下去也就弃疗了。看xjk推steins gate。WC的考试，没什么参考价值吧，拿一块银牌也就笑笑走人了。
时间过得飞快，又到了4月的省选。其实也没有那么在意吧。
血崩
————简单题不会，暴力打不对
最后靠NOIP的分强行进了A队，垫底。我思考，最后得出结论——我还太菜了。这种水平根本没有自满的资本。删了所有手机电脑游戏。还有不到三个月，我不能让自己为虚度这三个月而后悔。
学校成绩惨淡。mrc，czy都退役了。crh B队，wyx准备买D。机房又一下子冷清下来。在OI中告别已是常态了吧。生活不会事事如愿，我们在世界面前是弱小的，无法改变什么。只能做出自己微薄的努力，去祈求一点未必会有的回报。这世界既不温柔，也不正确。
接着便是APIO和CTSC。可能有些紧张了吧，又是两块银牌。也算在北京玩了几天。
国赛前的一个月在湖南度过，发现自己水平果然还是很低。在这一个月里认识了大佬们，学了很多东西。
最后的国赛。
这可能是我最后的OI比赛了吧。day1写了三个暴力，拿了206分。可能是暴力不太好写吧，发现进了前50。挺开心的，打了一天红警。day2先写了T1的2SAT，然后用力写了一下T2，过了大样例，然后写了T3的暴力。感觉自己很稳。然后决定拍一下T1，GG ，我发现我似乎把2SAT记错了。用力的改，直到考试结束。。。应该能骗到一些分吧，我这样安慰自己。
下午看成绩，
5+100+20=125
T1完美爆炸
一道暴力50+的题我拿了5分，还是无解的5分
OI再见
很不甘心，但已经结束了。一路走来没有什么后悔的地方。
上一年无聊的课内课，然后考一个一本。已经没有什么好害怕的了。
去听讲题，说是去听讲题，其实坐在座位上根本听不进去，T1 A了70多人，呵呵。
然后发成绩单，集训队线431，我TM，我TM，我TM竟然踩了集训队的线！
然后看名单，上面和我同分，我rank51？
隐约记得有一条规定是国赛同分按NOIP成绩计算，然后我成了这个规定适用的第一人？
感觉自己带着莫名喜感，NOI搞笑选手，呵呵。
假期玩了半个多月，开始上学。上课听听课，偶尔犯困，偶尔写写作业。
上了一个月的课，接到通知说我进集训队了？gzz因为学籍的问题集训队资格被取消了？
虽然感觉不太公平，实力在我之上的人因为学籍的问题失去了资格。但更多的是庆幸吧。庆幸自己终于可以不再学基础课，庆幸自己有时间做自己的事情。
不知道坑了多长时间，一直想去写，又迟迟没有动笔，又写了一半弃坑。今天终于补完了，匆忙收笔，有些遗憾，但凡事多少会有遗憾吧。
最后，感谢家长，老师，同学们长期的支持和帮助。感谢你能看完这篇流水账。
以上。
我的作业：codeforces 755G
一.题目大意
一行有$$n$$个球，现在将这些球分成$$K$$组，每组可以有一个球或相邻两个球。一个球只能在至多一个组中。求对于$$1\le K\le m$$的所有$$K$$分别有多少种分组方法。答案对$$998244353$$取模。
$$1\le n \le 10^9$$
$$1\le K \le 2^{15}$$
二.解题报告
算法1
设$$f[i][j]$$表示把$$i$$个球分成$$j$$组的方案数。
则$$f[i][j]=f[i-1][j-1]+f[i-2][j-1]+f[i-1][j]$$
最终答案为$$f[n][1...m]$$
时间复杂度$$O(nm)$$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5100,mod=998244353;
int n,m;
int f[N][N];
int main()
{
//freopen("tt.in","r",stdin);
scanf("%d%d",&n,&m);
f[1][1]=f[1][0]=f[0][0]=1;
for(int i=2;i<=n;i++)
{
f[i][0]=1;
for(int j=1;j<=i&&j<=m;j++)
f[i][j]=((f[i-1][j-1]+f[i-2][j-1])%mod+f[i-1][j])%mod;
}
for(int i=1;i<=m;i++)
printf("%d ",f[n][i]);
return 0;
}
算法2
设$$a(K)$$表示分为$$K$$组的答案。枚举相邻两个一组的个数$$i$$
$$a(K)=\sum\limits_{i=0}^{min(K,n-K)}C_{n-i}^K C_K^i$$
$$=\sum\limits_{i=0}^{min(K,n-K)} \frac{(n-i)!}{(n-i-K)!i!(K-i)!}$$
其中$$\frac{1}{i!}$$和$$\frac{1}{(K-i)!}$$可以通过$$O(m)$$预处理每次$$O(1)$$计算。
设$$g(i,K) = \frac{(n-i)!}{(n-i-K)!}$$
则$$g(i,K) = g(i,K-1)*(n-i-K+1)$$
对于每个$$K$$可以$$O(m)$$处理。
时间复杂度 $$O(m^2)$$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=21000,mod=998244353;
int n,m,ans;
int jc[N],njc[N],g[N];
int qpow(int x,int y)
{
int ret=1;
while(y)
{
if(y&1)ret=(ll)ret*x%mod;
x=(ll)x*x%mod;y>>=1;
}
return ret;
}
void init()
{
jc[0]=njc[0]=1;
for(int i=1;i<=m;i++)jc[i]=(ll)jc[i-1]*i%mod;
njc[m]=qpow(jc[m],mod-2);
for(int i=m-1;i>=1;i--)
njc[i]=(ll)njc[i+1]*(i+1)%mod;
}
int main()
{
//freopen("tt.in","r",stdin);
scanf("%d%d",&n,&m);
init();
for(int i=0;i<=m;i++)g[i]=1;
for(int K=1;K<=m;K++)
{
ans=0;
for(int i=0;i<=m;i++)
g[i]=(ll)g[i]*(n-i-K+1)%mod;
for(int i=0;i<=K&&i<=n-K;i++)
ans=(ans+(ll)g[i]*njc[i]%mod*njc[K-i]%mod)%mod;
printf("%d ",ans);
}
return 0;
}
算法3
在算法1基础上将$$f[i][0...m]$$看成一个关于x的多项式，称为$$f[i]$$
通过算法1可知如果已知$$f[n],f[n+1]$$可以$$O(m)$$求出$$f[n+2]$$
考虑在已知$$f[a],f[b],f[a-1],f[b-1]$$时计算$$f[a+b]$$
$$f[a+b]$$即为将长度为$$a$$和长度为$$b$$的两段连接起来得到的。
在连接处有两种情况，如果有一个两个球的组跨过连接处那么为$$f[a-1] * [b-1]$$（乘号为多项式卷积）
否则为$$f[a] * f[b]$$
因此$$f[a+b]=f[a-1] * f[b-1]+f[a] * f[b]$$
卷积可以通过NTT在$$O(m \log m)$$计算
因此可以在$$O(m\log m)$$通过$$f[a],f[b],f[a-1],f[b-1]$$计算$$f[a+b]$$
因此如果已知$$f[a-2],f[a-1],f[a]$$以及$$f[b-2],f[b-1],f[b]$$
可以通过$$f[a-2],f[a-1]$$，$$f[b-2],f[b-1]$$计算$$f[a+b-2]$$
通过$$f[a-1],f[a]$$，$$f[b-2],f[b-1]$$计算$$f[a+b-1]$$
通过$$f[a+b-2],f[a+b-1]$$计算$$f[a+b]$$
因此可以用倍增来计算$$f[n]$$
时间复杂度$$O(m\log n\log m)$$
#include <bits/stdc++.h>
using namespace std;
#define N (1<<16)+10
#define mod 998244353
#define ll long long
int len,n,m,flag;
int qpow(int x,int y)
{
int ret=1;
while(y)
{
if(y&1)ret=(ll)ret*x%mod;
x=(ll)x*x%mod;y>>=1;
}
return ret;
}
void NTT(int *a,int len,int type)
{
for(int i=0,t=0;i<len;i++)
{
if(i>t)swap(a[i],a[t]);
for(int j=len>>1;(t^=j)<j;j>>=1);
}
for(int i=2;i<=len;i<<=1)
{
int wn=qpow(3,(mod-1)/i);
for(int j=0;j<len;j+=i)
{
int w=1,t;
for(int k=0;k<i>>1;k++,w=(ll)w*wn%mod)
{
t=(ll)a[j+k+(i>>1)]*w%mod;
a[j+k+(i>>1)]=(a[j+k]-t+mod)%mod;
a[j+k]=(a[j+k]+t)%mod;
}
}
}
if(type==-1)
{
for(int i=1;i<=len>>1;i++)swap(a[i],a[len-i]);
int t=qpow(len,mod-2);
for(int i=0;i<len;i++)a[i]=(ll)a[i]*t%mod;
}
}
struct node
{
int a[N],b[N];
void dft()
{
memset(b,0,sizeof(b));
for(int i=0;i<len>>1;i++)b[i]=a[i];
NTT(b,len,1);
}
}a1,a2,a3,b1,b2,b3,ans,ans1,ans2,c1,c2;
void mul(node &r1,const node &r2,const node &r3)
{
for(int i=0;i<len;i++)
r1.b[i]=r1.a[i]=(ll)r2.b[i]*r3.b[i]%mod;
NTT(r1.a,len,-1);
for(int i=len>>1;i<len;i++)r1.a[i]=0;
}
void inv(node &r1,const node &r2,const node &r3)
{
r1.a[0]=1;
for(int i=1;i<len>>1;i++)
r1.a[i]=(r2.a[i]+r3.a[i-1])%mod;
r1.dft();
}
int main()
{
//freopen("tt.in","r",stdin);
scanf("%d%d",&n,&m);
for(len=1;len<(m+1)<<1;len<<=1);
a2.a[0]=1;a3.a[0]=1;a3.a[1]=1;
a1.dft();a2.dft();a3.dft();
for(;n;n>>=1)
{
if(n&1)
{
if(!flag)
{
ans=a3;ans1=a2;ans2=a1;
flag=1;
}
else
{
mul(c1,ans,a3);mul(c2,ans1,a2);
inv(ans,c1,c2);
mul(c1,ans1,a3);mul(c2,ans2,a2);
inv(ans1,c1,c2);
for(int i=0;i<len>>1;i++)
ans2.a[i]=((ans.a[i+1]-ans1.a[i+1]+mod)%mod-ans1.a[i]+mod)%mod;
ans2.dft();
}
}
mul(c1,a2,a2);mul(c2,a1,a1);
inv(b1,c1,c2);
mul(c1,a3,a3);mul(c2,a2,a2);
inv(b3,c1,c2);
b2.a[0]=1;
for(int i=1;i<len>>1;i++)
b2.a[i]=((b3.a[i]-b2.a[i-1]+mod)%mod-b1.a[i-1]+mod)%mod;
b2.dft();
a1=b1;a2=b2;a3=b3;
}
for(int i=1;i<=m;i++)
printf("%d ",ans.a[i]);
return 0;
}
算法4
由算法3知$$f[i]=(x+1)f[i-1]+x f[i-2]$$
求$$f[i]$$的通项公式：
设$$f[i]=C_1 T_1(x)^i+C_2 T_2(x)^i$$
其中$$T_1(x),T_2(x)$$为关于$$T(x)$$的方程$$T(x)^2=(x+1)T(x)+x$$的两根。
解得$$
\left\{
\begin{aligned}
T_1(x)=\frac{x+1+\sqrt{x^2+6x+1}}{2}\\
T_2(x)=\frac{x+1-\sqrt{x^2+6x+1}}{2}
\end{aligned}
\right.
$$
将$$f[0]=1,f[1]=1+x$$带入
解得$$
\left\{
\begin{aligned}
C_1=\frac{T_1(x)}{T_1(x)-T_2(x)}\\
C_2=\frac{T_2(x)}{T_2(x)-T_1(x)}
\end{aligned}
\right.
$$
因此$$f[i]=\frac{T_1(x)^{i+1}-T_2(x)^{i+1}}{T_1(x)-T_2(x)}$$
$$ = \frac{(\frac{x+1+\sqrt{x^2+6x+1}}{2})^{n+1}-(\frac{x+1-\sqrt{x^2+6x+1}}{2})^{n+1}}{\sqrt{x^2+6x+1}}$$
其中$$(\frac{x+1-\sqrt{x^2+6x+1}}{2})^{n+1}$$最低次项大于$$n$$，因此可以舍掉
通过多项式开根，多项式求逆可以$$O(m\log m)$$计算$$\frac{x+1+\sqrt{x^2+6x+1}}{2}$$以及$$\frac{1}{\sqrt{x^2+6x+1}}$$
通过多项式exp以及多项式取ln可以$$O(m\log m)$$计算一个多项式的$$n+1$$次幂
时间复杂度$$O(m\log m)$$
#include <bits/stdc++.h>
using namespace std;
#define N (1<<16)+10
#define ll long long
#define mod 998244353
const int inv2=499122177;
int n,m,len;
int tmp[N],sq[N],inv_sq[N],rt1[N],ln1[N],a[N],ans[N],inv[N];
int test1[N],test2[N],test3[N];
int qpow(int x,int y)
{
int ret=1;
while(y)
{
if(y&1)ret=(ll)ret*x%mod;
x=(ll)x*x%mod;y>>=1;
}
return ret;
}
void NTT(int *a,int len,int type)
{
for(int i=0,t=0;i<len;i++)
{
if(i<t)swap(a[i],a[t]);
for(int j=len>>1;(t^=j)<j;j>>=1);
}
for(int i=2;i<=len;i<<=1)
{
int wn=qpow(3,(mod-1)/i);
for(int j=0;j<len;j+=i)
{
int w=1,t;
for(int k=0;k<i>>1;k++,w=(ll)w*wn%mod)
{
t=(ll)a[j+k+(i>>1)]*w%mod;
a[j+k+(i>>1)]=(a[j+k]-t+mod)%mod;
a[j+k]=(a[j+k]+t)%mod;
}
}
}
if(type==-1)
{
for(int i=1;i<len>>1;i++)swap(a[i],a[len-i]);
int t=qpow(len,mod-2);
for(int i=0;i<len;i++)a[i]=(ll)a[i]*t%mod;
}
}
////////////////
void test_root(int *a,int len)
{
memset(test1,0,sizeof(test1));
for(int i=0;i<len;i++)
test1[i]=a[i];
NTT(test1,len<<1,1);
for(int i=0;i<len<<1;i++)
test1[i]=(ll)test1[i]*test1[i]%mod;
NTT(test1,len<<1,-1);
for(int i=0;i<len;i++)
printf("#%d ",test1[i]);
puts("");
}
void test_inv(int *a,int *b,int len)
{
memset(test1,0,sizeof(test1));
memset(test2,0,sizeof(test2));
for(int i=0;i<len;i++)
test1[i]=a[i],test2[i]=b[i];
NTT(test1,len<<1,1);
NTT(test2,len<<1,1);
for(int i=0;i<len<<1;i++)
test3[i]=(ll)test1[i]*test2[i]%mod;
NTT(test3,len<<1,-1);
for(int i=0;i<len;i++)
printf("#%d ",test3[i]);
puts("");
}
////////////////
void get_inv(int *a,int *b,int len)
{
static int tmp[N];
if(len==1)
{
b[0]=qpow(a[0],mod-2);
return;
}
get_inv(a,b,len>>1);
for(int i=0;i<len;i++)tmp[i]=a[i];
for(int i=len;i<len<<1;i++)tmp[i]=0;
NTT(tmp,len<<1,1);
NTT(b,len<<1,1);
for(int i=0;i<len<<1;i++)
b[i]=(ll)b[i]*(2-(ll)b[i]*tmp[i]%mod+mod)%mod;
NTT(b,len<<1,-1);
for(int i=len;i<len<<1;i++)b[i]=0;
}
void get_root(int *a,int *b,int len)
{
static int invb[N],tmp[N];
if(len==1){b[0]=1;return;}
get_root(a,b,len>>1);
for(int i=0;i<len<<1;i++)invb[i]=0;
get_inv(b,invb,len);
for(int i=0;i<len;i++)tmp[i]=a[i];
for(int i=len;i<len<<1;i++)tmp[i]=0;
NTT(tmp,len<<1,1);
NTT(b,len<<1,1);
NTT(invb,len<<1,1);
for(int i=0;i<len<<1;i++)
b[i]=(ll)inv2*(b[i]+(ll)tmp[i]*invb[i]%mod)%mod;
NTT(b,len<<1,-1);
for(int i=len;i<len<<1;i++)b[i]=0;
}
void get_ln(int *a,int *b,int len)
{
static int inva[N],a1[N];
for(int i=0;i<len<<1;i++)inva[i]=0;
get_inv(a,inva,len);
for(int i=0;i<len;i++)a1[i]=(ll)(i+1)*a[i+1]%mod;
for(int i=len;i<len<<1;i++)a1[i]=0;
NTT(a1,len<<1,1);
NTT(inva,len<<1,1);
for(int i=0;i<len<<1;i++)a1[i]=(ll)a1[i]*inva[i]%mod;
NTT(a1,len<<1,-1);
b[0]=0;
for(int i=1;i<len;i++)
b[i]=(ll)a1[i-1]*inv[i]%mod;
for(int i=len;i<len<<1;i++)b[i]=0;
}
void get_exp(int *a,int *b,int len)
{
static int lnb[N],tmp[N];
if(len==1){b[0]=1;return;}
get_exp(a,b,len>>1);
for(int i=0;i<len<<1;i++)lnb[i]=0;
get_ln(b,lnb,len);
for(int i=0;i<len;i++)tmp[i]=(a[i]-lnb[i]+mod)%mod;
tmp[0]++;
for(int i=len;i<len<<1;i++)tmp[i]=0;
NTT(b,len<<1,1);
NTT(tmp,len<<1,1);
for(int i=0;i<len<<1;i++)
b[i]=(ll)b[i]*tmp[i]%mod;
NTT(b,len<<1,-1);
for(int i=len;i<len<<1;i++)b[i]=0;
}
int main()
{
//freopen("tt.in","r",stdin);
scanf("%d%d",&n,&m);
for(len=1;len<=m;len<<=1);
for(int i=1;i<len;i++)inv[i]=qpow(i,mod-2);
tmp[0]=1;tmp[1]=6;tmp[2]=1;
get_root(tmp,sq,len);
get_inv(sq,inv_sq,len);
rt1[0]=rt1[1]=1;
for(int i=0;i<len;i++)
rt1[i]=(ll)(rt1[i]+sq[i])%mod*inv2%mod;
get_ln(rt1,ln1,len);
for(int i=0;i<len;i++)
ln1[i]=(ll)ln1[i]*(n+1)%mod;
get_exp(ln1,a,len);
NTT(inv_sq,len<<1,1);
NTT(a,len<<1,1);
for(int i=0;i<len<<1;i++)
ans[i]=(ll)a[i]*inv_sq[i]%mod;
NTT(ans,len<<1,-1);
for(int i=1;i<=m;i++)
printf("%d ",i>n ? 0:ans[i]);
return 0;
}
arc077f
题意：定义一个偶串为一个可写为一个字符串复制两次的字符串。S为一个偶串，定义f(S)为在S后加最少的字符（大于等于1个）使S成为的偶串。
设f(SS)=STST，g(S)=ST。则T为S最小的周期。
$$g(ST)=STT(|T| \\mid |S|) $$
$$g(ST)=STS(|T| \\nmid |S|)$$
#include <bits/stdc++.h>
using namespace std;
const int N=210000;
#define ll long long
char s[N];
ll L,R;
int nex[N];
ll len[210];
struct node
{
ll a[26];
void init(int x)
{
for(int i=1;i<=x;i++)
a[s[i]-'a']++;
}
friend node operator + (const node &r1,const node &r2)
{
node ret;
for(int i=0;i<26;i++)
ret.a[i]=r1.a[i]+r2.a[i];
return ret;
}
friend node operator - (const node &r1,const node &r2)
{
node ret;
for(int i=0;i<26;i++)
ret.a[i]=r1.a[i]-r2.a[i];
return ret;
}
void print()
{
for(int i=0;i<26;i++)
printf("%lld ",a[i]);
puts("");
}
}v[210];
node calc(ll x)
{
int p;
for(p=1;;p++)
if(len[p]>=x)break;
node ret,t;
memset(&ret,0,sizeof(ret));
memset(&t,0,sizeof(t));
for(;p>=1;p--)
if(len[p]<=x)
{
ret=ret+v[p];
x-=len[p];
}
t.init(x);
ret=ret+t;
return ret;
}
int main()
{
//freopen("tt.in","r",stdin);
scanf("%s%lld%lld",s+1,&L,&R);
len[2]=strlen(s+1)/2;
nex[1]=0;
for(int i=2,j=0;i<=len[2];i++)
{
while(j&&s[j+1]!=s[i])
j=nex[j];
if(s[j+1]==s[i])j++;
nex[i]=j;
}
len[1]=len[2]-nex[len[2]];
v[1].init(len[1]);
v[2].init(len[2]);
for(int i=3;;i++)
{
len[i]=len[i-1]+len[i-2];
v[i]=v[i-1]+v[i-2];
if(len[i]>=R)break;
}
(calc(R)-calc(L-1)).print();
return 0;
}
agc002d
整体二分裸题
#include <bits/stdc++.h>
using namespace std;
#define N 110000
#define PA pair<int,int>
int n,m,Q;
int X[N],Y[N],ans[N];
struct node
{
int x,y,tar,pos;
}a[N],b[N];
struct Ufs
{
int now;
int fa[N],size[N],mem[N];
void init()
{
for(int i=1;i<=n;i++)
fa[i]=i,size[i]=1;
}
int find(int x){return fa[x]==x ? x : find(fa[x]);}
void move(int tar)
{
int x,y;
while(now<tar)
{
now++;
if((x=find(X[now]))==(y=find(Y[now])))
mem[now]=0;
else
{
if(size[y]>size[x])swap(x,y);
size[x]+=size[y];
fa[y]=x;
mem[now]=y;
}
}
while(now>tar)
{
if(x=mem[now])
{
size[fa[x]]-=size[x];
fa[x]=x;
}
now--;
}
}
int calc(int x,int y)
{
x=find(x);y=find(y);
if(x==y)return size[x];
return size[x]+size[y];
}
}ufs;
void solve(int l1,int r1,int l2,int r2)
{
if(l2>r2)return;
if(l1==r1)
{
for(int i=l2;i<=r2;i++)
ans[a[i].pos]=l1;
return;
}
int mid=(l1+r1)>>1,lm=l2,rm=r2;
ufs.move(mid);
for(int i=l2;i<=r2;i++)
{
if(ufs.calc(a[i].x,a[i].y)>=a[i].tar)
b[lm++]=a[i];
else b[rm--]=a[i];
}
for(int i=l2;i<=r2;i++)a[i]=b[i];
solve(l1,mid,l2,lm-1);
solve(mid+1,r1,rm+1,r2);
}
int main()
{
//freopen("tt.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d",&X[i],&Y[i]);
scanf("%d",&Q);
for(int i=1;i<=Q;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].tar);
a[i].pos=i;
}
ufs.init();
solve(1,m,1,Q);
for(int i=1;i<=Q;i++)
printf("%d\n",ans[i]);
return 0;
}