Hdu 4565 So Easy! (数学构造矩阵)

绝地灬酷狼 2022-09-17 11:15 17阅读 0赞

今年网络赛的经验就是：邀请赛的题目一定要及时做。。。。。

MathType这软件还是挺好用的。。。

2013 ACM-ICPC长沙赛区全国邀请赛——题目重现 的一题

题意简单明了……

思路：看见这么大的乘方运算那很有可能是矩阵……

![SouthEast][]

然后我们就可以构造矩阵，利用矩阵的幂运算来做。

![SouthEast 1][]

#include <cstdio>
    #include <cstring>
    
    const int N=2;
    #define i64 __int64
    
    i64 modd;
    
    class Matrix
    {
    public:
    	i64 a[N][N];
    	int n;   //矩阵大小
    
    	void init (int x)
    	{
    		memset(a,0,sizeof(a));
    		if (x) for (int i=0;i<N;i++)
    			a[i][i]=1;
        }
    
    	Matrix operator * (Matrix b)
    	{
    		Matrix p;
    		p.n=b.n;   //
    		p.init(0);
    		for (int i=0;i<n;i++) for (int j=0;j<n;j++)
    			for (int k=0;k<n;k++)
    				(p.a[i][j]+=a[i][k]*b.a[k][j]%modd)%=modd;
    		return p;
    	}
    
    	Matrix power (int t)
    	{
    		Matrix ans,p=*this;
    		ans.n=p.n;  //
    		ans.init(1);
    		while (t)
    		{
    			if (t&1) ans=ans*p;
    			p=p*p;
    			t>>=1;
    		}
    		return ans;
    	}
    }p;
    
    int main ()
    {
        i64 a,b,n,m;
        while (~scanf("%I64d%I64d%I64d%I64d",&a,&b,&n,&m))
        {
    		if (n==1)
    		{
    			printf("%I64d\n",a*2%m);
    			continue;
    		}
            modd=m;
            p.init (0);
            p.n=2;
            p.a[0][0]=2*a%modd , p.a[0][1]=1;
            p.a[1][0]=-((a*a-b)%modd),p.a[1][1]=0;
            p=p.power(n-1);
            i64 ans=2*a*p.a[0][0]+2*p.a[1][0];
            ans%=modd;
    		if (ans<0)   //  注意这里
    			ans+=m;
            printf("%I64d\n",ans);
        }
        return 0;
    }

[SouthEast]: /images/20220828/0fd1f505f54046bc8a250eb71eebb0e8.png
[SouthEast 1]: /images/20220828/22ae6e7b29a042bab700fd708af49a6f.png