跃迁引擎启动

HDu5555 Immortality of Frog 题解

发表于 更新于 分类于 阅读次数：

妙啊！

题意

给了一个 $n \times n$ 的网格，第一行排着 $n$ 个青蛙，青蛙同时往上跳。

每行有一个线段，一个线段当且仅当完全覆盖一行时是好的，一个青蛙上跳的过程不能经过超过 $10$ 个坏的线段。

每个线段的每个位置等概率出现一个糖果，求每个青蛙恰好拿到一个糖并且能够走完全程的概率。

其中 $1 \le n \le 1000$。

分析

如果一个青蛙上面有超过 $10$ 个坏线段，显然概率为 $0$。

显然，每一行和每一列恰好有一个糖。

我们从左往右按列 dp，记 $dp[i][s]$ 表示当前到达第 $i$ 列，状态为 $s$ 的概率。

状态代表这列的坏线段依次选与不选，转移时需要将当前列的状态改变成下一列状态，并且需要判断掉一行终止且未选的无效情况。

转移时，将当前状态加到改变后的状态，并枚举下一列的一个位置进行选择，条件是不在当前列上或者当前列未选。

最后，计算出了所有坏线段的情况，乘上好线段的阶乘，即坏线段确定后，好线段可以任意取。

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#ifdef XLor
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << std::endl; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
  #define dbg(...)
#endif
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 105225319;
const int inf = 1 << 30;
const int maxn = 2000 + 5;

void add(int& x, int y) {
    x += y; if (x >= mod) x -= mod;
}

int n, l[maxn], r[maxn], dp[maxn][maxn];
vector<int> bag[maxn];

int main() {
    int T, kase = 0; scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) bag[i].clear();
        for (int i = 1; i <= n; i++) scanf("%d", l + i);
        for (int i = 1; i <= n; i++) scanf("%d", r + i);
        int good = n;
        for (int i = 1; i <= n; i++) {
            if (r[i] - l[i] + 1 == n) continue;
            good--;
            for (int j = l[i]; j <= r[i]; j++) {
                bag[j].push_back(i);
            }
        }
        printf("Case #%d: ", ++kase);
        int flag = 0;
        for (int i = 1; i <= n; i++) if ((int)bag[i].size() > 10) flag = 1;
        if (flag) {
            puts("0"); continue;
        }
        ms(dp, 0); dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            int ss = 1 << (int)bag[i].size();
            vector<int> f(15, -1), g(15, -1);
            for (int j = 0; j < (int)bag[i].size(); j++) {
                for (int k = 0; k < (int)bag[i + 1].size(); k++) {
                    if (bag[i][j] == bag[i + 1][k]) {
                        f[j] = k;
                    }
                }
            }
            for (int j = 0; j < (int)bag[i + 1].size(); j++) {
                for (int k = 0; k < (int)bag[i].size(); k++) {
                    if (bag[i + 1][j] == bag[i][k]) {
                        g[j] = k;
                    }
                }
            }
            auto get = [&](int x, int s) -> int {
                int ans = 0;
                for (int i = 0; i < (int)bag[x].size(); i++) {
                    if (f[i] == -1) {
                        if (s & (1 << i)) ;
                        else return -1;
                    } else if (s & (1 << i)) {
                        ans |= 1 << f[i];
                    }
                }
                return ans;
            };
            for (int s = 0; s < ss; s++) {
                int nx = get(i, s);
                if (nx == -1) continue;
                if (good) add(dp[i + 1][nx], dp[i][s]);
                for (int j = 0; j < (int)bag[i + 1].size(); j++) {
                    if (g[j] == -1) add(dp[i + 1][nx | (1 << j)], dp[i][s]);
                    else if ((s >> g[j] & 1) == 0) add(dp[i + 1][nx | (1 << j)], dp[i][s]);
                }
            }
        }
        int ans = dp[n][(1 << (int)bag[n].size()) - 1];
        for (int i = 1; i <= good; i++) ans = 1ll * ans * i % mod;
        printf("%d\n", ans);
    }
    return 0;
}