AcrossTheSky's Blog

完结撒花！！

NOIP滚粗...
NOI滚粗...
WC滚粗...

今年还有ZJOI CTSC APIO.. 以及..NOI 感觉压力好大啊..

以下是滚粗狗的自我修养。

NEERC2014练习

听孙大大说NEERC的题目好，于是打算来写写NEERC的题目。不知道OI生涯还能不能抢救抢救。

• [NEERC2014] Burrito King

有n个物品，每种物品有g[i]克，每种物品每克的joy值为a[i], unhappiness值为b[i]。给你两个参数A,B， 要求每种物品选取若干克(可以为小数), 在unhappiness值不超过B的情况下，joy值尽可能大。

经典的背包问题，按b[i] / a[i] 排序，能取则取。

WARNING
要特别注意b[i] = 0的情况.. 一除就爆炸了

• [NEERC2014] Cactus Generator

给你一个用上下文无关语言定义的仙人掌生成语言.. SCGL, 里面定义了链, 分叉, 环.. 以及循环的规则.. 让你写一个解释器, 读入一个源代码.. 生成一个仙人掌，并且用其最小链覆盖的形式输出。

以下是几个例子:

码农题啊.. 一看就斯巴达了。
慢着..最后那个最小链覆盖怎么求。
只要把所有奇度点任意连起来，然后跑个欧拉回路，再把这些边删掉，剩下的链就是最小链覆盖。
正确性？ 显然答案的下界是奇度点数/2, 这样做就能得到一个奇度点数/2的答案。
然后就码呀码.. 就好了.

WARNING
不要把int赋值给char!!

• [NEERC2014] Damage Assessment

给你个这样的几何体，让你算阴影部分体积。

积分..强上simpson.. 面积的计算比较麻烦..

• [NEERC2014] Epic Win!

一个玩石头剪刀布的DFA, 每个状态上都有一个值(R/P/S), 每个状态也有三条转移边。两个DFA对抗的时候，分别从start开始，比较完一个状态的值之后分别走对手的出招对应的转移边。现在给你一个DFA，但是不知到它的start，让你构造一个DFA，使得对手的DFA不论start在何位置，你对它的胜率都能超过99%.

感觉是个非常好的idea.
首先如果已经知道start了，那么就可以针对性地构造一个DFA，记为W.
那么把这个DFA先构造出来，枚举对手每一种可能的start，在当前的DFA上跑，如果状态跑出了环，说明可以一直赢下去，跳出。如果发现一条转移边并不存在于DFA上，就把W复制一份加到当前DFA中，把当前节点和对手DFA目前的点在新建W中的点连一条边，这样就能保证对手的状态处于被完全针对的状态上。这样就得到了一个状态数为对手状态数O(n ^ 2)级别的DFA。

WARNING
寻找状态的环的时候，要把两个DFA的状态一起考虑进去

if (vis[i][j] == x) break;
vis[i][j] = x;

• [NEERC2014] Filter

给你一个哈希函数，去找可能等于输入值的所有输出值

按照题意直接暴力做就可以了。

• [NEERC2014] Gomoku

交互式五子棋题目，给你一个先手的AI策略，你要写一个AI去击败他！

真有趣..手算题
题解说只有一种胜利策略.. 如下

• [NEERC2014] Hidden Maze

给你一棵随机生成的带权的树，求长度为奇数的链的中位数的期望值。

n < 30000

这题不算难吧..可是很奇怪现场没有一个队交。
其实就是暴力，只是复杂度比较玄学。
先把边的大小排序，一条一条插进去，对于每一条插进去的边，计算它为中位数的方案数。
插入的边权记为1，没插入的记为-1。
假设现在插入的边为x,方案数就是找到一条经过x的路径，边权和为1。
可以从x出发往根走，枚举路径的lca，计算方案数。
g[i][j]表示以i为根的子树中走到i的边权和为j的点数。
每次插入一条边，就枚举它的祖先，更新g[i][j]，顺带更新一发答案。
这个复杂度看起来非常玄学.. 题解说这个复杂度是靠谱的..

• [NEERC2014] Improvements

