这部分内容主要讲述动态规划的综合
包括大整数与计数问题，计数dp，数位统计dp

计数dp补充

大整数类与计数dp

这里特别注意大整数类的封装

POJ1737
POJ1737

basebase 取 1e41e4，很常见

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

// == Big Integer class ==
const int SZ = 200 + 5;

inline void write(ll x) {
    if(x < 0) {
        putchar('-');
        x = -x;
    }
    if(x < 10) {
        putchar(x + '0');
        return;
    }

    write(x / 10);
    putchar((x % 10) + '0');
}

const int base = 1e4;
class Int {
public:
    int a[SZ], len;
    Int() {
        Set(a, 0);
        len = 0;
    }
    Int(int x) {
        Set(a, 0);
        len = 0;

        while (x) {
            a[++len] = x % base;
            x /= base;
        }
    }
    inline void print() {
        write(a[len]);
        for(int i = len - 1; i; i--) {
            if(a[i] < 1000) putchar('0');
            if(a[i] < 100) putchar('0');
            if(a[i] < 10) putchar('0');
            write(a[i]);
        }
    }
};

inline Int operator+ (Int a, Int b) {
    Int ans;
    ans = a;

    ans.len = max(a.len, b.len);
    _rep(i, 1, ans.len) {
        ans.a[i] += b.a[i];
        ans.a[i + 1] += ans.a[i] / base;
        ans.a[i] %= base;
    }
    while (ans.a[ans.len + 1]) ans.len++;
    return ans;
}

inline Int operator / (Int a, int b) {
    Int ans;
    assert(ans.len == 0);

    int num = 0;
    for(int i = a.len; i; i--) {
        num = num * base + a.a[i];
        ans.a[i] = num / b;
        num %= b;

        if(ans.len == 0 && ans.a[i]) ans.len = i;
    }
    return ans;
}

inline Int operator* (Int a, int b) {
    Int ans = a;
    _rep(i, 1, ans.len) ans.a[i] *= b;
    _rep(i, 1, ans.len) {
        ans.a[i + 1] += ans.a[i] / base;
        ans.a[i] %= base;
    }

    while (ans.a[ans.len + 1]) {
        ans.len++;
        ans.a[ans.len + 1] += ans.a[ans.len] / base;
        ans.a[ans.len] %= base;
    }
    return ans;
}

inline Int operator* (Int a, Int b) {
    Int ans;
    assert(ans.a[1] == 0);

    ans.len = a.len + b.len;
    _rep(i, 1, a.len) _rep(j, 1, b.len) {
        ans.a[i+j-1] += a.a[i] * b.a[j];
        ans.a[i+j] += ans.a[i+j-1] / base;
        ans.a[i+j-1] %= base;
    }
    while (ans.a[ans.len] == 0) ans.len--;
    return ans;
}

inline Int operator- (Int a, Int b) {
    Int ans = a;
    _rep(i, 1, b.len) {
        ans.a[i] -= b.a[i];
        if(ans.a[i] < 0) {
            ans.a[i + 1]--;
            ans.a[i] += base;
        }
    }

    while (ans.a[ans.len] == 0) ans.len--;
    return ans;
}

// == Big Integer class finished ==

// == init ==
const int Max = 1500;
Int bin[Max * 2];

void initbin() {
    bin[0] = Int(1);
    _rep(i, 1, Max) bin[i] = bin[i - 1] * 2;
}

const int maxn = 50;
Int c[maxn + 5][maxn + 5];

