寻找母串
Time Limit: 2000/1000 MS (Java/Others) Memory Limit:32768/32768 K (Java/Others)
Total Submission(s): 33 Accepted Submission(s): 18
Problem Description
对于一个串S,当它同时满足如下条件时,它就是一个01偏串:
1、只由0和1两种符组成;
2、在S的每一个前缀中,0的个数不超过1的个数;
3、S中0的个数和1的个数相等。
现在给定01偏串S,请计算一下S在所有长度为n的01偏串中作为子串出现的次数的总和。
由于结果比较大,结果对1e9+7取余后输出。
样例解释:
在第二个样例中,长度为4的偏串共两个1010,1100。10在1010中出现了两次,在1100中出现了1次。所以答案是3。
Input
第一行给出一个整数T(1<=T<=40),表示测试数据的数目。
每一组测试包含一个整数n和字符串S,中间用空格分开。(1<=|S|<=100000,1<=n<=1000000000)
输入保证S是一个01偏串。
Output
对于每一组数据,输出一个整数占一行,表示答案。
Sample Input
2
2 10
4 10
Sample Output
1
3
【题意】
RT
【思路】
前置知识:其实这道题很显然与卡特兰数有关,你把1换成{,把0换成}不就变成了我们熟悉的卡特兰数的经典例题:括号匹配数了吗(还可以转化为出栈入栈顺序数)。那么显然长度为n的01偏串个数为Catalan(n/2)。
题目要求的是包含所给01偏串的01偏串SS的数量,显然我们根据01偏串的定义可以知道满足条件的SS去掉所给01偏串后得到的序列依然是一个01偏串,因为去掉的一部分0,1数量相等,对剩下的不会造成影响。那么我们只要去考虑去掉所给01偏串后的序列有几个即可。
设题目所给|S|=m,那么去掉后的序列长度为(n-m),由前置知识得01偏串的个数为Catalan((n-m)/2)。
接下来分析上面得到的个数跟结果的关系,假设T为其中的一个01偏串,其长度为(n-m),那么我们需要最的便是把S插入到T中,显然有(n-m+1)个位置可以插入。那么最终结果便是Catalan((n-m)/2)*(n-m+1).
有的人可能要问了,你这样不是会重复计数吗?对,会重复计数,但仔细看题目,题目要求的是出现次数,所以重复了并没有关系。
做到这里其实只完成了最基础的部分,因为数据范围很大,如何求卡特兰数成为了一个很大的问题。不过方法还是有的,即利用分块打表,每10000个卡特兰数打一次表,即算出第10000*x个卡特兰数,然后再利用递推公式计算结果(打表的区间也不能太小,表太大好像会无法提交,区间太大的话易超时)
附卡特兰数的递推公式:
因为递推公式里涉及到除法,所以需要求逆元,我下面的程序里用的是拓展欧几里得,但由于1e9+7为质数,也可以用费马定理求逆元。
附打表程序(打完表需要很长时间…)
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)
typedef long long ll;
const int maxn = 3005;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int mod_inverse(int a,int m)
{
int x,y;
exgcd(a,m,x,y);
return (x%m+m)%m;
}
int main()
{
//freopen("output.txt","w",stdout);
ll num=1;
printf("{1");
for(int i=1;i<=500000000+5;i++)
{
num=(4*i-2)%mod*num%mod*mod_inverse(i+1,mod)%mod;
//或num=(4*i-2)%mod*num%mod*fast_mod(i+1,mod-2,mod)%mod;
if(i%100000==0)
{
printf(",%I64d",num);
}
}
puts("}");
return 0;
}
完整代码
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)
typedef long long ll;
const int maxn = 100005;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
ll cal[5005]={1,945729344......790947898,142578126}; //表太长,见最下面链接
char s[maxn];
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int mod_inverse(int a,int m)
{
int x,y;
exgcd(a,m,x,y);
return (x%m+m)%m;
}
ll solve(int x)
{
int cnt=x/100000;
ll start=cal[cnt];
for(int i=cnt*100000+1;i<=x;i++)
{
start=(4*i-2)%mod*start%mod*mod_inverse(i+1,mod)%mod;
}
return start;
}
int main()
{
int n;
rush()
{
scanf("%d%s",&n,s);
int len=strlen(s);
int m=(n-len);
if(m<0||m&1)
{
puts("0");
continue;
}
ll temp=solve(m/2); //算出卡特兰数
ll ans=temp*(n-len+1)%mod;
printf("%I64d\n",ans);
}
return 0;
}
卡特兰数表