WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #175 Div2 D "Permutation Sum"

問題

http://www.codeforces.com/problemset/problem/285/D

Permutation pとは、Nを超えるような数値のない
互いに異なるN個の正の整数の集まりである。

N=5であれば
(1,2,3,4,5)
(4,3,5,1,2)
(2,3,1,5,4)など

長さがNのPermutation同士を足し算するオペレーションを導入する事にした。
2つのPermutationがa(a1,a2,a3...aN) b(b1,b2,n3...bN)とし、
足し算後のPermutationがc(c1,c2,c3...cN)とすると、
ci = ( (ai - 1) + (bi - 1) ) mod N + 1となる。

残念ながら、a,bの内容によっては、
cがPermutationでなくなってしまう事が明らかである。

そこで、cがPermutationであるようなa,bのペアが何パターンあるのかを知りたい。
数が膨大になる恐れがあるので、1000000009でmodした値を返せ。

制約

1 <= N <= 16

考えた事

例えばN=5の場合
縦の見出しがaの値 横の見出しがbの値。内容をa+bとすると

1 2 3 4 5
1 1 2 3 4 5
2 2 3 4 5 1
3 3 4 5 1 2
4 4 5 1 2 3
5 5 1 2 3 4

こんな感じで縦横重複せずにcの1,2,3,4,5を選べるが、

N=4だと

1 2 3 4
1 1 2 3 4
2 2 3 4 1
3 3 4 1 2
4 4 1 2 3

どう頑張っても縦横重複せずに1,2,3,4を選べない・・

だからN % 2 == 0の時はきっと答えも0なんだな。

じゃあどうやって効率よく数え上げればいいんだろうか?
・・・分からない・・・

brute force

a を { 1, 2, 3... N-1, N} に固定して、
cがPermutationになるようにbを総当りで選んでいく。
計算量はO(N!)。最大では、16はやらなくていいから15!で一兆ぐらい。

出てきた結果はaを固定しているので、その結果にN!を掛ける。
そうすると答えがでる。

計算量をO(1)へ

でてきた答えをソースコード上に埋め込む☆

DP?

タグでDPがついてる。
どうも上記以外の方法もあるようだ。

ソースコード

const int MOD = 1000000007;
int N;
bool use_b[17];
bool use_c[17];

int dfs(int a){

    if( a > N ){
        return 1;
    }

    int res = 0;
    for( int b = 1; b <= N; b++ ){
        if( use_b[b] ) continue;
        int c = ((a - 1) + (b - 1)) % N + 1;
        if( use_c[c] ) continue;
        use_b[b] = use_c[c] = true;
        res += dfs( a+1 );
        res %= MOD;
        use_b[b] = use_c[c] = false;
    }
    return res;
}

void printAnswer(){
    ofstream out( "out.txt" );
    for( int n = 0; n <= 16; n++ ){
        long long res = 0;
        if( n % 2 != 0 ){
            N = n;
            res = dfs(1);
            for( int i = n; i >= 1; i-- ){
                res *= i;
                res %= MOD;
            }
        }
        out << res << ", ";
    }
}

int main() {
//    printAnswer();
    int ans[] = {0, 1, 0, 18, 0, 1800, 0, 670320, 0, 734832000, 0, 890786230, 0, 695720788, 0, 150347555, 0, };
    int n;
    cin >> n;
    cout << ans[n] << endl;
}