BZOJ 2302 HAOI 2011 Problemcダイナミックプランニング

n人とn人の位置を与えて、1つのシーケンスaiを生成することを要求して、それから第1...n人は順番にa 1まで歩いて...n席、その席に人がいたら次の席に行って、空席が見つかるまで座ってください.n番目の席を探しても見つからない場合は、このシーケンスが合法ではないと言います.現在、aiがいくつか確定しています.合法的なシーケンスの数を求めています.
1つのシーケンスが合法的に番号≦iに等しい人は少なくともiつあってからDP辛いことができます.のfi,jが番号≦iを示す人にj個のシナリオ数,cntiが確定番号iを示す人の個数,sumiが番号≦iを示す人の個数ならfi,j=Σj−i+1 k=cntifi−1,j−k残りの人の中からk−cnti個人を選んでその番号をi時間複雑度O(Tn 3)にして1晩車に戻ることを少なくして・・・私は本当に年を取ったなぁ・・・

#include 
#include 
#include 
#include 
#define M 330
using namespace std;
int n,m,p;
int cnt[M],sum[M];
long long C[M][M],f[M][M];
void Initialize()
{
    int i,j;
    memset(cnt,0,sizeof cnt);
    memset(C,0,sizeof C);
    memset(f,0,sizeof f);
    for(i=0;i<=n;i++)
        for(C[i][0]=1,j=1;j<=i;j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
}
int main()
{
    int T,i,j,k,x;
    for(cin>>T;T;T--)
    {
        cin>>n>>m>>p;
        sum[0]=n-m;
        Initialize();
        for(i=1;i<=m;i++)
            scanf("%*d%d",&x),cnt[x]++;
        for(i=1;i<=n;i++)
        {
            sum[i]=sum[i-1]+cnt[i];
            if(sum[i]puts("NO");
                break;
            }
        }
        if(i!=n+1) continue;
        f[0][0]=1;
        for(i=1;i<=n;i++)
            for(j=sum[i];j>=i;j--)
                for(k=j-i+1;k>=cnt[i];k--)
                    (f[i][j]+=f[i-1][j-k]*C[sum[i]-j+k-cnt[i]][k-cnt[i]])%=p;
        printf("YES %d
",(int)f[n][n]);
    }
    return 0;
}