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; }