void initc() {
    c[0][0] = Int(1);
    _rep(i, 1, maxn) {
        c[i][0] = Int(1);
        _rep(j, 1, i) c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
}
// == init finished ==

// == initbin() initc(), then dp() ==
Int f[maxn + 5];

void dp() {
    f[1] = Int(1);
    _rep(i, 2, maxn) {
        f[i] = bin[i*(i-1) / 2];
        _for(j, 1, i) {
            f[i] = f[i] - (f[j] * c[i-1][j-1] * bin[(i-j)*(i-j-1) / 2]);
        }
    }
}
// == dp finished ==

int main() {
    freopen("input.txt", "r", stdin);

    initbin();
    initc();
    dp();

    int n;
    while (cin >> n && n) f[n].print(), puts("");
}

计数dp综合

他们中的多少个
这是无向连通图的计数问题，注意节点有标号。

具体的思路如下
Acwing308-01
Acwing308-02
Acwing308-03

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
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339

// == Big Integer class ==
const int SZ = 200 + 5;

inline void write(ll x) {
    if(x < 0) {
        putchar('-');
        x = -x;
    }
    if(x < 10) {
        putchar(x + '0');
        return;
    }

    write(x / 10);
    putchar((x % 10) + '0');
}

const int base = 1e4;
class Int {
public:
    int a[SZ], len;
    Int() {
        Set(a, 0);
        len = 0;
    }
    Int(int x) {
        Set(a, 0);
        len = 0;

        while (x) {
            a[++len] = x % base;
            x /= base;
        }
    }
    inline void print() {
        write(a[len]);
        for(int i = len - 1; i; i--) {
            if(a[i] < 1000) putchar('0');
            if(a[i] < 100) putchar('0');
            if(a[i] < 10) putchar('0');
            write(a[i]);
        }
    }
};

inline Int operator+ (Int a, Int b) {
    Int ans;
    ans = a;

    ans.len = max(a.len, b.len);
    _rep(i, 1, ans.len) {
        ans.a[i] += b.a[i];
        ans.a[i + 1] += ans.a[i] / base;
        ans.a[i] %= base;
    }
    while (ans.a[ans.len + 1]) ans.len++;
    return ans;
}

inline Int operator / (Int a, int b) {
    Int ans;
    assert(ans.len == 0);

    int num = 0;
    for(int i = a.len; i; i--) {
        num = num * base + a.a[i];
        ans.a[i] = num / b;
        num %= b;

        if(ans.len == 0 && ans.a[i]) ans.len = i;
    }
    return ans;
}

inline ll operator % (Int a, int b) {
    ll num = 0;
    for(int i = a.len; i; i--) {
        num = ((num * base) % b + a.a[i]) % b;
    }
    return num;
}

inline Int operator* (Int a, int b) {
    Int ans = a;
    _rep(i, 1, ans.len) ans.a[i] *= b;
    _rep(i, 1, ans.len) {
        ans.a[i + 1] += ans.a[i] / base;
        ans.a[i] %= base;
    }

    while (ans.a[ans.len + 1]) {
        ans.len++;
        ans.a[ans.len + 1] += ans.a[ans.len] / base;
        ans.a[ans.len] %= base;
    }
    return ans;
}

inline Int operator* (Int a, Int b) {
    Int ans;
    assert(ans.a[1] == 0);

    ans.len = a.len + b.len;
    _rep(i, 1, a.len) _rep(j, 1, b.len) {
            ans.a[i+j-1] += a.a[i] * b.a[j];
            ans.a[i+j] += ans.a[i+j-1] / base;
            ans.a[i+j-1] %= base;
        }
    while (ans.a[ans.len] == 0) ans.len--;
    return ans;
}

inline Int operator- (Int a, Int b) {
    Int ans = a;
    _rep(i, 1, b.len) {
        ans.a[i] -= b.a[i];
        if(ans.a[i] < 0) {
            ans.a[i + 1]--;
            ans.a[i] += base;
        }
    }

    while (ans.a[ans.len] == 0) ans.len--;
    return ans;
}

const int maxn = 50 + 2;


Int _c[maxn][maxn];
const int mod = 1e9 + 7;

ll H[maxn + 1];

// == table() and list H[] ==
const int Max = 1500;
Int bin[Max*2];

void initbin() {
    bin[0] = Int(1);
    _rep(i, 1, Max) bin[i] = bin[i - 1] * 2;
}

Int tb[maxn + 5];

void getH() {
    initbin();

    tb[1] = Int(1);
    _rep(i, 2, maxn) {
        tb[i] = bin[i*(i-1) / 2];
        _for(j, 1, i) {
            tb[i] = tb[i] - (tb[j] * _c[i-1][j-1] * bin[(i-j)*(i-j-1) / 2]);
        }
    }
}

void table() {
    getH();
    _rep(i, 1, maxn) H[i] = tb[i] % mod;
}
// == table() finsihed ==

const int maxm = 1250;

// == calculate C() ==


void initC() {
    _c[0][0] = Int(1);
    _rep(i, 1, maxn) {
        _c[i][0] = Int(1);
        _rep(j, 1, i) _c[i][j] = _c[i-1][j-1] + _c[i-1][j];
    }
}

inline ll C(int n, int m) {
    return _c[n][m] % mod;
}

ll power(ll a, int b) {
    ll ans = 1;
    for(; b; b >>= 1) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
    }
    return ans;
}
// == C() finsihed, usage initC() and C(x, y) ==

// == first part, init f(i,j) ==
ll f[maxn][maxm];
ll sum[maxn][maxm];

void initf() {
    Set(f, -1);
    Set(sum, 0);
    f[0][0] = 0;
    f[1][0] = 1;
    f[1][1] = 0;
    f[2][0] = 0;
    f[2][1] = 1;
    f[2][2] = 0;

    _for(i, 3, maxn) f[i][0] = 0;
}
// == f(i, j) finished ==

// == second part, init g(i,j,k) ==
ll g[maxn][maxn][maxm];

