atcoder_134F Permutation Oddness

题目:

  Let us define the oddness of a permutation of as .
  Find the number of permutations of of oddness , modulo .

思路:

  应该也算是线头dp的一种吧.....
  其实问题就是 个数字和 个位置的配对。为了方便起见如果数字在位置之前,那就用数字去配位置,如果是位置在前,那就用位置配数字(也就是说都用前面的去配对后面的)。如果把这些配对看作线,那么最后的答案就是总的线长。
  设 表示前 个数,当前价值为 (没有配对的线只拉到 ),还有 个东西没有配对( 个数字和 个位置)的方案数。那每次加入一个数字的时候就考虑这个数字的配对情况。
  如果这个数字和自己配对,那么转移就是:
  如果位置和数字中有一个和前面配对了:
  如果位置和数字都和前面配对了:
  如果位置和数字都没和前面配对:

代码:

#include <bits/stdc++.h>
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int MOD = 1e9 + 7, N = 55;

int dp[N][N * N][N];

int main() {
    // freopen("data.in", "r", stdin);
    int n, k;
    scanf("%d%d", &n, &k);
    dp[1][0][1] = 1; dp[1][0][0] = 1;
    rep(i, 1, n - 1) rep(j, 0, k) rep(x, 0, i) {
        (dp[i + 1][j + 2 * x][x] += dp[i][j][x]) %= MOD;
        (dp[i + 1][j + 2 * x][x + 1] += dp[i][j][x]) %= MOD;
        if(x > 0) {
            (dp[i + 1][j + 2 * x][x] += (ll) 2 * x * dp[i][j][x] % MOD) %= MOD;
            (dp[i + 1][j + 2 * x][x - 1] += (ll) x * x * dp[i][j][x] % MOD) %= MOD;
        }
    }
    printf("%d\n", dp[n][k][0]);
    return 0;
}