2021年4月29日题目 [HAOI2016]放棋子

题号 NC19999
名称 [HAOI2016]放棋子
来源 [HAOI2016]

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

给你一个N*N的矩阵，每行有一个障碍，数据保证任意两个障碍不在同一行，任意两个障碍不在同一列，要求你在这个矩阵上放N枚棋子（障碍的位置不能放棋子），要求你放N个棋子也满足每行只有一枚棋子，每列只有一枚棋子的限制，求有多少种方案。

样例

示例1
输入
2
0 1
1 0
输出
1

算法1

(容斥原理 + 组合计数 + 高精度)

先考虑没有障碍物的情况，总方案数为

如果加入障碍物，那么我们就要计算这的方案数中有多少方案是不存在任何一个棋子是摆在障碍物上的
本题有一个很强的性质:数据保证任意两个障碍不在同一行，任意两个障碍不在同一列

所以我们可以根据容斥原理来求：

答案 = - 至少有一个棋子放在了障碍物上 + 至少有两个棋子放在了障碍物上 - ...(奇减偶加)

假设有个障碍物

至少有个棋子放在了障碍物上的方案数

解释：由于求的是"至少"我们选出i个棋子放在障碍物上:()，其余棋子可随意放（可以放在障碍物上也可以放在空格上）:

题目没有要求输出多少的答案，所以要用高精度

时间复杂度

参考文献

C++ 代码

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

using namespace std;
typedef long long LL;
const int N = 210;
vector<int> fac[N];
vector<int> C[N][N];
int n;

vector<int> operator+(vector<int> &a,vector<int> &b)
{
    if(a.size() < b.size()) return (b + a);
    vector<int> c;
    int t = 0;
    for(int i = 0;i < a.size();i ++)
    {
        if(i < b.size()) t += b[i];
        t += a[i];
        c.push_back(t % 10);
        t /= 10;
    }
    if(t) c.push_back(t);
    return c;
}

vector<int> operator-(vector<int> &a,vector<int> &b)
{
    vector<int> c;
    int t = 0;
    for(int i = 0;i < a.size();i ++)
    {
        t = a[i] - t;
        if(i < b.size()) t -= b[i];
        c.push_back((t + 10) % 10);
        if(t < 0) t = 1;
        else t = 0;
    }
    while(c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

vector<int> operator^(vector<int> &a,int b)
{
    vector<int> c;
    int t = 0;
    for(int i = 0;i < a.size() || t;i ++)
    {
        if(i < a.size()) t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}

int main()
{
    scanf("%d",&n);
    for(int i = 0;i < N;i ++)
        for(int j = 0;j <= i;j ++)
            if(!j) C[i][j].push_back(1);
            else C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]);
    int k = 0;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= n;j ++)
        {
            int bar;
            scanf("%d",&bar);
            k += bar;
        }
    vector<int> res;
    res.push_back(1);
    for(int i = 1;i <= n;i ++) res = res^i;
    for(int i = 1;i <= k;i ++)
    {
        vector<int> tmp = C[k][i];
        for(int j = 1;j <= n - i;j ++) tmp=tmp^j;
        if(i & 1) res = res-tmp;
        else res = res+tmp;
    }
    for(int i = res.size() - 1;i >= 0;i --) printf("%d",res[i]);
    puts("");
    return 0;
}

用二项式反演应该可以更快求出答案（留坑）

类似的题目：D-CCA的小球_牛客练习赛78 (nowcoder.com)

总结：

1. 先思考没有限制的问题如何求解
2. 恰好问题到至少问题的转换（容斥原理）

这道题不用那么复杂，因为每行都有一个障碍物，所以正解是错排