【UVa#11806】Cheerleaders

朱雀 2023-06-05 08:53 121阅读 0赞

# Description #

[UVa\#11806][UVa_11806]

在一张$n\\times m$的网格图中放k个人，要求第一行第一列最后一行最后一列都必须放人，每个人都必须放，同一位置只能有一个人

求方案数对1e6+7取模的结果

# Solution #

容斥原理+状压

由于非法的方案数十分好求，所以我们考虑用总数-非法方案数来求解答案

$$sum\_\{all\}=C\_\{n\\times m\}^\{k\}$$

一个方案非法方案，一定是第一行第一列最后一行最后一列的一个或几个有空位

我们将这四个状压一下，第0位表示第一行是否空缺，第1位表示最后一行，第2位表示第一列，第3位表示最后一列

根据容斥原理，非法方案数=空一个位置-空两个位置+空三个位置-空四个位置-……

如果空一个位置并且是行空缺，那么方案数就是$C\_\{(n-1)\\times m\}^\{k\}$

其他情况以此类推

用杨辉三角处理组合数然后直接容斥就好了

时间复杂度可以看成常数

# Code #

#include <bits/stdc++.h>
    namespace shl {
        typedef long long ll;
        int T, n, m, k;
        int C[510][510];
        const int mod = 1e6 + 7;
        int main() {
            for (register int i = 0; i <= 500; ++i) {
                C[i][0] = C[i][i] = 1;
                for (register int j = 1; j < i; ++j)
                    C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
            }
            scanf("%d", &T);
            for (register int QQQ = 1; QQQ <= T; ++QQQ) {
                scanf("%d%d%d", &n, &m, &k);
                ll ans = 0;
                for (register int s = 0; s < 16; ++s) {
                    int x = n, y = m, num = 0;
                    if (s & 1) x--, num++;
                    if (s & 2) x--, num++;
                    if (s & 4) y--, num++;
                    if (s & 8) y--, num++;
                    if (num & 1) ans = (ans - C[x * y][k] + mod) % mod;
                    else ans = (ans + C[x * y][k]) % mod;
                }
                printf("Case %d: %lld\n", QQQ, ans % mod);
            }
            return 0;
        }
    };
    int main() {
        shl :: main();
        return 0;
    }

转载于:https://www.cnblogs.com/shl-blog/p/11383144.html

[UVa_11806]: https://www.luogu.org/problem/UVA11806