题目链接：http://codeforces.com/contest/909/problem/C
题意：
Python是没有大括号来标明语句块的，而是用严格的缩进来体现。
现在有一种简化版的Python，只有两种语句：
（1）'s'语句：Simple statements. 相当于一般语句。
（2）'f'语句：For statements. 相当于for循环，并且规定它的循环体不能为空。
然后给你一段没有缩进的Python程序，共n行(n <= 5000)。
问你添加缩进后，有多少种合法且不同的Python程序。
题解：
表示状态：
dp[i][j] = numbers
考虑到第i行，并且第i行的缩进有j个Tab时的合法方案数。
找出答案：
ans = ∑ dp[n-1][0 to n-1]
行号从0开始标。并且对于第i行来说，它的缩进最多有i个Tab。
如何转移：
两种情况。
当前为dp[i][j]（用顺推）。
（1）第i行为'f'，则第i+1行的缩进只能为j+1。
dp[i+1][j+1] += dp[i][j]
（2）第i行为's'，则第i+1行的缩进可以为[0,j]中的任意一种。
dp[i+1][0 to j] += dp[i][j]
边界条件：
dp[0][0] = 1
第0行的缩进只能为0。
树状数组优化：
如果按照上面的方程直接去写的话，枚举状态为O(N^2)，转移的第二种情况复杂度为O(N)。
所以最坏情况下为O(N^3)，对于N = 5000肯定炸了……
所以考虑用树状数组来实现转移的第二种情况，也就是区间加法和单点查询。
于是总复杂度变为O(N^2*logN)。
另外，树状数组下标从1开始，所以之前所有的下标都要+1。
update:
其实顺推也可以用差分优化掉一个n的啊……
（打比赛的时候人是瓷的……）
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 5005
#define MOD 1000000007 using namespace std; int n;
int dp[MAX_N][MAX_N];
char c[MAX_N]; void update(int *dat,int k,int x)
{
while(k>)
{
dat[k]=(dat[k]+x)%MOD;
k-=k&-k;
}
} int query(int *dat,int k)
{
int sum=;
while(k<=n)
{
sum=(sum+dat[k])%MOD;
k+=k&-k;
}
return (sum%MOD+MOD)%MOD;
} void sec(int *dat,int l,int r,int x)
{
update(dat,r,x);
update(dat,l-,-x);
} int main()
{
cin>>n;
for(int i=;i<=n;i++) cin>>c[i];
memset(dp,,sizeof(dp));
sec(dp[],,,);
for(int i=;i<=n;i++)
{
for(int j=;j<=i;j++)
{
int now=query(dp[i],j);
if(now)
{
if(c[i]=='f')
{
sec(dp[i+],j+,j+,now);
}
else
{
sec(dp[i+],,j,now);
}
}
}
}
int ans=;
for(int i=;i<=n;i++)
{
ans=(ans+query(dp[n],i))%MOD;
}
cout<<ans<<endl;
}