题解 P1397 【[NOI2013]矩阵游戏】

· · 题解

ps:更新一下结果疯狂说我的排版不整齐是什么鬼

哇好多水文啊

很多人根本没有说清楚a=1的情况

这不行，我试试填补这空缺吧

原文在我的blog

我转载一下，不知道公式有没有问题……

首先，这个n、m的大小这么奇葩，那就是有一定暗示的了 （UP：好像有人直接写十进制快速幂+常数优化搞过去了……）

那么我们引用伟大的费马小定理

这个神奇玩意居然对矩阵也有效！【flag，见后文】

在mod MOD（也就是1e9+7）下，设操作矩阵为A， 那么A^{1e9+6}=1 (\mod MOD) ，相当于单位矩阵 所以对于同一行下，第m个=第m%(MOD-1)个

而如果把【一行的转移+m到下一行第一个的转移】看作一个操作矩阵B， 同理第n行=第n%(MOD-1)行

综上所述，f[n][m]=f[n\%(MOD-1)][m\%(MOD-1)]

然后我到这里就懵逼了：这么大的数字怎么存储？还要写高精度取模？？？ 事实上，\%(MOD-1)=\%( (MOD-1)*10^k )

意思就是说， 完全可以放到字符串里面，取一个模一下 真是让人涨见识的骚操作QAQ 剩下的就是推一个简单矩阵了

发现自己wa了两个点【90分，其实也该满足了】？别着急 我也是自信满满地提交，然后看别人题解才看到：a=1和c=1的特殊情况

网上清一色“要特判”，但都没讲理由？

首先，实验证明，我的两个操作矩阵A^{MOD-1}\neq 1 (\mod MOD),事实上循环结长度是MOD

为什么会出现这种情况呢？【开始解决flag】

我们回顾一下，费马小定理的条件之一：gcd(A,MOD)=1 但这里A是一个矩阵呀，怎么会有gcd？咳咳，别着急。 前面我们直接啥也不管，以为网上题解说能就直接用了，所以才会有现在的状况

那么我先是问了下师兄，然后两人一起捣鼓半天，大概搞了个解释：

注意，所有公式都是在模意义下进行

我们回归到最初的公式【以行内转移举例，忽略行数，反正也就是二维】

f[i]=a\times f[i-1]+b (\mod MOD) ,1

我们希望把它变成一个等比数列来搞出一个通项公式 【没学过高中数学没关系，我也没学】 构造一个b'使满足这个式子：

f[i]+b'=a\times (f[i-1]+b') (\mod MOD),2

现在通过1和2推导出这道题的b'=\frac{b}{a-1} (a\neq1)

辣么现在就能搞出一个通项公式啦

f[i]+b'=a^{i-1}\times (f[1]+b') (\mod MOD)

既然是等比数列，那就搞上费马小定理吧~ 【gcd(a,MOD)=1并没有影响，因为题目条件里面限制了a的范围】

f[i]+\frac{b}{a-1}=a^{ (i-1)\%(MOD-1) }\times (f[1]+\frac{b}{a-1}) (\mod MOD) (a\neq1)

好了，我们搞这么多有什么用呢？

师兄的说法：用来给你十进制快速幂呀！啊那行之间怎么转移呢？不会呀

这么说原来根本就不是同一个做法好吗。

那我干嘛要写在博客上呀 仅仅因为那个a\neq1

没错我们现在说这么多就是为了解决我们丢了10分的问题【终于回到正题了】 不扯了 那a=1的时候，其实就变成了一个等差数列，通项公式：

f[i]=f[1]+b\times (i-1) (\mod MOD)

然后有个东西叫欧拉函数，\varphi(x)= 在1到x的正整数中与x互质的数的个数

显然在x为质数的时候，\varphi(x)=x-1 那么在我们刚才矩阵乘法的时候，循环节可以记作p=\phi(MOD) 由此而知f[p+1]=f[1] 【当a\neq1的时候，p已经算出来了，现在算a=1的情况，p未知】

f[p+1]=f[1]+b\times p (\mod MOD)

那么b\times p=0 (\mod MOD) 而这道题中，b一不是MOD的倍数，二不是0，则p=0 (\mod MOD) 而p肯定又不是0，所以可以考虑把p看作MOD的倍数 哇那就是说

$p=\phi(MOD)=MOD-1 $【Otherwise】 哈哈搞定 ~~~其实我自己觉得有种东扯扯西扯扯的感觉~~ 但好歹也是有理有据的嘛 总结： 综上所述，我们在搞n和m的时候，分别根据a和c是否是1来决定MOD（详见代码） 然后经验就是，这种有特殊条件的定理，先不要引入矩阵乘法，而是把公式搞清楚，把各种细节考虑周到再去优化【虽然这道题也就10分】 [code](https://www.luogu.org/paste/wrxomlh7)