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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ2326】【HNOI2011】【数学作业】  

2014-04-01 19:53:49|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
     这是从3月30日开始的坑....
     本来准备尽量努力刷bzoj第一版后开始刷一些省选题的,然后咱是蒟蒻 略刷不动了 =v=....
     于是提前开始了...然后DT的就是 勾股定理 TAT 因为一个很囧的语法错误调试了两天...中途还刷了一些水题...
     不管怎样总算开始了....
     这题就直接把当时在记事本里的东西搬出来了....
============记事本的=================
      最近貌似全国都下雨了233...然后不知道为什么咱的网速各种慢...连博客和bzoj都打不开了囧= =,然后就做一些离线的东西...
      其实bzoj准备尽量刷完第一版就开始刷省选的题目,这就当做提前开始吧...
      bless all。
      先做HNOI2011的题目了...
      题目大意:求concatenate(n) mod m,其中concatenate(n)表示 1~n连起来的数字的和。比如concatenate(5)=12345 mod m

      貌似以前学姐给咱出过类似的题目......
      设 an=concatenate(n)
      对于1<=i<=9,ai=ai-1*10+i;
      对于10<=i<=99,ai=ai-1*100+i;
      对于100<=i<=999,ai=ai-1*1000+i;
      然后以此类推...当然上面的后面都加个取模m。
      然后对于递推式,可以用矩阵做。分类用矩阵做即可。
      答案矩阵设作:
      [0,0,0,1](每一个代表的意思为[ai,ai-1,i,1])
      比如当1<=i<=9的时候相乘的矩阵应该是
      [10 1 0 0
         0 0 0 0
         1 0 1 0
         1 0 1 1]
      然后每一次算完一种情况往上递增的时候只需要把 矩阵中的 (1,1)即10那项乘以10即可。 讨论比较麻烦,但是只要细心就可以了。

program hnoi2011day1a;
type arr=array[0..4,0..4]of int64;
var n,m,now,sum:int64;
    sav,ans,b:arr;
function quickadd(a,b:int64):int64;
var sum:int64;
begin
  sum:=0;
  while b<>0 do
   begin
     if b and 1=1 then sum:=(sum+a)mod m;
     b:=b shr 1;
     a:=(a+a)mod m;
   end;
  exit(sum);
end;

procedure cheng(a,b:arr;var c:arr);
var i,j,k:longint;
begin
  fillchar(c,sizeof(c),0);
  for i:=1 to 4 do
   for j:=1 to 4 do
     for k:=1 to 4 do
       c[i][j]:=(c[i][j]+quickadd(a[i][k],b[k][j]))mod m;
end;

procedure quickmod(n:int64);
begin
  while n<>0 do
   begin
     if n and 1=1 then cheng(ans,b,ans);
     n:=n shr 1;
     cheng(b,b,b);
   end;
end;

procedure init;
var i:longint;
begin
  read(n,m);
  now:=9;
  fillchar(b,sizeof(b),0);
  b[1][1]:=10;b[1][2]:=1;
  b[3][1]:=1;b[3][3]:=1;
  b[4][1]:=1;b[4][3]:=1;b[4][4]:=1;
  sav:=b;
  fillchar(ans,sizeof(ans),0);
  for i:=1 to 4 do ans[i][i]:=1;
  while true do
   begin
     sum:=now-((now+1)div 10);
     if now<n then quickmod(sum+ord(sum<>9))
              else
               begin
                quickmod(n-((now-9)div 10));
                break;
               end;
     now:=now*10+9;
     sav[1][1]:=sav[1][1]*10;
     b:=sav;
   end;
  write(ans[4][1]);
end;

begin
  init;
end.

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

历史上的今天

评论

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

页脚

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