题意：给定T串只含小写字母的字符串，对于每串，输出回文字串的数目模10007
思路：区间合并，对于从第i个字符到第j个字符的串里面
（1）如果str[i]!=str[j],则dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]，即回文串在[i,j-1]的情况数加上[i+1,j]的情况数，再减去两种重叠部分的情况数，即属于[i+1,j-1]的情况数。
（2）如果str[i]==str[j],则dp[i][j]=(dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1])+（dp[i+1][j-1]+1）=dp[i+1][j]+dp[i][j-1]+1,即回文串在[i,j-1]的情况数加上[i+1,j]的情况数，再减去两种重叠部分的情况数，再加上由两端在同一个回文串中点所造成的新情况数，这些情况数为dp[i+1][j-1]+1（原来在[i+1,j-1]的回文串加上两端点造成的情况为dp[i+1][j-1],只含两端点的情况数为1，一共就是dp[i+1][j-1]+1）
（3）注意i==j的情况，dp[i][j]=1。另外，中间过程可能会有负数，因此取模前要加上10007
#include<stdio.h>
#include<string.h>
#define M 10007
#define MAXN 1005
int ca=0,T,i,j,k,dp[MAXN][MAXN];
char str[MAXN];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%s",str);
int n=strlen(str);
for(k=0;k<n;++k)
for(i=0;i+k<n;++i)
{
j=i+k;
if(!k) {dp[i][j]=1;continue;}//dp[i][i]=1;
if(str[i]==str[j]) dp[i][j]=(dp[i+1][j]+dp[i][j-1]+1+M)%M;
else if(k>1) dp[i][j]=(dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]+M)%M;
else dp[i][j]=(dp[i+1][j]+dp[i][j-1]+M)%M;//防止出现i+1>j-1的时候访问dp[i+1][j-1]，此时显然dp[i+1][j-1]=0，直接略去
}
printf("Case %d: %d\n",++ca,dp[0][n-1]);
}
return 0;
}