解題區/解題區 - 其他題目

[Tmt514] Beverage Cup 2 G - Strange Permutations

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

排列 1 到 n 的整數，使得相鄰兩數互質，部分位置一定要填入某些數字，請問剩餘數字的填法方案數為何？

Sample Input

1
2
3
1
8
1 2 0 0 0 0 7 8

Sample Output

1
2

Solution

bitmask 下去 dp[N][1<<N][N]，dp[i][j][k] 表示前 i 個位置，已經使用的數字狀態 j，最後一個數字 k。不曉得需不需要滾動，記憶體用量驚人。萬萬沒想到，撰寫過程中坑了一個建表的 gcd[20][20]，當 n = 20 時，直接 index out of bound，先撇開這個蠢錯。滾動數組下去玩，真是誘人的時間限制，再次得到 9.990s TLE 的事蹟 ！仔細想想，運算過程中只出現加法，將 mod 運算替換成條件判斷 + 減法，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MOD = 1000000007;
const int MAXN = 20;
int dp[2][1<<MAXN][MAXN], used[2][1<<MAXN][MAXN], ucases = 0;
int g[MAXN+20][MAXN+20];
int vaild(int i, int a, int b) { // a contract b
    if (i == 0)	return 1;
    return g[a+1][b+1];
}
int main() {
    for (int i = 1; i <= MAXN; i++) {
        for (int j = 1; j <= MAXN; j++)
            g[i][j] = __gcd(i, j) == 1;
    }
    int testcase, n;
    int A[MAXN];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        int cant = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &A[i]);
            if (A[i])
            	cant |= 1<<(A[i]-1);
        }
        
        int flag = 0;
        int mask = (1<<n)-1;
        int ret = 0;
//        memset(dp, 0, sizeof(dp));
        ucases++;
        used[flag][0][0] = ucases;
        dp[flag][0][0] = 1;
        for (int i = 0; i < n; i++) {
            int p = flag, q = !flag;
            flag = 1 - flag;
            ucases++;
//            for (int j = mask; j >= 0; j--)
//            	for (int k = 0; k < n; k++)
//            		dp[q][j][k] = 0;
            for (int j = (1<<n)-1; j >= 0; j--) {
            	for (int k = 0; k < n; k++) {
            		if (used[p][j][k] != ucases-1)
            			continue;
            		int ways = dp[p][j][k];
            		if (ways == 0)
            			continue;
            		if (A[i] == 0) {
            			for (int p = 0; p < n; p++) {
            				if ((j>>p)&1)
            					continue;
            				if (!vaild(i, k, p))
            					continue;
            				if (used[q][j|(1<<p)][p] != ucases)
            					used[q][j|(1<<p)][p] = ucases, dp[q][j|(1<<p)][p] = 0;
            				dp[q][j|(1<<p)][p] += ways;
            				if (dp[q][j|(1<<p)][p] >= MOD)
            					dp[q][j|(1<<p)][p] -= MOD;
            			}
            		} else {
            			for (int p = A[i]-1; p <= A[i]-1; p++) {
            				if ((j>>p)&1)
            					continue;
            				if (!vaild(i, k, p))
            					continue;
            				if (used[q][j|(1<<p)][p] != ucases)
            					used[q][j|(1<<p)][p] = ucases, dp[q][j|(1<<p)][p] = 0;
            				dp[q][j|(1<<p)][p] += ways;
                            if (dp[q][j|(1<<p)][p] >= MOD)
            					dp[q][j|(1<<p)][p] -= MOD;
            			}
            		}
            	}
            }
        }
        
        for (int i = 0; i < n; i++) {
        	if (used[flag][(1<<n)-1][i] != ucases)
        		continue;
        	ret += dp[flag][(1<<n)-1][i];
        	ret %= MOD;
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
10
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
4
0 2 4 0
8
1 3 5 0 0 0 0 0
8
1 2 0 0 0 0 7 8
8
1 0 5 8 0 0 0 0
8
0 2 0 7 0 0 0 8
8
0 2 0 0 0 0 0 8
8
0 2 0 0 0 0 0 0
8
0 0 0 0 0 0 0 0
7
0 0 0 0 0 0 0
1
0
*/