所有满足条件的排列，将它取逆之后，一定是个单峰的东西，就是先单调增 ，然后单调减。
脑补一下发现，将一个元素任意取值的操作等价于删掉这个元素。
那就是选择一个子序列，使得它先增后降，套上经典算法即可.. O(nlogn)

• [NEERC2014] Jokewithpermutation

直接dfs即可。

• [NEERC2014] Knockout Racing

直接暴力 O(nm)

完结撒花！！

NOIP滚粗...
NOI滚粗...
WC滚粗...

今年还有ZJOI CTSC APIO.. 以及..NOI 感觉压力好大啊..

以下是滚粗狗的自我修养。

NEERC2015练习

听孙大大说NEERC的题目好，于是打算来写写NEERC的题目。不知道OI生涯还能不能抢救抢救。

• [NEERC2015] Adjustment Office

给定一个n * n的矩阵， (i, j)位置元素的值为i + j, 有q次询问，每次给定一个行或一个列，求该行/列元素的和，并在询问之后将该行/列的所有元素变成0。

考虑行R, 如果R没有被询问过，则答案为R * (R中没被删除的元素数) + R中没被删除的列的编号和。发现删除一列C后，所有行中没被删除的元素数量减一，没被删除的列的编号和减C，这样就可以简单维护了。

• [NEERC2015] Binary vs Decimal

定义bindecimal为一类正整数，其十进制表示是其二进制表示的后缀。 求第k小的bindecimal。

$$ 一个性质：10 ^ k 的二进制表示的末尾一定恰有k个0$$

这样就可以枚举答案的位数，从低到高一位一位添加0 / 1,维护当前二进制末尾k位都合法的数字集合，因为有上面那个性质，所以从低到高枚举的时候，当把一个数十进制第k位赋为1的时候，只会影响到这个数二进制中第k位之前的值。因此，这个数的二进制后k位就逐一确定了，就可以把所有答案从小到大枚举出来。要用高精度。

WARNING
向vector中加入结构体时，结构体内的数据并不是0，要通过构造函数来进行赋值。

BigInt(int x) { CL(a, 0); a[len = 0] = x; }

• [NEERC2015] Cactus Jubilee

给你一棵仙人掌，求有多少种方案使得移动一条边之后的图形仍是仙人掌。

首先先求出仙人掌的桥边，如果删去的是桥边，那么仙人掌两个联通块之间任意连边均合法。如果删去的是环上的边，那么显然只能在新的仙人掌上的联通子树上加边。由于删去一条边的环会和周围的联通子树组成一个更大联通子树，因此先dfs出每个点所在的联通子树大小，再求出剖开一个环之后形成的新的联通子树的大小，利用这些联通子树的大小来更新答案即可。可以参考下图。

• [NEERC2015] Distance on Triangulation

给你一个正n边形的三角剖分（告诉你n - 3条对角线的位置), 每条边的权为1。q组询问，每次询问两个点之间的最短路径长度。

