TopCoder SRM 666 Div1 444 SumOverPermutations

感觉是道好题～TC好多题就这样，想半天，然后代码几行就完了。
原来碰到这种排列的dp就一脸懵逼，因为状态特别难设计，每次都感觉只会状压，现在终于有点get到其中的套路了。

在这题里我们可以发现几个事实

每个位置对答案的贡献只和它左右两边是否比它早确定有关
我们可以通过将 $i$ 插入 $1$ 到 $i - 1$ 的排列中得到所有 $1$ 到 $i$ 的所有排列

于是我们可以弄一个 $f [o] [i] [j]$ 表示到第 $o$ 个位置，这个位置在前 $o$ 个里面是第 $i$ 个确定的，以及前一个位置是否比它早确定， $j = 0$ 表示早， $j = 1$ 表示晚。
转移的话就枚举一下第 $o + 1$ 个位置是第几个被确定的。然后这样复杂度还是 $O (n^{3})$ 爆炸，于是就加个前缀和优化，再顺便滚动数组一下就过了。

然而，我一开始T了！！！震惊，说好的TC一秒1e9呢（雾），欺骗感情！！
结果发现是我手动取模爆炸了。。。。。。改了就过了。。。。。。

#include <bits/stdc++.h>
#define fr(i,x,y) for(int i=x;i<=y;i++)
#define ll long long
using namespace std;
const int N=4001;
const int p=1e9+7;
ll f[2][N][2];

template<class T> void checkmin(T &a,const T &b) { if (b<a) a=b; } 
template<class T> void checkmax(T &a,const T &b) { if (b>a) a=b; }

class SumOverPermutations {
public:
    int findSum( int n ) ;
};

void Add(ll &x,ll y){
	x+=y;
	while(x<0) x+=p;
	while(x>=p) x-=p;
}

int SumOverPermutations::findSum(int n) {
    int cur=1;
    f[1][1][1]=1;
    fr(o,2,n){
    	cur^=1;
    	//memset(f[cur],0,sizeof f[cur]);
    	fr(i,1,o){
    		f[cur][i][0]=f[cur][i][1]=0;
    		Add(f[cur][i][0],(n-1)*f[cur^1][i-1][0]%p+n*f[cur^1][i-1][1]%p);
    		Add(f[cur][i][1],(n-2)*(f[cur^1][o-1][0]-f[cur^1][i-1][0])%p);
    		Add(f[cur][i][1],(n-1)*(f[cur^1][o-1][1]-f[cur^1][i-1][1])%p);
    	}
    	if (o==n) continue;
    	fr(i,1,o){
    		Add(f[cur][i][0],f[cur][i-1][0]);
    		Add(f[cur][i][1],f[cur][i-1][1]);
    	}
    }
    ll ans=0;
    fr(i,1,n){
    	Add(ans,f[cur][i][0]*(n-1)%p);
    	Add(ans,f[cur][i][1]*n%p);
    }
    return ans;
}