一道很特别的数组构造题 排列的 n<18
但是这么特别的逻辑。。最快提交 竟然也只用了3分钟就写出来了
然后就是 不知道这种题目 猴年马月会再碰到。。
而且说实话 我并不不是很理解。。就是简洁
E - Permutation

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128_t
#define ar array<int, 2>
#define arr array<int, 3>
int  n, m, k, inf = 1LL << 61, mod = 998244353;// 1e9+7;
const int N = 5e5 + 50;void solve() {cin >> n >> m;vector<ar>mp[n + 1];for (int i = 0; i < m; ++i) {int x, y, z;cin >> x >> y >> z;mp[x].push_back({y, z});}vector<int>f(1 << n);f[0] = 1;for (int t = 1; t <= n; ++t) {for (int s = (1 << n) - 1; s >= 0; s--) {//滚动下for (int i = 0; i < n; ++i)if (~s >> i & 1)f[s | 1 << i] += f[s];}for (auto[y, z] : mp[t]) {//check 过滤for (int s = 0; s < 1 << n; ++s) {int x = s & (1 << y) - 1;//？其他不考虑if (__builtin_popcountll(x) > z)f[s] = 0;}}}cout << f.back();
};// 这种感觉就是dp 。。就是dp 不过。。挺特殊的。。很少见这种dpsigned main() {ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(15);
#ifdef DEBUGfreopen("../1.in", "r", stdin);
#endif//init_f();//init();//expr();// int T; cin >> T; while(T--)solve();return 0;
}