FZU 1683 纪念SlingShot （构造矩阵）

曾经终败给现在 2022-09-08 04:57 128阅读 0赞

矩阵这个东西还是很好用的，这回开始深入学习。

参考了：http://www.cnblogs.com/jianglangcaijin/archive/2012/12/29/2838328.html

题目链接：[http://acm.fzu.edu.cn/problem.php?pid=1683][http_acm.fzu.edu.cn_problem.php_pid_1683]

题意：f(0)=1,f(1)=3,f(2)=5,f(n)=3f(n-1)+2f(n-2)+5f(n-3)。求s(n)=(f(0)+f(1)……+f(n))%2009。

思路：S(n)=S(n-1)+F(n)=S(n-1)+3F(n-1)+2F(n-2)+7F(n-3)，因此构造矩阵：

![SouthEast][]

#include <cstdio>
    #include <cstring>
    
    const int N=5;
    const int mod=2009;
    
    class Matrix
    {
    public:
    	int 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;
    	}
    
    	void read (int _n)
    	{
    		n=_n;      //
    		for (int i=0;i<n;i++)
    			for (int j=0;j<n;j++)
    			{
    				scanf("%d",&a[i][j]);
    				a[i][j]%=mod;
    			}
    	}
    
    	Matrix operator + (Matrix b)
    	{
    		Matrix c;
    		for (int i=0;i<n;i++)
    			for (int j=0;j<n;j++)
    				c.a[i][j]=(a[i][j]+b.a[i][j])%mod;
    		return c;
    	}
    
        Matrix operator + (int x)
    	{
    		Matrix c=*this;
    		for (int i=0;i<n;i++)
    			c.a[i][i]+=x;
    		return c;
    	}
    
    	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]%mod)%=mod;
    		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;
    	}
    
    	void print (int n)
    	{
    		for (int i=0;i<n;i++)
    			for (int j=0;j<n;j++)
    				printf(j==n?"d\n":"%d ",a[i][j]);
    	}
    }a;
    
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int T,n;
    	scanf("%d",&T);
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    	    scanf("%d",&n);
            if (n<=2)
            {
                printf("Case %d: %d\n",Cas,(n+1)*(n+1));
                continue;
            }
            a.n=4;
            a.init(0);
            a.a[0][0]=1;a.a[0][1]=3;a.a[0][2]=2;a.a[0][3]=7;
            a.a[1][1]=3;a.a[1][2]=2;a.a[1][3]=7;
            a.a[2][1]=1;
            a.a[3][2]=1;
            a=a.power(n-2);
            int ans=(a.a[0][0]*9+a.a[0][1]*5+a.a[0][2]*3+a.a[0][3])%mod;
            printf("Case %d: %d\n",Cas,ans);
    	}
    	return 0;
    }

[http_acm.fzu.edu.cn_problem.php_pid_1683]: http://acm.fzu.edu.cn/problem.php?pid=1683
[SouthEast]: /images/20220829/980ccb6b27554a2893f67fa1d6c79ef8.png