题目链接：http://hihocoder.com/problemset/problem/1149

题意：中文的。

dp(i,j)表示[i,j]区间内的回文串数量。

如果s[i]!=s[j]，dp(i,j)=dp(i+1,j)+dp(i,j-1)-dp(i+1,j-1)

如果s[i]==s[j]，dp(i,j)=dp(i+1,j)+dp(i,j-1)+1

注意取模

1 #include 
     
       2 using namespace std; 3  4 const int maxn = 1010; 5 const int mod = 100007; 6 int n; 7 char s[maxn]; 8 int dp[maxn][maxn]; 9 10 int main() {11   //freopen("in", "r", stdin);12   int T, _ = 1;13   scanf("%d", &T);14   while(T--) {15     scanf("%s", s); n = strlen(s);16     memset(dp, 0, sizeof(dp));17     for(int i = 0; i < n; i++) dp[i][i] = 1;18     for(int i = 0; i < n; i++) {19       for(int j = i-1; j >= 0; j--) {20         if(s[i] != s[j]) dp[j][i] = dp[j+1][i] + (dp[j][i-1] - dp[j+1][i-1] + mod) % mod;21         else dp[j][i] = dp[j+1][i] + dp[j][i-1] % mod + 1 % mod;22       }23     }24     printf("Case #%d: %d\n", _++, dp[0][n-1] % mod);25   }26   return 0;27 }