常用知名购物网站,网络公司网站官网,免费源码html网站,做网站l价格链接:二维斐波那契数列_牛客题霸_牛客网 注:文字描述部分如果比较乱可下滑看图片描述哦^(*#xffe3;(oo)#xffe3;)^ 描述 二维斐波那契数列满足以下递推式#xff1a; {ai,j1,(i,j∈{1})ai,jai−1,j,(2≤i; j∈{1})ai,jai,j−1,(2≤j; i∈{1})ai,jai−1,jai,j−1,(…链接:二维斐波那契数列_牛客题霸_牛客网注:文字描述部分如果比较乱可下滑看图片描述哦^(*(oo))^描述二维斐波那契数列满足以下递推式{ai,j1,(i,j∈{1})ai,jai−1,j,(2≤i; j∈{1})ai,jai,j−1,(2≤j; i∈{1})ai,jai−1,jai,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​ 对 10971097 取模后的结果。输入描述在一行中输入两个正整数 n,mn,m1≦n,m≦1031≦n,m≦103分别表示行下标和列下标。输出描述输出一个整数表示 an,m mod (1097)an,m​mod(1097) 的值。示例1输入1 1复制输出1复制说明根据定义a1,11a1,1​1。示例2输入2 2复制输出2复制说明由递推可得a2,1a1,11a2,1​a1,1​1a1,2a1,11a1,2​a1,1​1 a2,2a1,2a2,1112a2,2​a1,2​a2,1​112。备注提示取模运算对加法运算满足交换律和结合律所以在计算过程中多次取模得到的计算结果和全部计算都完成后得到的计算结果是相同的。////法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 拆成二进制例如 b131101(2)则 a^13 a^8 * a^4 * a^ ll qpow(ll a, ll b) { ll res 1; a % MOD; // 先取模防止溢出 while(b) { if(b1)// 如果 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 up1, down1;//up分子,down分母 for(ll i 1; i m; i)// 计算n * (n-1) * ... * (n-m1) / (1 * 2 * ... * m) { up up*(n-i1) % 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; // 总共走 (ab-2) 步选 (a-1) 步向下或选 b-1 步向右 cout C(ab-2, a-1); }核心思想计算从左上角 (1,1) 走到右下角 (a,b) 每次只能向右或向下走有多少种不同的路径想象一个网格要从 (1,1) 到 (a,b) 必须向右走 (b−1) 步向下走 (a−1) 步总共走 (a−1)(b−1)ab−2 步问题变成在这 ab−2 步中选哪些步向下走或向右走组合数公式答案$C_{ab−2}^{a−1}​$$C_{ab−2}^{b−1​}$例如 a3,b3 需要走 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)费马小定理Fermats 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}$