hihocoder 1987 字符串hash+dp

链接http://hihocoder.com/problemset/problem/1987

题意：

输入一个长度为n的字符串，问有多少种划分方式使得划分后的每个字符串都是循环串。循环串定义为：对于一个字符串A，如果存在不等于A的字符串B使得连续若干个B连接起来后可以组成A，那么称A为循环串。

例如AABAAB就是循环串，而AABAAC则不是。

答案可能很大，输出对1e9+7取模。

思路：

暴力hash dp一下，枚举子串，然后往后比较，复杂度很好分析，一个"循环串"最多被枚举它的因数的次数，显然是sqrt(n)的，那么知道了所有的"循环串"就可以dp了，就是首尾相接的可以转移。dp[R]=(dp[R]+dp[L-1]),同时注意一个“循环串”只统计一次。

代码：

#include 
#define LL long long
#define pii pair
#define PB push_back
#define X first
#define Y second
using namespace std;
const int maxn = 1005,seed=131,mod = 1e9+7;
LL p[maxn],s[maxn];
string str;
LL add(LL a,LL b){
    return (a+b)%mod;
}
LL mul(LL a,LL b){
    return (a*b)%mod;
}
LL sub(LL a,LL b){
    return (a-b+mod)%mod;
}
LL get_hash(int l ,int r){
    l++,r++;
    return sub(s[r],mul(s[l-1],p[r-l+1]));
}

LL dp[maxn],vis[maxn];

void find_pair(int n){
    for(int i=0;i>t;
    while(t--){
        cin>>n>>str;
        p[0]=1;s[0]=0;
        for(int i=0;i<=n;i++) dp[i]=0;
        for(int i=1;i<=n;i++)p[i]=mul(p[i-1],seed);
        for(int i=1;i<=n;i++)s[i]=add(mul(s[i-1],seed),str[i-1]);
        find_pair(n);
        cout<