P1350 车的放置

P1350 车的放置 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

非递推做法，对于这个题，这个图形之间统计很麻烦，由此我们可以把它分成两个矩形。如直接沿 \(b\) 边切割。但这样我们发现还是不好统计，因为左边矩形会受到右边不一定的限制，于是沿着 \(b,c\) 边再次切割，分成三个矩形，从上到下矩形标号为 \(1,2,3\)。可以发现 \(1,3\) 没有任何关系，而 \(1,3\) 同时影响 \(2\)。

先看看没有影响的 \(1,3\)，对于一个矩形，放置方案可以为先选 \(k\) 个横坐标，再选 \(k\) 个纵坐标，最后排列这 \(k\) 对坐标，具体为何自己试试。

接下来看看 \(2\)，假设 \(1,3\) 分别放了 \(k_1, k_2\) 个车，那么 \(2\) 将有分别有 \(k_1,k_2\) 行横纵坐标不能使用。去掉这些不能用的行就变成了一个 \(a-k_1,b-k_2\) 的矩形，而这个新矩形也就和 \(1,3\) 没有影响了，按他们的方式求出来。

最后把 \(1,2,3\) 的方案乘起来就是当前状态（每个矩形放几个车）的方案数。把所有方案加起来就是最终答案。

注意要预处理逆元，阶乘，否则时间不够。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 1010, mod = 1e5 + 3;

int n, m, k;
int a, b, c, d;
int f[N], in_f[N];

int qmi(int a, int k, int p)
{
    int res = 1;
    
    while (k)
    {
        if (k & 1) res = (1ll * res * a) % p;
        k >>= 1;
        a = 1ll * a * a % p;
    }
    
    return res;
}

int get(int x) // 获取逆元，这里利用费马小定理
{
    return qmi(x, mod - 2, mod);
}

int get2(int a, int b) // 组合数
{
    return 1ll * f[a] * in_f[a - b] % mod * in_f[b] % mod;
}

int get3(int a, int b, int k) // 为了方便
{
    return 1ll * f[k] * get2(a, k) % mod * get2(b, k) % mod;
}

int main()
{
    cin >> a >> b >> c >> d >> k;
    
    f[0] = 1;
    in_f[0] = get(f[0]);
    for (int i = 1; i <= 1000; i ++ )
    {
        f[i] = 1ll * f[i - 1] * i % mod;
        in_f[i] = get(f[i]);
        // cout << 1ll * in_f[i] << ' ' << get(f[i]) % mod << endl;
    }
    
    int t3 = 0;
    
    for (int i = 0; i <= k; i ++ )
    {
        if (a < i || b < i) continue;
        for (int j = 0; j <= k - i; j ++ )
        {
            if (c < j || d < j) continue;
            int x = a - i, y = d - j, z = k - i - j;
            if (x < 0 || y < 0 || z > x || z > y) continue;
        
            t3 = (1ll * t3 + 1ll * get3(x, y, z) * get3(a, b, i)  % mod * get3(c, d, j) % mod) % mod;
            // printf("%d %d %d\n", i, j, t3);
        }
    }
    cout << t3;
    
    return 0;
}