矩阵乘法模板之hdu——1751

比眉伴天荒 2022-08-10 14:52 150阅读 0赞

题目大意：f(x)满足：

If x < 10 f(x) = x.  
If x >= 10 f(x) = a0 \* f(x-1) + a1 \* f(x-2) + a2 \* f(x-3) + …… + a9 \* f(x-10);  
And ai(0<=i<=9) can only be 0 or 1 .  
给出a0——a9的值，求出f（k）%m为多少。 此题用到了矩阵乘法和快速幂计算，code如下：

#include<cstdio>
    #include<cstring>
    const int N=10;
    int m;
     struct matrix
    {
    	__int64  a[N][N],r,c;
    };
    matrix m_mul(matrix x,matrix y)
    {
    	matrix z;
    	z.r=x.r;z.c=y.c;
    	memset(z.a,0,sizeof(z.a));
    	int i,j,k;
    	for(i=0;i<z.r;i++)
    	for(j=0;j<z.c;j++)
    	{
    		for(k=0;k<x.c;k++)
    		z.a[i][j]+=(x.a[i][k]*y.a[k][j])%m;
    		if(z.a[i][j]>=m) z.a[i][j]%=m;
    	}
    	return z;
    }
    matrix q_pow(matrix x ,int k)
    {
    	matrix unit;int i;
    	memset(unit.a,0,sizeof(unit.a));
    	unit.r=x.r;unit.c=x.c;
    	for(i=0;i<x.r;i++)
    	unit.a[i][i]=1;
    	if(k==0)
    	return unit;
    	while(k)
    	{
    		if(k&1)unit=m_mul(unit,x);
    		x=m_mul(x,x);
    		k>>=1;
    	}
    	return unit;
    }
    int main()
    {
    	int K,i;matrix in;
    	while(scanf("%d%d",&K,&m)==2)
    	{
    		memset(in.a,0,sizeof(in.a));
    		for(i=0;i<10;i++)
    			{
    				scanf("%I64d",&in.a[0][i]);
    				in.a[i][i-1]=1;
    			}
    		in.r=in.c=10;
    		matrix t_res,res,init;
    		for(i=0;i<10;i++)
    			init.a[i][0]=9-i;
    		init.c=1;init.r=10;
    		if(K>9)
    		{
    			t_res=q_pow(in,K-9);
    			res=m_mul(t_res,init);
    		/*	for(int l=0;l<10;++l)
    			{
    				for(int j=0;j<10;j++)
    				printf("%I64d ",res.a[l][j]);
    				printf("\n");
    			}
    			*/
    			printf("%I64d\n",res.a[0][0]);
    		}
    		else printf("%I64d\n",res.a[K][0]);
    	}
    	return 0;
    }

自己改了一下代码结果改了好久也没改对先放这吧，以后再看看。

#include<cstdio>
    #include<cstring>
    using namespace std;
    const int n=10;
    int K,m;
    struct matrix
    {
        __int64  a[n][n];
        matrix operator*(const matrix&x)
        {
            matrix t;
            int i,j,k;
            memset(t.a,0,sizeof(t.a));
            for (i=0; i<n; ++i)
            for (j=0; j<n; ++j)
            {
     		 	for (k=0; k<n; ++k)
            	t.a[i][j]+=(a[i][k]*x.a[k][j])%m;
                if (t.a[i][j]>=m)t.a[i][j]%=m;
             }
            //return memcpy(a,t.a,sizeof(a)),*this;
            return t;
        }
    } in,unit;
    int main()
    {
       while(scanf("%d%d",&K,&m)==2)
       {
        	int i,j;
        	for (i=0; i<10; ++i)
        	{
    			scanf("%I64d",&in.a[0][i]);
    			if(i>0)in.a[i][i-1]=1;
        	}
    		int sign=K;
    		if(sign>9)
    		{
    			memset(unit.a,0,sizeof(unit.a));
    			for(i=0;i<n;i++)
    			unit.a[i][i]=1;
    			int coun=K-9;
    			while(coun!=0)
    			{
    				if(coun&1)unit=unit*in;
    				in=in*in;
    				coun>>=1;
    			}
    			/*for(i=0;i<10;i++)
    			{
    				for(j=0;j<10;j++)
    				printf("%I64d ",unit.a[i][j]);
    				printf("\n");
    			}*/
        		int sum=0;
        		for(i=0;i<n;i++)
        		sum=(sum+unit.a[0][i]*(9-i))%m;
        		printf("%d\n",sum);
    		}
    		else printf("%d\n",sign);
       }
        return 0;
    }

在其他博客看到一段代码（虽然不是这一题的），当时就觉得你能不能再美一些......

#include<cstdio>
    #include<cstring>
    using namespace std;
    int i,j,k,n,l,m,r;
    bool s[32];
    struct matrix
    {
        int a[30][30];
        void pr()
        {
            for(i=0; i<n;printf("%d/n",a[i++][j]))
                for(j=0;j<n-1;++j)printf("%d ",a[i][j]);
        }
        matrix& operator+=(const matrix&x)
        {
            for(int i=0; i<n; ++i)
                for(int j=0; j<n; ++j)
                if(x.a[i][j])
                {
                    a[i][j]+=x.a[i][j];
                    if(a[i][j]>=m)a[i][j]%=m;
                }
            return *this;
        }
        matrix& operator*=(const matrix&x)
        {
            matrix t;
            int i,j,k;
            for(i=0; i<n; ++i)
                for(j=0; j<n; ++j)t.a[i][j]=0;
            for(i=0; i<n; ++i)
                for(k=0; k<n; ++k)
                    if(a[i][k])
                        for(j=0; j<n; ++j)
                        {
                            t.a[i][j]+=a[i][k]*x.a[k][j];
                            if(t.a[i][j]>=m)t.a[i][j]%=m;
                        }
            return memcpy(a,t.a,sizeof(a)),*this;
        }
    } t,a,unit,ans,exp;
    int& fun(int &a)
    {
        return a;
    }
    int main()
    {
        for(scanf("%d%d%d",&n,&l,&m),i=0; i<30; ++i)unit.a[i][i]=1;
        for(i=0; i<n; ++i)
            for(j=0; j<n; ++j)
                scanf("%d",a.a[i]+j);
        for(r=-1;l;l>>=1)s[++r]=l&1;
        for(ans=exp=a; --r>=0; exp*=exp,s[r]?exp*=a:exp)
            t=exp,s[r]?ans*=(t*=a)+=unit,ans+=(t=exp)*=a:ans*=t+=unit;
        ans.pr();
        return 0;
    }