void initg() {
    Set(g, -1);

    _for(i, 0, maxn) _for(j, 0, maxm) g[0][i][j] = 0;

    _for(k, 0, maxm) g[1][0][k] = 0;

    g[1][1][0] = 1;
    _for(k, 1, maxm) g[1][1][k] = 0;

    //_for(i, 0, maxn) g[i][1][0] = 1;
    g[2][1][1] = 2;
    g[2][1][0] = 0;
    //g[2][0][0] = 1;
    //g[2][0][1] = 0;
}
// == g(i,j,k) finished ==

// == function G(i,j,k) ==
ll G(int i, int j, int k) {
    if(g[i][j][k] >= 0) return g[i][j][k];

    ll res = 0;
    _rep(p, 1, i) _rep(q, 0, k) {
            //debug(p);
            //debug(q);
            //debug(f[p][q]);
            if(q >= p) continue;
            assert(f[p][q] >= 0);
            //debug(f[p][q]);

            ll S = G(i-p, j-1, k-q);
            assert(S >= 0);

            res += (f[p][q] * C(i-1, p-1) % mod * p % mod * S) % mod;
            res %= mod;
        }
    return g[i][j][k] = res;
}
// == G(i,j,k) finished ==

// == function cal(i, j, k) ==
ll cal(int i, int j, int k) {
    assert(f[k][0] >= 0);
    //debug(k), debug(f[k][0]);
    //puts("");

    //printf("i = %d, k = %d, %lld\n",i, k, C(i-1, k-1));

    ll S1 = f[k][0] * C(i-1, k-1) % mod;
    //debug(C(i-1, k-1));

    ll S2 = 0;
    _rep(x, 1, min(i-k, j)) {
        S2 = (S2 + (G(i-k, x, j-x) * power(k, x)) % mod) % mod;
    }
    // if(i == 3) debug(S2);
    return S1 * S2 % mod;
}
// == cal(i, j, k) finsihed ==

// == then solve ==
const int N = 50;
const int M = 1250;

void solve() {
    _rep(i, 3, N) {
        f[i][0] = H[i];
        _for(j, 1, i) {
            //assert(f[i][j] <= 0);

            f[i][j] = 0;
            _rep(k, 1, i - 1) {
                f[i][j] = (f[i][j] + cal(i, j, k)) % mod;
            }
            f[i][0] = (f[i][0] - f[i][j] + mod) % mod;
        }

    }
}
// == solve finished ==

int main() {
    //freopen("input.txt", "r", stdin);
    freopen("sol.out", "w", stdout);
    initC();

    table();

    initf();
    initg();
    solve();

    //debug(H[52]);
    //debug(H[3]);
    //debug(f[3][1]);
    //debug(f[3][2]);


    //debug(g[2][1][1]);
    //debug(g[2][1][0]);
    _rep(i, 1, N) {
        cout << i << ":  ";
        printf("  ||  H[i]=%lld  ||      ", H[i]);
        _rep(j, 0, 10) printf("%lld    ", f[i][j]);
        puts("");
    }


    cout << "\n===================\n" << endl;

    // == get another table ==
    _rep(i, 0, N) {
        if(i == 0) {
            _rep(j, 0, N) printf("0, ");
            printf("\n");
            continue;
        }
        _rep(j, 0, N) {
            if(f[i][j] < 0) printf("0, ");
            else printf("%lld, ", f[i][j]);
        }
        printf("\n");
    }
    // == table end ==
}

康托尔思想

POJ1037

POJ1037

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

const int maxn = 20 + 5;
const int N = 20;
int n;
ll m, f[maxn][maxn][2];

void prework() {
    Set(f, 0);
    f[1][1][1] = f[1][1][0] = 1;

    _rep(i, 2, N) _rep(j, 1, i) {
        _rep(p, j, i - 1) f[i][j][0] += f[i - 1][p][1];
        _rep(p, 1, j - 1) f[i][j][1] += f[i - 1][p][0];
    }
}


bool used[maxn];

void solve() {
    Set(used, 0);

    int last, k;
    _rep(j, 1, n) {
        if(f[n][j][1] >= m) {
            last = j;
            k = 1;
            break;
        }
        else m -= f[n][j][1];

        if(f[n][j][0] >= m) {
            last = j;
            k = 0;
            break;
        }
        else m -= f[n][j][0];
    }

    //debug(last);
    //debug(k);

    used[last] = 1;
    printf("%d", last);

    _rep(i, 2, n) {
        int j = 0;
        k ^= 1;

        // assign new len to last
        // find out a new len, then get last len
        _rep(len, 1, n) {
            if(used[len]) continue;
            j++;

            if((k == 0 && len < last) || (k == 1 && len > last)) {
                // assign a new value to last
                if(f[n - i + 1][j][k] >= m) {
                    last = len;
                    break;
                }
                else m -= f[n - i + 1][j][k];
            }
        }

        used[last] = 1;
        printf(" %d", last);
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    prework();

    int kase;
    cin >> kase;
    while (kase--) {
        cin >> n >> m;
        solve();
        cout << endl;
    }
}