首页 > 代码库 > 1556 计算

1556 计算

2024-08-13 11:54:40   210人阅读

有一个1*n的矩阵 固定第一个数为1 其他填正整数  且相邻数的差不能超过1 求方案数%1e9+7的结果
Input
一个数n 表示1*n的矩阵（n<=10^6）
Output
一个数 表示方案数%1e9+7的结果
Input示例
3
Output示例
5
考虑用默慈金数解决这个问题。

在一个网格上，若限定每步只能向右移动一格，可以右上，右下，

横向，向右，并禁止移动到技术分享以下的地方，则以这种走法移动技术分享步从技术分享到技术分享的可能形成的路径的总数

为技术分享的默慈金数。如下图示

 

         技术分享

 

默慈金数满足如下递推式： 技术分享

详细证明：http://www.docin.com/p1-964777006.html 

接下来 我们考虑用总数减去不合法的方案数 考虑过y=0的方案 显然为Mi*(3^i)

用总数减即可。

 

 1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<queue> 6 #include<math.h> 7 #include<stack> 8 #include<vector> 9 using namespace std;10 typedef long long LL;11 const LL mod = 1e9+7;12 LL M[1000005];13 LL quick(LL n,LL m);14 int main(void)15 {16         M[1] = 1;17         M[2] = 2;M[0] = 1;18         int n;19         scanf("%d",&n);20          for(int i = 3; i <= n; i++)21         {22                 LL ni = i+2;23                 ni = quick(ni,mod-2);24                 M[i] = (LL)(2*i+1)*M[i-1]%mod+(LL)3*(i-1)*M[i-2]%mod;25                 M[i] %= mod;26                 M[i] = M[i]*ni%mod;27         }28         LL sum = quick((LL)3,(LL)n-1);29         for(int i = 2;i <= n; i++)30         {31             LL ak = M[i-2]*quick((LL)3,(LL)n-i)%mod;32             sum = sum - ak;33             sum%=mod;34         }35         printf("%lld\n",(sum%mod+mod)%mod);36         return 0;37 }38 LL quick(LL n,LL m)39 {40         LL ask = 1;41         while(m)42         {43                 if(m&1)44                         ask = ask*n%mod;45                 n = n*n%mod;46                 m/=2;47         }48         return ask;49 }

 

 

 

1556 计算






























        

            
                
                  
                
                

                    联系

                    我们