START204——Perfect Matching

思路讲解

我发现，这个还是要解偶，就是说，我们要得到放的种类数，但是这个“种类”，就是第 1 小的数字放在哪里，第 2 小的数字放在哪里，。。。，第 n 小的数字放在哪里。其中具体放什么数字，直接从这个他后面的数字中取就可以了。

AC代码

源代码

心路历程（WA，TLE，MLE……）

会算多的想法

for(int i=4;i<=N;i+=2){

    // 这个代码的问题在于不是所有的都能换
    // 只有处于末尾位置的节点才可以换
    FOR(k,1,N){
        if(i-2-k<0) break;
        dp[i]+=dp[i-2]*(i-2-k)*2;
        dp[i]+=dp[i-2];
        dp[i]%=mod;
    }

    // 分母是 （i-1）！
    ans[i]=dp[i]*inv[i-1];
    ans[i]%=mod;
}

但是我认为总体大思路是没有问题的，其实难点就在于如何知道可以更换的末尾节点有多少个。