Codeforces Good Bye 2015 D. New Year and Ancient Prophecy 后缀数组 树状数组 dp
D. New Year and Ancient Prophecy
题目连接:
http://www.codeforces.com/contest/611/problem/C
Description
Limak is a little polar bear. In the snow he found a scroll with the ancient prophecy. Limak doesn't know any ancient languages and thus is unable to understand the prophecy. But he knows digits!
One fragment of the prophecy is a sequence of n digits. The first digit isn't zero. Limak thinks that it's a list of some special years. It's hard to see any commas or spaces, so maybe ancient people didn't use them. Now Limak wonders what years are listed there.
Limak assumes three things:
Years are listed in the strictly increasing order;
Every year is a positive integer number;
There are no leading zeros.
Limak is going to consider all possible ways to split a sequence into numbers (years), satisfying the conditions above. He will do it without any help. However, he asked you to tell him the number of ways to do so. Since this number may be very large, you are only asked to calculate it modulo 109 + 7.
Input
The first line of the input contains a single integer n (1 ≤ n ≤ 5000) — the number of digits.
The second line contains a string of digits and has length equal to n. It's guaranteed that the first digit is not '0'.
Output
Print the number of ways to correctly split the given sequence modulo 109 + 7.
Sample Input
6
123434
Sample Output
8
Hint
题意:
给你一个全是数字的字符串(长度5000),问你多少种划分方案,就可以使得这个字符串分割成了一个绝对递增序列。
题解
DP,dp[i][j]表示以i位置结尾,长度为j的字符串的方案数。转移很简单,就dp[i][j]+=dp[i-j]k,如果str[i-j+1][i]>str[i-j-j+1][i-j]的话,dp[i][j]+=dp[i-j][j]。
很显然,dp是n^3的,我们就可以用奇怪的手法去优化一下就好了,我是无脑后缀数组预处理优化的。
代码
#include<bits/stdc++.h>
using namespace std;
long long dp[5005][5005];
char str[5005];
const int mod = 1e9+7;
char s[5005];
struct Bit
{
int lowbit(int x)
{
return x&(-x);
}
long long val[5005];
int sz;
void init(int sz){
this->sz=sz;
for(int i = 0 ; i <= sz ; ++ i) val[i] = 0 ;
}
void updata(int pos ,long long key)
{
while(pos<=sz){
val[pos]+=key;
if(val[pos]>=mod)
val[pos]-=mod;
pos+=lowbit(pos);
}
}
long long query(int pos)
{
long long res=0;
while(pos>0)
{
res+=val[pos];
if(res>=mod)res-=mod;
pos-=lowbit(pos);
}
return res;
}
}bit[5005];
#define maxn 5005
const int inf=0x3f3f3f3f;
int wa[maxn],wb[maxn],wn[maxn],wv[maxn];
int rk[maxn],height[maxn],sa[maxn],r[maxn],Min[maxn][20],ok[maxn][maxn],n;
int cmp(int *r,int a,int b,int l)
{
return (r[a]==r[b])&&(r[a+l]==r[b+l]);
}
void da(int *r,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=0;i<m;i++) wn[i]=0;
for(i=0;i<n;i++) wn[x[i]=r[i]]++;
for(i=1;i<m;i++) wn[i]+=wn[i-1];
for(i=n-1;i>=0;i--) sa[--wn[x[i]]]=i;
for(j=1,p=1;p<n;j*=2,m=p)
{
for(p=0,i=n-j;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=0;i<n;i++) wv[i]=x[y[i]];
for(i=0;i<m;i++) wn[i]=0;
for(i=0;i<n;i++) wn[wv[i]]++;
for(i=1;i<m;i++) wn[i]+=wn[i-1];
for(i=n-1;i>=0;i--) sa[--wn[wv[i]]]=y[i];
for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void calheight(int *r,int *sa,int n)
{
int i,j,k=0;
for(i=1;i<=n;i++) rk[sa[i]]=i;
for(i=0;i<n;height[rk[i++]]=k )
for(k?k--:0,j=sa[rk[i]-1];r[i+k]==r[j+k];k++);
}
void makermq()
{
for(int i=1;i<=n;i++) Min[i][0]=height[i];
for(int i=1;(1<<i)<=n;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
{
Min[j][i]=min(Min[j][i-1],Min[j+(1<<i-1)][i-1]);
}
}
int ask(int a,int b)
{
int l=rk[a],r=rk[b];
if(l>r) swap(l,r);
l++;
if(l>r) return n-a;
int tmp=int(log(r-l+1)/log(2));
return min(Min[l][tmp],Min[r-(1<<tmp)+1][tmp]);
}
int check(int r,int l,int r1,int l1)
{
r--,l--,r1--,l1--;
if(r<0||l<0||r1<0||l1<0)return 0;
if(ok[l1][r]==1)return 1;
return 0;
}
long long updata(long long a,long long b)
{
return (a+b)%mod;
}
int main()
{
scanf("%d%s",&n,s+1);
for(int i=0;i<n;i++)
str[i]=s[i+1];
for(int i=0;i<n;i++)
r[i]=str[i];
r[n]=0;
da(r,sa,n+1,256);
calheight(r,sa,n);
makermq();
for(int i = 0 ; i <= n ; ++ i) bit[i].init(n);
for(int i = 0 ; i < n ; ++ i)
for(int j = i + 1 ; j < n ; ++ j)
if((j-i)%2==1){
int tmp=ask(i,i+(j-i+1)/2);
if(i+tmp>=i+(j-i+1)/2||str[i+tmp]>=str[i+(j-i+1)/2+tmp]) ok[i][j]=0;else ok[i][j]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
if(s[i-j+1] == '0')
continue;
dp[i][j] = 0 ;
if(i-j == 0) dp[i][j] ++ ;
dp[i][j] += bit[i-j].query(j - 1);
if(i-j!=0&&(i-j-j+1)>0){
if(ok[i-j-j][i-1])
dp[i][j] += bit[i-j].query(j)-bit[i-j].query(j-1);
}
if(dp[i][j]>=mod)dp[i][j]%=mod;
bit[i].updata(j,dp[i][j]);
}
}
cout<<bit[n].query(n)<<endl;
return 0;
}
最新文章
- MYSQL MHA
- Android帧动画
- OkHttp使用进阶 译自OkHttp Github官方教程
- STL--集和多集(set/multiset)
- request.getAttribute() 和 request.getParameter() 有何区别?
- linux设备驱动归纳总结(三):5.阻塞型IO实现【转】
- js获取滚动条距离浏览器顶部,底部的高度,兼容ie和firefox
- 免费邮件服务器:MailEnable
- 翻转句子中单词的顺序 C语言
- 构建安全的Xml Web Service系列之初探使用Soap头
- setTimeout与setInterval的区别
- Bank Interest
- 用javascript做别踩白块游戏1
- Redis集群管理
- 【原创】大叔经验分享(49)hue访问hdfs报错/hue访问oozie editor页面卡住
- php中的echo 与print 、var_dump 的区别
- mybatis 学习笔记 -详解mybatis 及实例demo
- vue之node.js的简单介绍
- [daily][tcpdump][bpf] 如何用tcpdump抓到一个分片包
- URL的解析,C语言实现
热门文章
- Nginx - Windows下Nginx基本安装和配置
- PyPI镜像网站
- 程序世界系列之-struts2安全漏洞引发的安全杂谈(上)
- Page 63-64 Exercises 2.3.7 -------Introduction to Software Testing (Paul Ammann and Jeff Offutt)
- @Html.Raw()
- Linux-sort用法
- macos+apache+php+phpmyadmin 的整合过程梳理
- Maven安装与全局profile配置
- Camel In Action 阅读笔记 第一章 认识Camel 1.1 Camel 介绍
- Hadoop2.2.0 手动切换HA环境搭建