bzoj4563 [Haoi2016]放棋子_有一个n*n的矩阵,和n个棋子

Description

给你一个N*N的矩阵，每行有一个障碍，数据保证任意两个障碍不在同一行，任意两个障碍不在同一列，要求你在
这个矩阵上放N枚棋子（障碍的位置不能放棋子），要求你放N个棋子也满足每行只有一枚棋子，每列只有一枚棋子
的限制，求有多少种方案。

第一行一个N，接下来一个N*N的矩阵。N<=200,0表示没有障碍，1表示有障碍，输入格式参考样例

Solution

首先可以想到行与行之间、列与列之间可以交换而不改变答案。把障碍移到对角线上后可以发现，一个合法的答案当且仅当第i行的棋子不在第i列，且每一行都有棋子。这是一个错排的模型。没有模数上高精度

Code

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define drp(i,st,ed) for (int i=st;i>=ed;--i)
#define fill(x,t) memset(x,t,sizeof(x))

const int MOD=1000;
const int N=505;
const int L=505;

struct num {
    int s[L], len;
    inline bool operator ==(num b) {
        num a = *this;
        if (a.len != b.len) {
            return 0;
        }else {
            drp(i, a.len, 1) {
                if (a.s[i] != b.s[i]) {
                    return 0;
                }
            }
            return 1;
        }
    }
    inline bool operator <(num b) {
        num a = *this;
        if (a.len < b.len) {
            return 1;
        }else if (a.len > b.len) {
            return 0;
        }else {
            drp(i, a.len, 1) {
                if (a.s[i] < b.s[i]) {
                    return 1;
                }else if (a.s[i] > b.s[i]) {
                    return 0;
                }
            }
            return 0;
        }
    }
    inline bool operator <=(num b) {
        num a = *this;
        if (a < b || a == b) {
            return 1;
        }else {
            return 0;
        }
    }
    inline bool operator >(num b) {
        num a = *this;
        if (a.len > b.len) {
            return 1;
        }else if (a.len < b.len) {
            return 0;
        }else {
            drp(i, a.len, 1) {
                if (a.s[i] > b.s[i]) {
                    return 1;
                }else if (a.s[i] < b.s[i]) {
                    return 0;
                }
            }
            return 0;
        }
    }
    inline bool operator >=(num b) {
        num a = *this;
        if (a > b || a == b) {
            return 1;
        }else {
            return 0;
        }
    }
    inline num operator +(num b) {
        num a = *this, c = (num) { {0}, std:: max(a.len, b.len)};
        int v = 0;
        rep(i, 1, c.len) {
            c.s[i] = (a.s[i] + b.s[i] + v) % MOD;
            v = (a.s[i] + b.s[i] + v) / MOD;
        }
        if (v) {
            c.len += 1;
            c.s[c.len] = v;
        }
        return c;
    }
    inline num operator -(num b) {
        num a = *this, c = (num) { {0}, std:: max(a.len, b.len)};
        rep(i, 1, c.len) {
            c.s[i] = a.s[i] - b.s[i];
            if (c.s[i] < 0) {
                c.s[i] += MOD;
                a.s[i + 1] -= 1;
            }
        }
        while (!c.s[c.len] && c.len > 1) {
            c.len -= 1;
        }
        return c;
    }
    inline num operator *(num b) {
        num a = *this, c = (num) { {0}, a.len + b.len};
        rep(i, 1, a.len) {
            rep(j, 1, b.len) {
                c.s[i + j - 1] += a.s[i] * b.s[j];
            }
        }
        rep(i, 1, a.len + b.len) {
            c.s[i + 1] += c.s[i] / MOD;
            c.s[i] %= MOD;
        }
        while (!c.s[c.len] && c.len > 1) {
            c.len -= 1;
        }
        return c;
    }
    inline num operator /(int b) {
        num a = *this, c = (num) { {0}, a.len};
        int v = 0;
        drp(i, len, 1) {
            int t = v * MOD + a.s[i];
            c.s[i] = t / b;
            v = t % b;
        }
        while (!c.s[c.len] && c.len > 1) {
            c.len -= 1;
        }
        return c;
    }
    inline void read() {
        fill(s, 0); len = 0;
        char st[L];
        scanf("%s", st);
        int v = 0, i;
        for (i = strlen(st) - 1; i >= 3; i -= 3) {
            rep(j, i - 2, i) {
                v = v * 10 + st[j] - '0';
            }
            s[++ len] = v;
            v = 0;
        }
        rep(j, 0, i) {
            v = v * 10 + st[j] - '0';
        }
        s[++ len] = v;
    }
    inline void read1(int x) {
        fill(s, 0);
        len = 0;
        do {s[++ len] = x % MOD;}while (x /= MOD);
    }
    inline void output() {
        num tmp = *this;
        int i = tmp.len;
        while (!tmp.s[i] && i > 1) {
            i -= 1;
        }
        printf("%d", tmp.s[i]);
        drp(j, i - 1, 1) {
            int v = tmp.s[j];
            int f[5] =  {0};
            rep(k, 1, 3) {
                f[k] = v % 10;
                v /= 10;
            }
            drp(k, 3, 1) {
                printf("%d", f[k]);
            }
        }
        printf("\n");
    }
} f[N];
num one;

int main(void)  {
    int n; scanf("%d",&n);
    rep(i,1,n) rep(j,1,n) scanf("%*d");
    f[2].len=1; f[2].s[1]=1;
    rep(i,3,n) {
        num tmp; tmp.read1(i-1);
        f[i]=f[i-1]+f[i-2];
        f[i]=f[i]*tmp;
    }
    f[n].output();
    return 0;
}
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189