题解 | 二维斐波那契数列

#include <iostream>
using namespace std; 
long long mod=1e9+7;
/*long long a(int i,int j)
{
    if(j==1||i==1) return 1;
    else return (a(i-1,j)+a(i,j-1))%mod;
}*/
long long a[1001][1001]={0};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
//加了快读快写依然啥用没有
    int n,m;
    cin>>n>>m;//15
    for(int i=1;i<=n;i++) 
        a[i][1]=1;
    for(int i=1;i<=m;i++)
        a[1][i]=1;
    for(int i=2;i<=n;i++)
    {
        for(int j=2;j<=m;j++)
        {
            a[i][j]=(a[i-1][j]+a[i][j-1])%mod;
		  //随地大小模
        }
    }
    cout<<a[n][m];
}

其实当时写的时候我有一个问题：

这道题，为什么第一张代码图（mod加在循环里）就能过，第二张图（mod加在输出时）就过不了？

答案是因为：这样就不会发生溢出，所有中间值都是正确的，最终结果也正确。

你在过程中mod就能保证值全都在1e9+6以下，绝对不会超过long long。

因为斐波那契涨得快，所以ij稍大时，a[i][j] 就会超出 long long 的范围，导致溢出，数值失真。即使最后对溢出后的错误结果取模，得到的也不是正确答案。

在这类需要对大数取模的题目中，必须在每一步计算后都进行取模，而不是只在最后一步取模。这样既能防止数据溢出，又能保证每一步的计算结果都在可控范围内，从而得到正确的最终答案。