QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #198191 | #6954. Almost Acyclic | PPP | TL | 0ms | 0kb | C++17 | 7.1kb | 2023-10-03 09:05:17 | 2023-10-03 09:05:17 |
answer
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int mod = (int)1e9 + 7;
int mult(int a, int b) {
return (1LL * a * b) % mod;
}
int sum(int a, int b) {
int s = a + b;
if (s >= mod) s -= mod;
return s;
}
int sub(int a, int b) {
int s = a - b;
if (s < 0) s += mod;
return s;
}
const int maxN = (1 << 16) + 2;
int w[16][16];
int n;
int tree[maxN];
int forest[maxN];
int uni[maxN];
int uni_bad[maxN];
int DP[maxN][3];
int trans[16][maxN][4];
int DP2[maxN][4][2];
void upd(int& a, int b) {
a += b;
if (a >= mod) a -= mod;
}
int help[maxN][4][2];
void solve() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> w[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int mask = 0; mask < (1 << n); mask++) {
if (mask & (1 << i)) continue;
int prod = 1;
int s1 = 0;
int s2 = 0;
for (int b = 0; b < n; b++) {
if (mask & (1 << b)) {
prod = mult(prod, sum(w[i][b], 1));
s2 = sum(s2, mult(w[i][b], s1));
s1 = sum(s1, w[i][b]);
}
}
trans[i][mask][0] = s1;
trans[i][mask][1] = s2;
// if (i == 0 && mask == 6) {
// cout << s2 << " ??? " << endl;
// }
trans[i][mask][2] = sub(prod, sum(1, sum(s1, s2)));
}
}
for (int mask = 1; mask < (1 << n); mask++) {
int x = __builtin_ctz(mask);
if (mask == (1 << x)) {
tree[mask] = 1;
}
else {
tree[mask] = 0;
int y = __builtin_ctz(mask ^ (1 << x));
int M = (mask ^ (1 << x)) ^ (1 << y);
int T = M;
while (true) {
tree[mask] = sum(tree[mask],
mult(tree[T ^ (1 << y)], mult(tree[(M ^ T) ^ (1 << x)], trans[x][T ^ (1 << y)][0])));
if (T == 0) break;
T = M & (T - 1);
}
}
}
uni[0] = 0;
//uni_forest - one uni, others not
for (int mask = 1; mask < (1 << n); mask++) {
uni[mask] = 0;
uni_bad[mask] = 0;
int x = __builtin_ctz(mask);
if (mask == (1 << x)) {
continue;
}
else {
uni[mask] = 0;
int y = __builtin_ctz(mask ^ (1 << x));
int M = (mask ^ (1 << x)) ^ (1 << y);
int T = M;
while (true) {
uni[mask] = sum(uni[mask],
mult(uni[T ^ (1 << y)], mult(tree[(M ^ T) ^ (1 << x)], trans[x][T ^ (1 << y)][0])));
uni[mask] = sum(uni[mask],
mult(tree[T ^ (1 << y)], mult(uni[(M ^ T) ^ (1 << x)],
trans[x][T ^ (1 << y)][0])));
uni[mask] = sum(uni[mask],
mult(tree[T ^ (1 << y)], mult(tree[(M ^ T) ^ (1 << x)],
trans[x][T ^ (1 << y)][1])));
if (T == 0) break;
T = M & (T - 1);
}
}
}
int S = sum(uni[(1 << n) - 1], tree[(1 << n) - 1]);
for (int a = 0; a < n; a++) {
DP[0][0] = 1;
for (int mask = 1; mask < (1 << n); mask++) {
if (mask & (1 << a)) continue;
for (int q = 0; q < 3; q++) {
DP[mask][q] = 0;
}
int x = __builtin_ctz(mask);
int M = (mask ^ (1 << x));
int T = M;
while (true) {
for (int p = 0; p <= 2; p++) {
for (int q = 0; q <= 2; q++) {
upd(DP[mask][min(p + q, 2)], mult(DP[M ^ T][q], mult(tree[T ^ (1 << x)],
trans[a][T ^ (1 << x)][p])));
}
}
if (T == 0) break;
T = M & (T - 1);
}
}
S = sum(S, DP[((1 << n) - 1) ^ (1 << a)][2]);
}
// cout << S << " ??? " << endl;
for (int a = 0; a < n; a++) {
for (int b = a + 1; b < n; b++) {
// if (b != 3) continue;
DP2[0][1][1] = w[a][b];
DP2[0][0][0] = 1;
for (int mask = 1; mask < (1 << n); mask++) {
if (mask & (1 << a)) continue;
if (mask & (1 << b)) continue;
for (int q = 0; q < 4; q++) {
for (int s = 0; s < 2; s++) {
DP2[mask][q][s] = 0;
help[mask][q][s] = 0;
}
}
for (int cnt_a = 0; cnt_a <= 3; cnt_a++) {
for (int cnt_b = 0; cnt_b <= 3; cnt_b++) {
if (cnt_a >= 2 || cnt_b >= 2) continue;
int X_a = 0, X_b = 0;
if (cnt_a == 0) X_a = 1;
else X_a = trans[a][mask][cnt_a - 1];
if (cnt_b == 0) X_b = 1;
else X_b = trans[b][mask][cnt_b - 1];
if (cnt_a == 0 && cnt_b == 0) continue;
upd(help[mask][min(cnt_a + cnt_b - 1, 3)][(cnt_a > 0 && cnt_b > 0)],
mult(tree[mask], mult(X_a, X_b)));
}
}
int x = __builtin_ctz(mask);
int M = (mask ^ (1 << x));
int T = M;
while (true) {
for (int p = 0; p <= 3; p++) {
for (int q = 0; q < 2; q++) {
if (!DP2[M ^ T][p][q]) continue;
for (int add = 0; add <= 3; add++) {
// if (p + add >= 3 && help[T ^ (1 << x)][add][1]) {
// cout << " HI " << endl;
// cout << mask << endl;
// }
upd(DP2[mask][min(p + add, 3)][q],
mult(DP2[M ^ T][p][q], help[T ^ (1 << x)][add][0]));
upd(DP2[mask][min(p + add, 3)][1],
mult(DP2[M ^ T][p][q], help[T ^ (1 << x)][add][1]));
}
}
}
if (T == 0) break;
T = M & (T - 1);
}
}
S = sub(S, DP2[((1 << n) - 1) ^ (1 << a) ^ (1 << b)][3][1]);
// cout << S << " ? " << endl;
// if (a == 0 && b == 3) exit(0);
}
}
cout << S << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef DEBUG
freopen("input.txt", "r", stdin);
#endif
int tst;
cin >> tst;
while (tst--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
16 1 0 2 0 953763239 953763239 0 3 0 734999893 771971068 734999893 0 980773372 771971068 980773372 0 4 0 295218414 142837698 715328025 295218414 0 833169030 224028769 142837698 833169030 0 450275651 715328025 224028769 450275651 0 5 0 168127828 27116722 242318695 817220009 168127828 0 719973784 3288...