百度之星：尋找母串/HDU 6084 尋找母串

• 題目
• • 題目大意：
• 解析
• 代碼

題目

題目連結

Problem Description
對于一個串S，當它同時滿足如下條件時，它就是一個01偏串：
 1、隻由0和1兩種符組成； 
 2、在S的每一個字首中，0的個數不超過1的個數；
 3、S中0的個數和1的個數相等。
現在給定01偏串S，請計算一下S在所有長度為n的01偏串中作為子串出現的次數的總和。 由于結果比較大，結果對1e9+7取餘後輸出。

Sample Input
2
2 10
4 10

Sample Output
1
3
樣例解釋：
在第二個樣例中，長度為4的偏串共兩個1010，1100。10在1010中出現了兩次，在1100中出現了1次。是以答案是3。
Input
第一行給出一個整數T(1<=T<=40),表示測試資料的數目。 每一組測試包含一個整數n和字元串S，中間用空格分開。(1<=|S|<=100000，1<=n<=1000000000)
輸入保證S是一個01偏串。
Output
對于每一組資料，輸出一個整數占一行，表示答案。
           

題目大意：

對于一個串S，當它同時滿足如下條件時，它就是一個01偏串：

1. 隻由0和1兩種符組成；
2. 在S的每一個字首中，0的個數不超過1的個數；

3. S中0的個數和1的個數相等。

   現在給定01偏串S，請計算一下S在所有長度為n的01偏串中作為子串出現的次數的總和。

   由于結果比較大，結果對 1 0 9 + 7 10^9+7 109+7取餘後輸出。

解析

打表？暴力？額，好像不會做。

其實01偏串實際上等價于合法括号序列，在合法括号序列中取出一個合法括号序列之後剩下的一定也是一個合法括号序列

是以我們計算 n − l e n S n-lenS n−lenS的合法括号序列數，乘上 S S S在 n n n中的位置種類即可，計算卡特蘭數時候因為模比較大，我們采用分段打表。注意n-s<0||(n-s)%2==1條件的特判。

然後一開始打 s q r t ( n ) sqrt(n) sqrt(n)的表，代碼長度超限

打 1 0 5 10^5 105還是超。。

于是 1 0 6 10^6 106終于過了

本來要是還不過就不會了。。

代碼

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const LL MOD=1000000007,blk=500000;
const LL lst[2001]={……};
int T,n,s;
char ss[1000010];
LL Fact(LL x){
    if(x<0)return 0;
    LL res=lst[x/blk];
    for(LL i=(x/blk)*blk+1;i<=x;i++)res=(res*i)%MOD;
    return res;
}
LL power(LL a,LL b){
    if(b==0)return 1;
    if(b&1)return(power(a,b-1)*a)%MOD;
    LL t=power(a,b/2);return (t*t)%MOD;
}
LL C(LL a,LL b){
    if(a<0||b<0||a<b)return 0;
    return(Fact(a)*power(Fact(a-b),MOD-2)%MOD*power(Fact(b),MOD-2))%MOD;
}
LL Calc(int x){return (C(2*x,x)-C(2*x,x-1)+MOD)%MOD;}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d %s",&n,ss);
        s=strlen(ss);
        if(n-s<0||(n-s)%2==1)puts("0");
        else printf("%d\n",Calc((n-s)/2)*(n-s+1)%MOD);
    }return 0;
}