题目描述

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

样例

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

算法1

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

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

如果加入障碍物，那么我们就要计算这$n!$的方案数中有多少方案是不存在任何一个棋子是摆在障碍物上的

本题有一个很强的性质:每一行每一列只可能有一个障碍物

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

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

假设有$k$个障碍物

至少有$i$个棋子放在了障碍物上的方案数$s_i = C_{k}^{i} * (n - i)!$

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

$ans = n! + \sum_{i=1}^{k}(-1)^{i} C_{k}^{i} * (n - i)!$

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

时间复杂度 $O(n^2)$

参考文献

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;
}

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

总结：

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