据说是tourist出的题。
这题实现起来比较恶心。
由于给出的图是一个多边形的三角剖分，因此每条对角线都能将这个多边形分成两个部分，就可以采用分治的方法。类似树分治，先构出一个分治结构：每次在当前多边形中选出一条对角线，使得两部分点数尽可能均匀(可以证明最坏情况下存在任意一侧不少于n/3的分法），这条对角线两侧就形成了两个子多边形，递归下去，直到当前多边形为三角形为止，并且通过bfs计算出每个子多边形上每个点到选定的对角线两点的距离。询问的时候只要判断一下两个点是否在选定的对角线同侧，如果是则递归求解，否则可以通过之前预处理出的距离简单计算。

WARNING
构建分治结构的时候，要把边和点一并重建，不能只存点的信息，这样会TLE。

• [NEERC2015] Easy Problemset

给你一堆题目和他们的难度，告诉你一套题目的生成规则，求最后的总难度。

模拟即可。

• [NEERC2015] Froggy Ford

在一个平面上给你一些点，要求从x = 0这条线走到x = w, 使得中间经过的最长距离最短。你可以任意添加一个点，求添加完一个点之后的答案尽可能小，求一种最优的加点方案。

如果不加点，则可以通过一遍最短路，或者二分答案+BFS来求出最优解。

显而易见，最优情况下，添加的点一定落在某两个点连线的中点上, 把这些可能的点都加进去。这样得到了O(n^2)个点和O(n^2)条边，只要在跑最短路/二分+BFS的时候另加一维记录一下是否已经过添加点就可以了。

WARNING
这题卡SPFA。用最trivial的Dijkstra就可以了。

• [NEERC2015] Generators

给定n个线性同余随机数生成器，形如：

$$x_{i+1} = \left (ax_i + b \right ) \ mod \ c$$

最大化：

$$s = \sum_{j = 1}^{n}x_{t_j}^{(j)} $$

且满足：

$$s \ mod \ k \neq 0 $$

由于这道题的c很小，只有1000，所以可以把每个随机数生成器所能生成的数算出来。对于每个随机数生成器取出它能产生的最大的数加起来,记作s。若s不能被k整除，则s就是答案，否则从某个随机数生成器中选出一个最大的元素，使得该生成器产生的最大元素减去它不是k的倍数，用其替换即可。

• [NEERC2015] Hypercube

给你一个四维超正方体在三维超平面中的展开图，问这个展开图是否能折成一个超正方体。

四维计算几何.. 一看就懵逼了...

超正方体完全想象不出来.. 尤其是不同晶胞之间的位置关系..

一个超正方体由8个完全等价的立方体晶胞构成(可以类比立方体中6个面)。
首先任意选定一个晶胞放到超正方体的一个位置，然后开始dfs，根据每一步走的方向(上/下/左/右/前/后)将当前晶胞在超正方体上朝对应的方向翻转90度，就得到其在展开图上相邻晶胞在超正方体上的位置了, 然后判断这个位置是否已经被占领，若已被占领则返回无解，否则将这个晶胞放进这个位置然后继续dfs下去直到返回无解或者遍历完了整个展开图。

这个翻转比较抽象.. 可以类比立方体上每个面和相邻面之间的位置关系。具体操作就是，给每个晶胞规定三个维度上的向量(x, y, z)和一个第四维上的法向量，翻转的时候进行向量变换就可以了。具体可以参考下图。

• [NEERC 2015] Iceberg Orders

根据题目给出的证券交易市场的冰山指令规则，给你一堆买入和卖出请求，模拟整个交易过程。

比较繁琐，先挖个坑

过年玩了两天..继续开更..

• [NEERC 2015] Jump

一道挺有趣的交互题。
交互库会生成一个长度为n(n为偶数),的01串, 让你猜这个01串是什么。
每次可以询问交互库一个长度为n的01串与原串之间相同的位数是多少。
如果相同的位数是n或n / 2, 则返回这个数，否则返回0。
其中n不超过1000，询问的次数不能超过1500。

嗯..好像可以先随便猜一个n / 2位相同的串出来..
期望次数大约是40.. 非常小的样子.. 那么就先猜一个出来
现在我们想知道每一位具体的值。 似乎将每一位单独取反之后.. 答案要么+1要么-1.. 返回值都是0
这样就没有办法判断了
把每位与第一位同时取反,然后做一次询问，这样就能得到每一位和第一位之间的关系了,这一步要进行n - 1次询问
然后枚举第一位是0还是1.. 根据之前得到的每位与第一位之间的关系，就能得出每一位的值。
对这两种情况分别做一次询问就好了。

• [NEERC 2015] King

给你一张有向图，求哈密顿回路。其中边数与点数的差不超过20。

因为边数最多只比点数大20.. 首先把入度和出度都为1的点连成一条链, 然后给它们缩起来。
这样最多剩下20条链，压一下状态，dfs之。
在连链和dfs的过程中要注意细节。

WARNING
dfs回溯的时候.. 要把所有修改的信息都给还原了

int kk = ans[x];
ans[x] = v;
if (dfs(id[v], ss)) return true;
ans[x] = kk;

如果ans[x]没还原成kk就会炸。

• [NEERC 2015] Landscape Improved

有w行石子，每一行石子的高度告诉你，再给你n个石子，让你把这些石子往上面放，问石子最高能堆多高。
每个放上去的石子要满足其下、左下、右下都已经有石子了。

发现最终放上去石子的形状肯定是一个金字塔形。
二分答案，枚举最高点位置。这个金字塔的左右边界可以用单调队列预处理出来。
知道左右端点之后就可以计算出需要的石子数量了。
总的复杂度为O(wlogn)
更具体的可以参考下图：

已经一年没更啦..
开更开更..

上次更博客还是一年前省选滚粗的时候呢。
这一年发生了太多的事情了//
一时无法说起.. 就先从省选开始写起吧

要谈ZJOI, 得从去年noip开始谈起.. 谁让这noip有30分呢..
noip正式揭开了我的高中OI生涯..
结果是把它搞砸了.. 415分..
（后来知晓孙大大高二noip也是415..
于是ZJOI之前就带着7分的劣势...
这样心态倒是很好.. 反正进不了队..只能买买名额了
ZJOI去买买萌就行了

ZJOI day1..
看到题面.. 尼玛..幽香？
真的是陈老师的题啊.. 回想起陈老师出的WC模拟赛..就觉得要暴力分滚粗了
仔细一看.. 嗯.. 三棵树
第一题.. 求树的带权重心..支持修改边权.. 哎呀.. 怎么搞.. O(h) 似乎有些分..嗯..肯定是送的.. 不管了.. 先看下一题
第二题.. 求最小瓶颈生成树上的最大边的期望.. 哎呀.. 冬令营似乎有讲过？ 没听课..先看下一题
第三题.. 咦？ 度数不超过20？ 这有啥用？链的情况似乎写一个SAM就好了..

就这样盯着题目看了一个小时.. 把玩把玩钢笔..想着不能再颓下去了..于是决定码一码SAM..先拿二三十分再说..
码完了SAM.. 又盯着第二题看了半个小时... 似乎会第二题暴力了.. 啊.. 我想.. ZJOI反正就是暴力写写就能进队的.于是就开心地码完了暴力..没去想正解..

暴力大法好！

然后又去码第一题暴力.. 发现O(h)的暴力我不会..啊啊啊.. 想想O(h)也就比O(n)的暴力多了十分..
于是开心地开始弃疗.. 算算分.. 嗯.. 105.. 似乎还行..

出考场. 什么？策爷T3说SAM直接能做. 什么？吉丽说T2状压DP乱搞搞就行了 什么？xyw说T1边分治无压力

日狗了. 原来三道题都能做.. 我真是傻逼..

吃午饭时. 和政委、敦爷、镇中众主力交谈.. 他们似乎写的也都是暴力(雾）
觉得暴力似乎还是有希望的（大雾）

时限原因， 整个下午一直在焦急地等待成绩.. 得知第三题是叶子节点不超过20个.. 得知二中两位物理爷这题都没看错.. 得知xj的大爷们似乎都A题了.. 啊啊.. 感觉写暴力好没前途啊..肯定要滚粗了

Boom！

果然爆炸了.. 本身就可怜的暴力分缩水了5分. 只有100分了..
看着二中两位物理爷A了题..都到了前15..黄主力和zhl更是到了前10..敦爷靠着noip依旧前20..
学军众大爷就更不用说了..

rank44

算了一算..假如noip高一点.. 现在应该正好能当当守门员>_<

嗯.. 其实挺好.. 从100+到44.. 嗯.. 反正省队也进不去，体验一把站着死的感觉也不错

day1之后..我立志考试要认真想题..不能写写暴力就弃疗..嗯..
当然如果只会写暴力就写暴力咯.. 我还是坚信如果noip不滚粗.. 暴力写写是能进队的

心态啊.. 心态真重要 --CTSC感想

侥幸水了一块CTSC金牌.. 又回到了学校..熟悉的机房..熟悉的模拟赛..熟悉的生活。
似乎已经忘记之前noip和省选day1的坑.. 再也不像去年省选day2之后按着计算器..妄想着day2要多少分才能翻进队
似乎省选已经从我生活中淡忘...再也不想它.. 因为.xy肯定会给我名额的

在去余姚中学的车上.. 看完了《黑天鹅》.. 它没有给我留下什么深刻的印象.. 现在脑子里对于这部电影，只有一些碎片了
看完电影..脑补着最后榜出来，我是如何因为NOIP分数被卡出队的..

(学校超市卖的桃子不太好吃啊... 继续更

省选住的酒店还是挺不错的，和政委一间。
第一天我们一起在看《无敌浩克》.. 只是一直没搞清楚那个大反派是怎么突然变坏的QAQ

之后两天.. 上午听课 下午回房间颓..
说好的下午打板子..实际上两个下午只码了一个斯坦纳树QAQ.其他大部分时间都在颓QAQ
晚上膜World Final.. 还怂恿政委和我一起看《飞天小女警》.. 结果政委似乎不感兴趣.. 于是我们看了一个晚上的《赌侠》
...最开始听到《赌神》里经典的BGM的时候..热血沸腾啊..以为是《赌神》的正经续集.. 结果一看到周星驰出场..感觉画风不太对啊..一下子就变成了逗比片了QAQ

ZJOI day2之前的那个晚上.. 奇怪了..怎么感觉一点压力都没有.. 并不是好现象啊.. 试图给自己一些紧张感.. 然而并没有用QAQ
刷了会儿足球论坛.. 和孙大大聊了聊天.. 大概11点半才睡的吧..

第二天起来.. 感觉精神还挺好.. 洗漱..整理行李..下楼吃饭.. 感觉比前一天晚上稍微紧张一些了..但是还是挺放松的，反正都知道八成滚粗了,所以也不紧张了。

吃完早饭..下楼..坐车去考场。 在车上跟吉丽交谈WF的事情.. 得知PKU被THU翻了16min.. 从此金银两隔.. 如此相爱相杀.怎么能不好评呢

一路说说笑笑到了考场..
走进考场， 看到座位上都装上了隔板.. 吓了一跳.. 肯定是年纪太轻见识太少了..

坐到位置上..把键盘插好.. 敲好vimrc 等待着密码的公布
密码写到了黑板上.. 不知是机房呆久了还是什么原因..视力有轻微下降，密码看着有些模糊.. 输错了两次密码之后.. 终于成功解压了题目
P.S. 密码是Never Forget How Hard.. 不知道各位有什么好的解释呢

看了看题.. 嗯.. 第一题提答.. 跟去年省选day2画风一样啊.. 去年的2048没去搞实在是太可惜了..今年吸取教训..直接开始搞提答.. 嗯.. Flea++？ vfk怎么也来出题了.. 阅读汇编？ 嗯...那就搞吧.. 反正没啥顾虑了..

搞了一个半小时.. 42分... 感觉不太乐观啊.. 没事没事.. 来看下一题..
咦？ 30分是裸的费用流？ 后面的分数呢..感觉不太好做啊.. 感觉是神题啊.. 嗯.. 先放放..看最后一题

点开最后一题.. 看了一遍
咦..这不是最大权闭合子图吗.. 不对啊.. 怎么可能会出这种题
又看了一眼.. 咦这不是裸的费用流吗.. 怎么可能会出这种题
再看一眼.. 这真的是裸的费用流啊... 说不定真的送温暖呢...
想着大家都A掉这道题.. 心里想想还是挺感人的
于是马上在草稿纸上画了画图.. 诶.. 发现不太对劲啊.. 这个似乎不能直接流..
被自己的naive逗笑了..
看了看暴力分.. 10分.. 嗯.. 真是一个让人翻盘..让人滚粗的暴力分啊

又看了看题.. 咦？ 这不是一个最小权的覆盖问题吗..NPC..
题目那个奇怪的一堆圆到底有什么性质... 完全不知道啊..
如果这玩意儿是全幺模的就好了.. 那么直接跑lp就是答案啦
好开心啊
随机了几个图.. 发现矩阵都是全幺模的...
woc.. 不会能A题吧.. 好激动啊..
码完单纯形.. 对拍了一下..发现没啥问题啊.
看了看时间.. 还有两个半小时..
就又回去码费用流.. 感觉脑子不太好.. 调了半天..先是读入的顺序搞错..再是加边加错QAAAAQ
好不容易磨过了样例.. 目测了一下..就没去管它了..我想费用流总不会写错吧

还有一个多小时.. 回去搞第一题.. 似乎对两三个点找到方法了.. 又去搞了18分.. 提答就正好60分了..
想了一想.. 190.. 应该还不错吧..

走出考场.. 迎面一只杜教.. 吓死了.. 杜教第一句话就是“单纯形90分，现在还没卡”.. woc.. 单纯形原来是错的..那玩意儿不是全幺模？ 不过有90分还是很开心的.. 物理大爷yqw说他也写的是单纯形.. 又和大家交流了一下.. 感觉第二题会搞的不多啊.. 第一题似乎60分还是比较高的..
吉丽dzyxyw他们第一题分数似乎也都不高...

回酒店的路上..听说单纯形要被卡.好虚
回酒店的路上..听说单纯形被卡成10分了.. 好难过
回酒店的路上..听说模拟退火什么的很靠谱.. 啊啊.. 感觉要滚粗了

在酒店的一楼等车..等了好久好久..
等车的时候..听lljz说他第二题能A..最少60..吓哭了.. 又听说他第三题写的是模拟退火.. 感觉ll要标准分了啊.. 吓死了

回来的车上打了一个小时以撒.. 看着窗外发呆了一个小时. 也不知道在想什么.. 感觉也不是很失落 也不是很兴奋
大概进不了队了吧..
也蛮坦然的

回到机房.. 打开UOJ群..咦.. 单纯形有40分.. 感觉只要标准分低于200分.. 我还是能当当守门员的嘛..
被突然到来的惊喜砸中了... 几个月以来以为进不了队了.. 现在似乎有一线生机啊..

人呐..就是这样..之前进队无望的时候.. 就心态可好的..一点都不紧张..
现在进队有希望了.. 就紧张起来了..一个晚上都在关注各种测评情况啊..
各种小道消息层出不穷..消息来源奇怪啊.. 啊啊.. 好久没这么刺激了>_<

又有最新消息了.. 标准分174.. 似乎是洲爷.. 太强了..膜膜膜..

8点半.. 杜教说我进队了.. rank5..
这tm逗我吧.. 一看就是烟雾弹..

noip滚粗成这样还能有rank5.. 不可信啊..
后来杜教又说搞错了..还在rejudge.. 就没去管它了..

睡了一觉.. 早上起来.. xy说我rank5

哦， 杜教看来靠谱。

原来T3我的单纯形姿势比较好..搞了70分.. 意料之外..

于是160.. 嗯..浓浓的骗分狗的气息

然后看到榜了.. 吓死了..
GST3模拟退火70! 调参大师！
GS day2 172..成功翻到rank7..
xj大部分人也没有被翻盘.. 只是lljz说好的的T2满分做法呢... 不知为何..爆零了QAAAAQ

最关键的是.. NOIP吧吧主dzy老爷..510 + 110 + 84... 6道稳稳的暴力.
最后成功进队..教科书一般展示了了ZJOI应该怎样打。
看了许多ZJOI2015行记之后..我觉得..这才是ZJOI的真谛啊。

心态.. 其实还是心态..
先要努力想正解..不要随便弃疗..不过.就算正解想不出来..不要虚啊..就去写暴力啊..稳的啊

人呐就都不知道，自己不可以预料。

logdown的blog都大约两个月没更新了。。 主要原因还是太弱~
Alright, rating涨了一点还是挺好的。

总的来说这场SRM还是偏简单的..

250PT:
题意大概是， 给你一个无向完全图，边权 <= 10 ， 再给你一个参数T。若一条边在至少K对点间的最短路上，则答案加上这条边的权值。众所周知的 TC-STYLE，n <= 50. 于是算法就很显然了， 先求出每对点间的最短路(floyd)， 再枚举每条边， 枚举每对点， 判断这条边是否可能在这对点间的最短路上， 然后更新答案就行了。。

500PT:
给你一棵带权树， 再给你一个参数MaxDist, 你可以通过砍掉某些边的方式来使这个树分裂成好多棵小的树， 需要满足最后所有的树的直径都不超过MaxDist。 你要让最后子树的个数尽可能小 (就是求最少需要切割的刀数)。 数据范围， 依旧TC-STYLE。
一眼的Tree-DP, 具体怎么处理呢： 设 F[i][j] 为将以第i个点为根的子树切割成合法方案最少需要的刀数， 其中i到与i相联通的部分最远的结点的距离为j。 每次转移的时候先枚举最长的距离源自i的哪个孩子(就是枚举i的哪个孩子的子树中贡献了最长路径j) 然后自己再画画图应该就能想出来转移的方程。 j = 0的情况需要特殊考虑。

900PT:
题意比较繁琐， 就不再简述了， 来说说我的做法吧。。
我的做法貌似比较奇葩。。 和 XYZ哥哥的做法好像不是很类似 （说不定本质是一样的。。 但至少看上去不太一样）

设 F[n][k] 为1 - n 所有数中第k位为1的个数， 有了这个，我们就能简单地通过奇偶性来算出最终的异或值。
设 Fib[i] 为第i个Fibonacci数
设MaxFib[n]为不大于n的最大的Fibonacci数，
这样就有比较显然的转移：
若fib[k] ≠ MaxFib[n] 那么 F[n][k] = F[n - MaxFib[n]][k] + F[MaxFib[n] - 1][k]
若fib[k] = MaxFib[n] 那么 F[n][k] = F[n - MaxFib[n]][k] + F[MaxFib[n] - 1][k] + n - Maxfib[n] + 1

由于 n <= 10^15, 直接这么递归下去显然是会T的.. 那么记忆化？ …… 似乎不可行，因为n的范围太大了。。
……
仔细想想看， 记忆化实际上是可以的。 我们注意到式子中多次出现了 F[MaxFib[n] - 1][k]， 由于10^15 之内的Fibonacci数只有72个， MaxFib[n] - 1 实际上也只有72个值。。 我初步想法是先把 F[MaxFib[n] - 1][k] 这个东西记忆化下来。。 至于某个数不是一个Fibonacci数减一的话就暴力往下递归，不储存它的值了。。。

……

然后？ 惊人地发现极限数据秒出了。。 这是为什么。。 明明只部分记忆化了72个值。。

……

其实真相是这样的：
每次递归下去两部分 F[n - MaxFib[n]][k] 和 F[MaxFib[n] - 1][k]。
第二部分我们已经记忆化了，于是剩下的运算都在F[n - MaxFib[n]][k] 上面， 这样相当于每次递归都减去了一个MaxFib[n].
极限数据的递归深度就变成只有18层.. 也就是18个未被记忆化的O(1)运算， 其他递归的东西都被记忆化了。。

部分记忆化真是神奇呢。

$$一如既往，[condition]的意思是，如果方括号内的条件为真，则值为1，反之为0.$$

首先要感谢Picks和Foreseeable97大牛给我提供的帮助

单位根真是太神奇了！

这标题看起来有点13.... 不过单位根真的很有用，能用来化简一类等差循环和式 (不确定这个名词是否存在....)
先给出公式吧，证明后面会讲。

$$\omega 是k次单位根$$
不清楚单位根的可以自行wiki
先给出两道题目题目的链接。。方便各位去切题
PYXFIB

Guideposts

进入正题。

先从PYXFIB开始好了。我介绍的是一种相对来说好理解的做法，也可以很方便推广到Guideposts上 (这种做法我是看hza的blog时发现的，orz...)
照例，先来看看我们要求的式子，然后进行初步化简。

我们先把k|i的约束放在一边。 先来解决一个子问题(也可以理解成k=1时的情况)

这就有点棘手了。 但是因为我们可以通过矩阵乘法快速计算出Fibonacci数列的第n项，所以尝试写出Fibonacci数列的转移矩阵G。
这样整个式子可以变成下面的形式：

看看前面的组合数系数，是不是有点类似二项式系数。 其实二项式定理在矩阵的运算中也是成立的， 因此我们有：

其中1为单位矩阵。

这样当k=1的时候，我们就可以用矩阵乘法快速幂求出答案了。

keep going!

接下来我们考虑[k|i]这个条件。
注意开头提到的那个式子

我们可以把它带入开始的式子。

嗯... 现在这个式子看上去就蛮可做的样子。
再结合刚刚的矩阵的形式。

$$现在我们就可以枚举t,对于每个t，用矩阵乘法快速幂求出 \left ( G \omega ^t +1 \right )^n，最后再除以k就行了$$
$$这样总共的复杂度就是O(k*logn*2^3)$$

然后是Guideposts这题，做法几乎和PYXFIB一模一样。
稍微了解一点图论的同学都知道，求图中一点走k步后到达另一点的方案数只要将这个图的邻接矩阵自乘k次，然后矩阵中的数就是两点间路径的方案数。
更多有关内容参见YHC大牛的论文

$$应用上题的方法我们得到了一个O(k*logn*m^3)的做法$$

看到这里大家应该都会做了。。 后面我来自娱自乐一下。讲一些和这两题有关的细节问题。

两题都要求取模，那么我们一般意义上的单位根(定义在复数域中的)可能会遇到很多问题。 首先是中间不能取模，以及精度的问题难以解决。 那应该怎么办呢？
我们可以使用数论变换(NTT)中的单位根(定义在mod P的剩余系下)。

其中G为P的一个原根

这样我们就可以利用它来完成上述的算法了。

最后，证明一下开头的那个公式

当n是k倍数的时候

当n不是k倍数的时候

至于代码。。 写的太丑了，我就不贴了。 hza博客中有python写的PYXFIB,做法和我这个应该是一样的

显然，每行不超过2个炮，每列不超过两个炮.

进而发现，解的个数和具体每一列的状态无关，具体点说，解数就是只和当前有1个炮的列数与有2个炮的列数有关
由于只和列数有关，而和具体是哪些列无关，我们就可以得出一个dp方程来

具体转移分当前这行不放棋子，放一个棋子，放两个棋子分开来讨论。 具体实现略有复杂，我就放代码吧。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define mo 9999973LL
using namespace std;
typedef long long LL;
int n,m;
LL f[111][111][111];
LL c[111];
LL ans=0;
int main()
{
    cin>>n>>m;
    for (int i=0;i<=m;++i)
        c[i]=i*(i-1)/2;
    f[0][0][0]=1;
    for (int i=1;i<=n;++i)
        for (int j=0;j<=m;++j)
            for (int k=0;k<=m;++k)
            {
                if (k+j>m) break;
                f[i][j][k]=f[i-1][j][k];
                if (k>0) f[i][j][k]+=f[i-1][j+1][k-1]*(LL)(j+1)%mo;
                if (j>0) f[i][j][k]+=f[i-1][j-1][k]*(LL)(m-j-k+1)%mo;
                if (k>1) f[i][j][k]+=f[i-1][j+2][k-2]*c[j+2]%mo;
                if (j>1) f[i][j][k]+=f[i-1][j-2][k]*c[m-k-j+2]%mo;
                if (j>0&&k>0) f[i][j][k]+=f[i-1][j][k-1]*(LL)(m-k-j+1)*(LL)(j)%mo;
                f[i][j][k]%=mo;
                if (i==n) ans+=f[i][j][k];
                ans%=mo;
            }
    cout<<ans<<endl;
    return 0;
}

$$这题很早就做过，最近在复习简单数论，因而写个题解，也再试一下 \LaTeX$$

$$[condition]的意思是，如果方括号内的条件为真，则值为1，反之为0.$$

先来看一下我们要求的东西

现在把问题简单化，假设我们已经知道一个质数p，要求

这是个很经典的问题，我们可以用莫比乌斯反演来解决。

如果还不知道莫比乌斯反演，请移步贾志鹏线性筛

$$这个问题我们可以在O(n)-O(\sqrt n)时间内求出$$

由此，我们可以得到一个初步的算法，枚举n以内每个质数p,通过刚刚的方法求出每个质数的答案，然后再加起来。

可是由于多组数据的存在，这个算法很显然是会T的。 我们需要更好的方法。

我们把p加到式子上，看看能不能化简。

以上的p都是质数

令

上式可以写成

我们假定n < m,有

以上的p也都是质数

现在问题转变为求f(d)，令s为d的不相同的质因子个数，由f的定义可知

$$由此，虽然f(d)不是一个积性函数,但我们可以用欧拉筛在线性时间内预处理出所有的f(d).$$

$$我们预处理出f函数后，就能够通过之前的方法实现单组询问O(\sqrt n)的复杂度，总共复杂度就是O(n)-O(\sqrt n)$$

代码网上都有，我就不贴了。具体实现还是挺简单的