注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 2326 (hnoi2011) 数学作业  

2013-02-13 00:11:21|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2011年的暑假,一群正在从初二升到初三的小屁孩们听一个发型诡异、身穿拖鞋的大神讲矩阵乘法……

第一道题叫斐波那契

第二道题就是数学作业了……

 

言归正传

一个一行三列的矩阵:F[i] i 1

一个三行三列的矩阵:10^k   0 0

                                   1        1 0

                                   1        1  1

乘起来之后

一个一行三列的矩阵:F[i+1]  i+1  1

没了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef unsigned long long LL;
int mod;
struct Matrix
{
    int n,m;
    LL digit[5][5];
    friend Matrix operator * (const Matrix &a,const Matrix &b)
    {
        Matrix c;
        c.n=a.n,c.m=b.m;
        memset(c.digit,0,sizeof(c.digit));
        for(int i=1;i<=c.n;i++)
            for(int j=1;j<=c.m;j++)
                for(int k=1;k<=a.m;k++)
                    c.digit[i][j]=(c.digit[i][j]+a.digit[i][k]*b.digit[k][j])%mod;
        return c;
    }
}square,ans;
int Len(LL p)
{
    int len=0;
    for(LL i=p;i;i/=10)
        len++;
    return len;
}
LL Ten(int len)
{
    LL p=1;
    for(int i=1;i<=len;i++)
        p*=10;
    return p;
}
Matrix power(Matrix p,LL n)
{
    Matrix ans;
    ans.n=ans.m=p.n;
    for(int i=1;i<=ans.n;i++)
    {
        for(int j=1;j<=ans.n;j++)
            ans.digit[i][j]=0;
        ans.digit[i][i]=1;
    }
    while(n)
    {
        if(n&1)  ans=ans*p;
        p=p*p,n>>=1;
    }
    return ans;
}
LL calc(LL B1,LL A1,LL A2,LL n)
{
    B1%=mod,A1%=mod,A2%=mod;
    square.n=3,square.m=3;
    square.digit[1][1]=B1,square.digit[1][2]=0,square.digit[1][3]=0;
    square.digit[2][1]=1,square.digit[2][2]=1,square.digit[2][3]=0;
    square.digit[3][1]=1,square.digit[3][2]=1,square.digit[3][3]=1;
    ans.n=1,ans.m=3;
    ans.digit[1][1]=A1,ans.digit[1][2]=A2,ans.digit[1][3]=1;
    ans=ans*power(square,n);
    return ans.digit[1][1];
}
LL work(LL L,LL R)
{
    int len=Len(R)-1;
    LL ans=0;
    for(int i=0;i<len;i++)
        ans=calc(Ten(i+1),ans,Ten(i)-1,9*Ten(i));
    ans=calc(Ten(len+1),ans,Ten(len)-1,R-Ten(len)+1);
    return ans;
}
int main()
{
    LL n;
    cin>>n>>mod;
    cout<<work(1,n)<<endl;
    return 0;
}


  评论这张
 
阅读(449)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017