QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#198191#6954. Almost AcyclicPPPTL 0ms0kbC++177.1kb2023-10-03 09:05:172023-10-03 09:05:17

Judging History

你现在查看的是最新测评结果

  • [2023-10-03 09:05:17]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [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;
}

详细

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...

output:


result: