fzu Problem 2198 快来快来数一数 (快速幂+优化)

题目链接：

　　Problem 2198 快来快来数一数

题目描述：

　　给出n个六边形排成一排，a[i]代表i个六边形能组成的生成树个数，设定s[i]等于a[1]+a[2]+a[3]+....+a[i-1]+a[i]，问s[n]为多少？

解题思路：

　　n取值范围[1, 10¹⁸],打表内存不够，然后就要考虑快速幂咯！纳尼！！！！快速幂写出来竟然超时，敢信？果然还是见题太少了。(GG)

　　对于a[n] = 6*a[n-1] - a[n-2]，可以很明显看出。

　　然后求和的时候就要化简一番了，但是并不是很难，最终的公式是：s[n] = 6*s[n-1] - s[n-2] + 5;然后构造矩阵，预处理构造矩阵，跑快速幂即可！！

代码：

 #include <iostream>

 #include <cstdlib>

 #include <cstdio>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <cstring>

 using namespace std;

 #define LL long long

 const LL maxn = ;

 const LL mod = ;

 struct mat

 {

     LL col, row;

     LL p[maxn][maxn];

 } pp[];

 mat mul (mat a, mat b);

 mat pow (LL n, LL res, mat b);

 int main ()

 {

     LL n, t;

     mat b;

     scanf ("%lld", &t);

     memset (pp[].p, , sizeof(pp[].p));

     memset (b.p, , sizeof(b.p));

     pp[].col = pp[].row = b.row = maxn;

     b.col = ;

     pp[].p[][] = ;

     pp[].p[][] = -;

     pp[].p[][] = pp[].p[][] = pp[].p[][] = ;

     b.p[][] = ;

     b.p[][] = ;

     b.p[][] = ;

     for (int i=; i<; i++)

         pp[i] = mul(pp[i-], pp[i-]);

     while (t --)

     {

         mat a;

         scanf ("%lld", &n);

         a = pow(n-, , b);

         printf ("%lld\n", a.p[][] % mod);

     }

     return ;

 }

 mat mul (mat a, mat b)

 {

     mat c;

     c.col = a.col;

     c.row = b.row;

     memset (c.p, , sizeof(c.p));

     for (int k=; k<a.row; k++)

         for (int i=; i<a.col; i++)

         {

             if (a.p[i][k] == ) continue;

             for (int j=; j<b.row; j++)

             {

                 if (b.p[k][j] == ) continue;

                 c.p[i][j] = (c.p[i][j] + a.p[i][k] * b.p[k][j] + mod) % mod;

             }

         }

     return c;

 }

 mat pow (LL n, LL res, mat b)

 {

     while (n)

     {

         if (n % )

             b = mul (b, pp[res]);

         res ++;

         n /= ;

     }

     return b;

 }

写的好丑！不要喷我 (捂脸逃~~~~)

巴特西

fzu Problem 2198 快来快来数一数 (快速幂+优化)

最新文章

热门文章