清北学堂模拟赛d3t3 c

分析：一开始拿到这道题真的是无从下手，暴力都很难打出来.但是基本的方向还是要有的，题目问的是方案数，dp不行就考虑数学方法.接下来比较难想.其实对于每一行或者每一列，我们任意打乱顺序其实对答案是没有影响的.那么我们按照高度从大到小对行和列进行排序，单独考虑所有高度相等的行和列，组成了一个L形，如果我们把所有的L形的方案数求出来最后乘起来就是答案了，关键就是怎么求它的方案数.

要求L形中满足每行每列最大高度不超过H的方案数很难求，因为不好保证最大高度，正难则反，先求出不满足的，但是不满足的也比较难求，我们就先求出有一行不满足的，一列不满足的，然后求出两行不满足的，两列不满足的，这其实就是一个容斥原理，处于限制的行和列由于取的数小于H,所以每一位能取H个数，而没有限制的可以取0~H,共H+1个数，那么方案数就出来了:H^(限制的面积) + (H+1)^（没有限制的面积）* (-1)^|S|,就像下面一个图：

蓝色部分没有限制，黑色部分有限制，黑色部分和蓝色部分组成了一个L形.

正难则反，如果求满足某某条件很难，就求出不满足某某条件的，如果还是很难，就分解一下，利用容斥原理来做.

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int mod = 1e9 + ;

long long n, m,a[],b[],x,y;

long long ans = ,c[][];

void init()

{

    c[][] = ;

    for (int i = ; i <= ; i++)

    {

        c[i][] = ;

        for (int j = ; j <= ; j++)

            c[i][j] = (c[i - ][j] + c[i - ][j - ]) % mod;

    }

}

long long qpow(long long a, long long b)

{

    long long res = ;

    while (b)

    {

        if (b & )

            res = (res * a) % mod;

        b >>= ;

        a = (a * a) % mod;

    }

    return res;

}

long long cal(long long x, long long y, long long nx, long long ny, int p)

{

    long long res = ;

    for (long long i = ; i <= nx; i++)

        for (long long j = ; j <= ny; j++)

        {

        long long temp = qpow(p, x * y - (x - i) * (y - j)) * qpow(p + , (x - i) * (y - j) - (x - nx) * (y - ny)) % mod * c[nx][i] % mod * c[ny][j] % mod;

        if ((i + j) & )

            res = ((res - temp) % mod + mod) % mod;

        else

        {

            res += temp;

            while (res >= mod)

                res -= mod;

        }

        }

    return res;

}

int main()

{

    scanf("%lld%lld", &n, &m);

    for (int i = ; i <= n; i++)

    {

        long long x;

        scanf("%lld", &x);

        a[x]++;

    }

    for (int i = ; i <= m; i++)

    {

        long long x;

        scanf("%lld", &x);

        b[x]++;

    }

    init();

    for (int i = ; i >= ; i--)

        if (a[i] || b[i])

        {

        x += a[i];

        y += b[i];

        ans = ans * cal(x, y, a[i], b[i],i) % mod;

        }

    printf("%lld\n", ans);

    return ;

}

巴特西

清北学堂模拟赛d3t3 c

最新文章

热门文章