矩阵乘法专题4——bzoj 2326 [HNOI2011] 数学作业 题解

转载请注明：http://blog.csdn.net/jiangshibiao/article/details/24963747

【原题】

Description

【分析】我们按数字的位数来划分。对于K位数，我们就可以专门设计一个矩阵来计算。

然后就是注意细节了。

【代码】

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
struct matrix
{ll p[4][4];int n,m;matrix(){memset(p,0,sizeof(p));}
}res,a;
ll MOD,n,chen,i,ans;
matrix operator * (matrix a,matrix b){matrix c;c.n=a.n;c.m=a.m;for (int i=1;i<=a.n;i++)for (int j=1;j<=b.m;j++)for (int k=1;k<=a.m;k++)  c.p[i][j]=(c.p[i][j]+1ll*a.p[i][k]*b.p[k][j])%MOD;return c;}
void make_matrix()
{a.p[1][2]=a.p[1][3]=a.p[2][3]=0ll;a.p[2][1]=a.p[2][2]=a.p[3][1]=a.p[3][2]=a.p[3][3]=1ll;a.p[1][1]=chen%MOD;a.n=3;a.m=3;res.p[1][2]=(chen/10-1ll)%MOD;res.p[1][3]=1ll;res.n=1;res.m=3;
}
void quick(ll b)
{bool flag=true;while (b){if (b&1ll) res=res*a;b=b/2ll;a=a*a;}
}
int main()
{scanf("%lld%lld",&n,&MOD);res.p[1][1]=0ll;chen=1ll;for (i=1;i<=18;i++){chen*=10ll;make_matrix();quick((chen<=n)?(chen/10*9ll):(n-chen/10+1ll));if (chen>n) break;}printf("%lld",res.p[1][1]);return 0;
}