这次情况稍微好了点，但是还是各种写跪23333……不得不说，纪中的OIer数学推演能力好像都太好了点，就是讲的课很容易让人听不懂…… 【T1】【JZOJ 3777】 这道题目是一类特殊图的最短路，这种题目一般是打表+找规律+证明（一般不会去想？）……讲的是对于一个格点图，对于点 (i,j) 定义权值为 F(i,j)=F(i−1,j)+F(i,j−1) ，边界 i=0 或 j=0 时 F(i,j)=1 ，同时在 (i,j) 与 (i,j−1) 、 (i−1,j) 间相应分别连两条零权值边，问 (0,0) 到 (n,m) 的最短路。 容易发现最短路就是沿着边走，不妨设 n<m ，那么最短路就是 (0,0)−(0,m)−(n,m) ，因为从另一个方向的折线显然比它长。那么问题就变成了求 m+∑i=1nF(i,m) 。由于我们马上可以发现 F(i,j) 其实对应杨辉三角，进而对应组合数，所以上面那个式子 =m+∑i=1nC(i+m−1,i 。 怎样快速求呢？这里有两个思路： 思路一，注意到
C(i,j)=j!i!(j−i)! 和 C(i+1,j+1)=(j+1)!(i+1)!(j−i)! 那么我们得到 C(i+1,j+1)=j+1i+1C(i,j)=(j+1)(i+1)−1C(i,j) 就可以很方便地用逆元直接推啦~ 直接搞是 O(nlgn) ，如果用线性推逆元（推到 nm−−−√ ）就可以直接做到 O(n) ，但是比较麻烦。 思路二，考虑到 C(i,j)=C(i−1,j)+C(i−1,j−1) 我们再次注意到那个式子里面我们如果把 C(m,0) 给补上去，然后由上面那条式子，可以得到 C(m,0)+C(m,1)+C(m+1,2)+⋯ =C(m+1,1)+C(m+1,2)+C(m+2,3)+⋯ =⋯=C(m+n−1,n) 这个可以直接算若干阶乘，然后全部阶乘完再做逆元，这样似乎比较快？而且还挺好写的，时间复杂度 O(n+lgn) 。 【T2】【JZOJ 3769】 题意是考虑一种特殊的斐波那契进制来表示数，即把数表示成每位权值分别为 1,2,3,5,8...Fib(i) 的向量 a ，使得这个a最大，也就是 |a| 最大且对于任意一个表示同样数且长度一样的的向量 a′ ，设从高位到低位第一个不同的是 ai≠a′i ，那么都要满足 ai>a′i 。这里给出两个这样的向量，求把这两个向量对应加起来之后的最大向量。 我们发现，满足最大的向量一定没有相邻的两个一，而且也不可能有大于一的数，前一个可以合并两个一，后一个可以分拆，比如 2xi=xi−2+xi+1 ，这样向量都会更大。于是我们先定义一次迭代操作就是先把所有的大于一的数分拆，然后再统一合并相邻的非零数，接着听说跑个玄学次就能过了，我也不会证……不过还是有可能构造出数据的。隔壁zmz dalao认为跑 lgn 次就可以了，但是我也还是证不了，根据数据只用10+次。【T3】【JZOJ3771】 对于这道题目，我们直接来讨论下满分算法。考虑到如果不算所有乘上了 2i 的数，那么第一个盒子里的数都是奇数。那么我们容易发现，第一个盒子里面的所有数实际上就是所有形式为 a2mi 的数，其中 a 都是奇数，结合标号条件，我们还需要a2mi m 1≤n。这时我们考虑枚举下 i ，就可以求出对应的a的范围，然后全部加一块就行了。我们发现，实际上我们给 [n2] （这里[x]表示下取整）每次除多 2m 就行了……反正高精度里面压压位，然后直接用位运算加速就好了。
