2019牛客暑期多校训练营（第五场）B generator 1

ゝ一纸荒年。 2023-10-11 09:30 8阅读 0赞

[传送门][Link 1]

题意：

先输入X0,X1,a,b然后按照Xi=a\*X(i-1)+b\*X(i-2)     (i>=2)

之后再输入n，mod，让你根据公式求X(n)的值取余于mod

题解：

相信大家很快就能找到矩阵快速幂的系数

|X0  X1|  \*  |0  b|   =  |X1 X2|

|1  a|

或者

|0  1|  \*  |x0|  =  |x1|

|b  a|     |x1|      |x2|

就根据公式来写矩阵快速幂

但是我们还要注意题目上输入的n的位数早就已经超出了long long的范围了，所以要想求出来系数矩阵的次幂还是有问题的

我们观察2^121这个次幂，它是由一个1、2\*10、1\*100

2^121 = (2^1)\*(2^10)\*(2^2)\*(2^10)\*(2^1)

根据这种特性，我们就可以把一个大数次幂给一一分解^\_^

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long LL;
     4 const int size=1e6+5;
     5 char n[size];
     6 int x0,x1,a,b;
     7 typedef long long LL;
     8 LL mod;
     9 struct mat
    10 {
    11     int m[3][3];
    12     mat(){
         for(int i=0;i<3;i++)for(int j=0;j<3;j++) m[i][j]=0;}
    13     friend mat operator*(mat x,mat y)
    14     {
    15         mat ans;
    16         for(int i=1;i<=2;i++)
    17         {
    18             for(int j=1;j<=2;j++)
    19             {
    20                 for(int k=1;k<=2;k++)
    21                 {
    22                     ans.m[i][k] = (ans.m[i][k]+1LL*x.m[i][j]*y.m[j][k])%mod;
    23                 }
    24             }
    25         }
    26         return ans;
    27     }
    28 };
    29 inline mat quick_pow(mat a,int b)
    30 {
    31     mat ans;
    32     ans.m[1][1]=1;ans.m[2][2]=1;
    33     while(b)
    34     {
    35         if(b&1) ans=ans*a;
    36         a=a*a;
    37         b>>=1;
    38     }
    39     return ans;
    40 }
    41 int main()
    42 {
    43     scanf("%d%d%d%d",&x0,&x1,&a,&b);
    44     scanf("%s%lld",n,&mod);
    45     mat ori;
    46     int len =strlen(n);
    47     ori.m[1][2]=1,ori.m[2][1]=b;ori.m[2][2]=a;
    48     mat ans;
    49     ans.m[1][1]=1;ans.m[2][2]=1;
    50     for(int i=len-1;i>=0;i--)
    51     {
    52         ans=ans*quick_pow(ori,n[i]-'0');
    53         ori=quick_pow(ori,10);
    54     }
    55     printf("%lld\n",(1LL*x0*ans.m[1][1]+1LL*x1*ans.m[1][2])%mod);
    56 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11284234.html

[Link 1]: https://ac.nowcoder.com/acm/contest/885/B
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif