题意
给定一个 (n imes n) 的矩阵，其中仅有 (k) 个位置的值可能不是 (1)。对于第 (i) 个位置 ((x_i,y_i))，其值为 (w_i)。要求这个矩阵的积和式，对 (10^9 + 7) 取模。
数据范围：(1 le n le 10^5)，(1 le k le 50)，(1 le x_i,y_i le n)，(0 le w_i < 998244353)。
题解
首先把每个 (w_i) 拆成 (1) 和 (w_i-1)，也就是把每个特殊位置看做是在 (1) 的基础下额外增加了 (w_i-1)。
然后枚举我们算积和式的时候用了哪些额外增加的元素，要求这些元素的 (x_i) 互不相同，(y_i) 也互不相同。
容易想到一个暴力：
对于每一列，枚举额外增加的是哪一行，或是不选择额外增加的，然后状压哪些行已经被占用了。
考虑优化。注意到如果一行在之后的列都不会用到了，那就可以不状压这行。
这样事实上就可以过了，但是这样可能会被卡到 (Theta(k^22^{frac{k}{2}}))。
注意到如果一行的元素很少，那我们去掉这一行就会很容易。
于是每次找到元素数最少的行，并找到用到这行的列，先枚举这些被用到的列。
这样跑得飞快，在 CF 上是最优解（截至 2021.11.4）。
代码
#include<bits/stdc++.h>
#define L(i, j, k) for (int i = (j); i <= (k); i++)
#define R(i, j, k) for (int i = (j); i >= (k); i--)
#define sz(a) ((int) (a).size())
#define ll long long
#define vi vector < int >
using namespace std;
const int N = 1 << 6, M = 1e5 + 7, mod = 1e9 + 7;
int n, m, a[N][N], fac[M], ns;
int x[N], y[N], w[N];
int arra[N], atot, arrb[N], btot;
int cnta[N], cntb[N];
unordered_map < ll, int > mp[N], cp[N];
int main () {
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
memset(a, -1, sizeof(a));
fac[0] = 1;
L(i, 1, n) fac[i] = (ll) fac[i - 1] * i % mod;
L(i, 1, m) {
cin >> x[i] >> y[i] >> w[i], (w[i] += mod - 1) %= mod;
arra[++atot] = x[i];
arrb[++btot] = y[i];
}
sort(arra + 1, arra + atot + 1), atot = unique(arra + 1, arra + atot + 1) - arra - 1;
sort(arrb + 1, arrb + btot + 1), btot = unique(arrb + 1, arrb + btot + 1) - arrb - 1;
L(i, 1, m)
x[i] = lower_bound (arra + 1, arra + atot + 1, x[i]) - arra, y[i] = lower_bound(arrb + 1, arrb + btot + 1, y[i]) - arrb,
a[x[i]][y[i]] = w[i], ++cnta[x[i]], ++cntb[y[i]];
mp[0][0] += 1;
while (1) {
int o = -1;
L(i, 1, btot) if(cntb[i] && (o == -1 || cntb[o] > cntb[i])) o = i;
if(o == -1)
break ;
L(i, 1, atot) if(a[i][o] != -1 && cnta[i]) {
cnta[i] = 0;
ll cle = ((1LL << btot) - 1) << 1, msk = 0;
vi S;
L(j, 1, btot) if(a[i][j] != -1) {
S.push_back(j);
cntb[j] -= 1, msk |= 1LL << j;
if(!cntb[j]) cle ^= 1LL << j;
}
L(z, 0, m)
for (auto u : mp[z]) {
(cp[z][u.first & cle] += u.second) %= mod;
for (const int &t : S) if(!(u.first >> t & 1))
(cp[z + 1][(u.first | (1LL << t)) & cle] += (ll) u.second * a[i][t] % mod) %= mod;
}
L(z, 0, m) swap (mp[z], cp[z]), cp[z].clear ();
}
}
L(z, 0, m) for (auto u : mp[z]) (ns += (ll) u.second * fac[n - z] % mod) %= mod;
cout << ns << '
';
return 0;
}
祝大家学习愉快！