牛客题解-二维斐波那契数列

链接:二维斐波那契数列_牛客题霸_牛客网

注:文字描述部分如果比较乱可下滑看图片描述哦^(*￣(oo)￣)^

描述

二维斐波那契数列满足以下递推式：

{ai,j=1,(i,j∈{1})ai,j=ai−1,j,(2≤i; j∈{1})ai,j=ai,j−1,(2≤j; i∈{1})ai,j=ai−1,j+ai,j−1,(2≤i,j)⎩⎪⎪⎪⎨⎪⎪⎪⎧​ai,j​=1,ai,j​=ai−1,j​,ai,j​=ai,j−1​,ai,j​=ai−1,j​+ai,j−1​,​(i,j∈{1})(2≤i;j∈{1})(2≤j;i∈{1})(2≤i,j)​

给定正整数 n,mn,m，求 an,man,m​ 的值。由于结果可能很大，请输出 an,man,m​ 对 109+7109+7 取模后的结果。

输入描述：

在一行中输入两个正整数 n,mn,m（1≦n,m≦1031≦n,m≦103），分别表示行下标和列下标。

输出描述：

输出一个整数，表示 an,m mod (109+7)an,m​mod(109+7) 的值。

示例1

输入：

1 1

复制输出：

1

复制说明：

根据定义，a1,1=1a1,1​=1。

示例2

输入：

2 2

复制输出：

2

复制说明：

由递推可得：a2,1=a1,1=1a2,1​=a1,1​=1，a1,2=a1,1=1a1,2​=a1,1​=1； a2,2=a1,2+a2,1=1+1=2a2,2​=a1,2​+a2,1​=1+1=2。

备注：

提示，取模运算对加法运算满足交换律和结合律，所以在计算过程中多次取模得到的计算结果，和全部计算都完成后得到的计算结果是相同的。

////法1:动态规划DP //#include <bits/stdc++.h> //using namespace std; //typedef long long ll; // //const ll MOD = 1e9 + 7; // //ll dp[1004][1004]; // //int main() //{ // ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // ll a, b; // cin >> a >> b; // // dp[1][1] = 1; // for(ll i = 1; i <= a; i++) // for(ll j = 1; j <= b; j++) // { // if(i == 1 && j == 1) continue; // dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD; // } // // cout << dp[a][b]; // return 0; //} //法2:组合路径计数等价 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MOD = 1e9 + 7; // 快速幂：计算 a^b mod MOD // 原理：把 b 拆成二进制，例如 b=13=1101(2)，则 a^13 = a^8 * a^4 * a^ ll qpow(ll a, ll b) { ll res = 1; a %= MOD; // 先取模防止溢出 while(b) { if(b&1)// 如果 b 的最低位是1 { res = res * a % MOD;// 乘上当前的 a } a = a*a % MOD;// a 平方（对应下一位） b >>= 1;// b 右移一位 } return res; } // 计算组合数 C(n, m) = n! / (m! * (n-m)!) mod MOD // 由于有除法，需要用逆元：a/b mod MOD = a * b^(MOD-2) mod MOD ll C(ll n, ll m) { if(m < 0 || m > n) return 0; ll up=1, down=1;//up分子,down分母 for(ll i = 1; i <= m; i++)// 计算：n * (n-1) * ... * (n-m+1) / (1 * 2 * ... * m) { up = up*(n-i+1) % MOD;// 分子累乘：n, n-1, ... down = down*i % MOD;// 分母累乘：1, 2, ... } // 费马小定理：down^(MOD-2) 就是 down 的逆元 return up * qpow(down, MOD-2) % MOD;//不能写成return up * qpow(down, -1) % MOd; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll a, b; cin >> a >> b; // 总共走 (a+b-2) 步，选 (a-1) 步向下（或选 b-1 步向右） cout << C(a+b-2, a-1); }

核心思想

计算：从左上角 (1,1) 走到右下角 (a,b) ，每次只能向右或向下走，有多少种不同的路径？

想象一个网格：

• 要从 (1,1) 到 (a,b) ，必须向右走 (b−1) 步，向下走 (a−1) 步

• 总共走 (a−1)+(b−1)=a+b−2 步

• 问题变成：在这 a+b−2 步中，选哪些步向下走（或向右走）？

组合数公式

答案=$C_{a+b−2}^{a−1}​$=$C_{a+b−2}^{b−1​}$

例如 a=3,b=3 ：

• 需要走 4 步（2步右，2步下）

• 方案数 = $C_4^2$

关键知识点

1. 为什么用逆元而不是直接除？

模运算中：(a/b)%MOD ≠ (a%MOD) / (b%MOD)

需要用乘法逆元：a/b≡a×$b^{−1}$ (mod MOD)

当 MOD 是质数时，根据费马小定理： $b^{−1}$≡$b^{MOD−2}$ (mod MOD)

费马小定理（Fermat's Little Theorem）

定理内容

如果 p 是质数，且整数 a 不是 p 的倍数，

则：$a^{p−1}$ ≡ 1 (mod p)

推论：求逆元

两边同时除以 a ：

$a^{p−2}$ ≡ $a^{−1}$ (mod p)

这就是代码中qpow(down, MOD-2)的原理！

直观理解

在模 p 的世界里，每个非零数 a 都有一个"倒数" $a^{−1}$ ，使得：

a× $a^{−1}$ ≡ 1 (mod p)

费马小定理告诉我们：这个倒数就是 $a^{p−2}$