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

ydc的博客

 
 
 

日志

 
 

bzoj 1361 孪生项链  

2014-01-16 09:16:44|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
楼教当年现场A的题……

第一问的话,我算是知道了……如果一个串循环之后和原串一样的话那么就一定是以这个长度为周期的串
这样的话就能计数了
第二问的构造很神……我是打死都没想到
求串S的后继
构造方法:
将S不断重复……成一个无限长的串
取前n位
将这个串当做整数,+1
然后再把整数看作串,末尾的0去掉
证明:
先证合法性再证最优性
设s为原串,t为新串
len=strlen(s)
每len位看作一个小节
多出来的一部分看作一个小节
容易证明最后一个小节肯定大于前面的每一个小节(当然前面的小节都相等)
假设他有循环表示t'
如果t'的开头是某小节的开头
比较t和t'的大小……会一些小节两两抵消之后让t'末尾小节与t的中间小节大小相等……所以说明t的末尾小节-1小于t的前面的小节。于是s不合法了
如果t'的开头不是某小节的开头……前len位一定是s的循环循环表示,所以前len位>s……那么t'就肯定>t了
然后是最优性……
s和str(int(s)+1)之间应该是再也插不进任何串进去了把

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 400010
#define maxm 1010
#define mod 1000000000
using namespace std;
typedef long long LL;
struct bign
{
int digit[50],n;
friend bign operator * (const bign &a,int p)
{
static bign b;
int jinwei=0;
memset(b.digit,0,sizeof(b.digit));
b.n=a.n;
for(int i=1;i<=b.n;++i)
{
b.digit[i]=a.digit[i]*p+jinwei;
jinwei=b.digit[i]/mod;
b.digit[i]%=mod;
}
if(jinwei)
b.digit[++b.n]=jinwei;
return b;
}
void operator -= (const bign &b)
{
int tuiwei=0;
for(int i=1;i<=n;++i)
{
digit[i]=digit[i]+mod-b.digit[i]-tuiwei;
tuiwei=(digit[i]/mod)^1;
digit[i]%=mod;
}
for(;n>1&&digit[n]==0;--n);
}
void operator /= (int p)
{
int tmp,rem=0;
for(int i=n;i>=1;--i)
tmp=digit[i],digit[i]=((LL)rem*mod+tmp)/p,rem=((LL)rem*mod+tmp)%p;
for(;n>1&&digit[n]==0;--n);
}
void print()
{
printf("%d",digit[n]);
for(int i=n-1;i>=1;--i)
printf("%09d",digit[i]);
printf("\n");
}
}power[maxm],f[maxm];
int n,m,k;
char str[maxn];
void read()
{
scanf("%d %d %d",&n,&m,&k);
scanf("%s",str+1);
}
void work()
{
power[0].n=1,power[0].digit[1]=1;
for(int i=1;i<=k;++i)
power[i]=power[i-1]*2;
for(int i=1;i<=k;++i)
if(k%i==0)
f[i]=power[i];
for(int i=1;i<=k;++i)
if(k%i==0)
for(int j=i+i;j<=k;j+=i)
if(k%j==0)
f[j]-=f[i];
f[k]/=k;
f[k].print();
int len=strlen(str+1);
for(int now=len;now<=n;)
for(int i=1;i<=len;++i)
str[++now]=str[i];
for(;n>=1&&str[n]=='1';--n);
++str[n];
if(n==0)
printf("1\n");
else
{
for(int i=1;i<=n;++i)
printf("%c",str[i]);
printf("\n");
}
}
int main()
{
read();
work();
return 0;
}


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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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