generator 1

题目链接：  https://ac.nowcoder.com/acm/contest/885/B

利用斐波拉契数列通项公式和快速幂求解

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
long long int m;
char st[2000006];
struct node
{
    long long int x1,x2,y1,y2;
};
node fun2(node ans,node ans1)
{
    node ans3;
    ans3.x1=((ans.x1*ans1.x1)%m+(ans.x2*ans1.y1)%m)%m;
    ans3.x2=((ans.x1*ans1.x2)%m+(ans.x2*ans1.y2)%m)%m;
    ans3.y1=((ans.y1*ans1.x1)%m+(ans.y2*ans1.y1)%m)%m;
    ans3.y2=((ans.y1*ans1.x2)%m+(ans.y2*ans1.y2)%m)%m;
    return ans3;
}
node fun1(node ans,int w)//快速幂
{
    node ans1;
    ans1.x1=1;
    ans1.x2=0;
    ans1.y1=0;
    ans1.y2=1;
    while(w)
    {
        if(w%2==1)
            ans1=fun2(ans1,ans);
        ans=fun2(ans,ans);
        w=w/2;
    }
    return ans1;
}
node fun(node ans)
{
    int i,n;
    n=strlen(st);
    node ans1,ans2;
    ans1.x1=1;
    ans1.x2=0;
    ans1.y1=0;
    ans1.y2=1;
    ans2.x1=1;
    ans2.x2=0;
    ans2.y1=0;
    ans2.y2=1;
    for(i=n-1;i>=0;i--)
    {
        int w=st[i]-'0';
        if(w!=0)
        {
            ans2=fun1(ans,w);
            ans1=fun2(ans1,ans2);
        }
        ans=fun1(ans,10);
    }
    return ans1;
}
int main()
{
    long long int n,a,b,x0,x1;
    while(~scanf("%lld %lld %lld %lld",&x0,&x1,&a,&b))
    {
        scanf("%s",st);
        scanf("%lld",&m);
        n=strlen(st);
        for(int i=n-1;i>=0;i--)
        {
            if(st[i]=='0')
                st[i]='9';
            else
            {
                st[i]=st[i]-1;
                break;
            }
        }
        node ans;
        ans.x1=a;
        ans.x2=b;
        ans.y1=1;
        ans.y2=0;
        ans=fun(ans);
        long long int sum=(ans.x1*x1%m+ans.x2*x0%m)%m;
        printf("%lld
",sum);
    }
    return 0;
}