UOJ Logo immortalCO的博客

博客

UOIP十合一乱搞记+详细题解附代码

2016-07-06 22:33:03 By immortalCO

题目地址

http://uoj.ac/problem/208

题意简述

给出一张有向图,求有多少边的子集是DAG。

开头

为啥会做这一题呢?

几周前,机房高一神犇 WrongAnswer 在这题刚出来不久就秒掉了它。我也看了看,觉得比较interesting,而且我的数数题一向很弱,就决定开始搞了。从此入坑,一发不可收拾。

真是好题啊!搞了我整整一周。不过,其中的一些做法还是非常有趣的。

分点题解+日志

Case 1

打开1。卧槽,n和m都这么大,暴力肯定跑不出来。观察了一下,发现似乎前面几条边的左端点都不大于右端点?写个程序assert一发,确实如此。

那就很容易了,把自环扔掉,剩下k条边,答案就是$2^k$。跑了一下,过check了,就扔一边了。

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;

int main()
{
    assert(freopen("uoip1.in", "r", stdin));
    assert(freopen("uoip1.out", "w", stdout));
    int n, m;
    cin >> n >> m;
    int ans = 1;
    while(m--)
    {
        int x, y;
        cin >> x >> y;
        if(x != y)
        {
            assert(x < y);
            ans = 2ll * ans % mod;
        }
    }
    cout << ans;
    cerr << "check = " << (ans ^ 597855228) % 181 << endl;
}

Case 3

看了一下2,感觉没啥性质,就扔一边先去看3了。

一眼n=m。环套树即视感。仔细看一下,每条边左端点都是i。果然是环套树。写个程序assert一下,发现果然是环套树森林。

那么显然找环。不在环上的边,删不删没啥关系。环上的边就至少得删一条。于是就求出所有环大小,答案就是$2^{不在环上的边}\prod(2^{环的大小}-1) $咯。刚开始没想清楚WA了好几次,改清楚就过了。

#include <bits/stdc++.h>
using namespace std;
#define IL __inline__ __attribute__((always_inline))
#define RG register
const int mod = 1000000007;
const int MaxN = 100010;

namespace pb_ds
{
    int v[MaxN], timer;
    int to[MaxN], dep[MaxN];
    int ring;
    void dfs(int i)
    {
        v[i] = timer; if(!v[to[i]]) return (dep[to[i]] = dep[i] + 1, dfs(to[i]));
        if(v[to[i]] == timer) ring = (dep[i] - dep[to[i]] + 1); 
        else ring = -1;
    }
}

int main()
{
    using namespace pb_ds;
    assert(freopen("uoip3.in", "r", stdin));
    assert(freopen("uoip3.out", "w", stdout));

    int n, m;
    cin >> n >> m; assert(m == n);
    for(int i = 1; i <= n; ++i)
    {
        int x; cin >> x >> to[i];
        assert(x == i);
        assert(to[i] != i);
    }
    int ans = 1, other = n;
    for(int i = 1; i <= n; ++i) if(!v[i]) 
    {
        ++timer;
        dfs(i);
        if(ring == -1) continue;
        //printf("i = %d ring = %d\n", i, ring);
        other -= ring;
        int tmp = 1; while(ring--) tmp = (tmp << 1) % mod;
        ans = (long long) ans * (tmp - 1) % mod;
    }
    //printf("other = %d\n", other);
    while(other--) ans = (ans << 1) % mod;

    cout << ans;
    cerr << "check = " << (ans ^ 597855228) % 181 << endl;
}

Case 2 & 4

看4。一眼还是没啥性质。拉到下面去,似乎左右端点的宽度都差不多(我承认我是这么看出性质的)?写个程序验证一下,发现左右端点差不超过7。 想到2,发现左右端点同样不超过7。原来两个测试点能用一样的方法做。

这性质怎么用呢?貌似可以按顺序DP。考虑一条边(x,y),它能被加入当且仅当原图中不存在一条从y到x的路径;而由于端点距离不超过7,我们只需要考虑这个点往前7个点(包括本身,共8个点)的连通性。那我们就可以以最后8个点的传递闭包为状态进行DP。

我们可以用unsigned long long恰好64位整数来状压。然而这样状态很多,而我们知道合法的状态很有限(比如如果(1,2)和(2,3)为1,则(1,3)就必须为1)。我懒得预处理所有状态和转移,就直接用map<ull, int>来记录状态,开两个做滚动数组。每个位置还要编号前移,不过这也只是唯一的细节。

刚开始一直WA,后来发现1 << x的时候没用1ll。我很弱。

然后就把2和4都跑过了。2闪出,4开了O2只跑了8秒左右。

#include <bits/stdc++.h>
using namespace std;
#define IL __inline__ __attribute__((always_inline))
#define RG register
const int mod = 1000000007;
const int MaxN = 4010;
vector< pair<int, int> > e[MaxN];
#define pb push_back
#define mkp make_pair
#define fir first
#define sec second
typedef unsigned long long ull;

namespace pb_ds
{
    IL int inc(RG int x, RG int v) {x += v; return x >= mod ? x - mod : x;}
    IL void add(RG int& x, RG int v) {x = inc(x, v);}
    //number from 0 to 7
    //chuan di bi bao
    const ull empty = 9241421688590303745ull;
    IL bool test(RG const ull& s, RG int x, RG int y) {return s >> (x << 3 | y) & 1;}
    IL void set(RG ull& s, RG int x, RG int y) {s |= 1ull << (x << 3 | y);}
    IL int out_set(RG const ull& s, RG int i) {return (s >> (i << 3)) & 255;}
    IL void print(RG const ull& s, RG int n = 8)
    {
        for(RG int i = 0; i != n; ++i)
            for(RG int j = 0; j != n; ++j)
                printf("%d%c", test(s, i, j), " \n"[j + 1 == n]);
    }
    IL ull add_edge(RG ull s, RG int x, RG int y)
    {
        if(test(s, y, x)) return 0;
        for(RG int i = 0; i != 8; ++i) if(test(s, i, x))
            s |= (ull) out_set(s, y) << (i << 3);
        return s;
    }
    IL ull move_next(RG const ull& s)
    {
        //(x, y) -> (x + 1, y + 1)
        RG ull ret = empty;
        for(RG int i = 0; i + 1 != 8; ++i)    
            for(RG int j = 0; j + 1 != 8; ++j)
                if(test(s, i, j)) set(ret, i + 1, j + 1);
        return ret;
    }

    map<ull, int> Q[2];
    template<class T> void reinit(RG T& t) {t.~T(); new (&t)T; }
}

int main()
{
    using namespace pb_ds;
    assert(freopen("uoip4.in", "r", stdin));
    assert(freopen("uoip4.out", "w", stdout));
    int n, m;
    cin >> n >> m;
    while(m--)
    {
        int x, y;
        cin >> x >> y;
        assert(fabs(x - y) <= 7);
        if(x == y) continue;
        e[max(x, y)].pb(mkp(x, y));
    }
    RG bool d = 0;
    Q[d][empty] = 1;
    RG map<ull, int>::iterator iter, end;
    #define formap(M) for(iter = M.begin(), end = M.end(); iter != end; ++iter)
    RG ull next;
    for(RG int p = 1; p <= n; ++p)
    {
        reinit(Q[d ^= 1]);
        formap(Q[!d]) add(Q[d][move_next(iter->fir)], iter->sec);
        for(RG unsigned i = 0; i != e[p].size(); ++i)
        {
            RG int x = p - e[p][i].fir, y = p - e[p][i].sec;
            reinit(Q[d ^= 1]);
            formap(Q[!d]) 
            {
                add(Q[d][iter->fir], iter->sec);
                next = add_edge(iter->fir, x, y);
                if(next) add(Q[d][next], iter->sec);
            }
        }
    }
    RG int ans = 0;
    formap(Q[d]) add(ans, iter->sec);
    cout << ans;// << endl;
    cerr << "check = " << (ans ^ 597855228) % 181 << endl;
}

Case 5

看起来并没有啥规律……

我相信出题人一定隐藏了什么奇怪的性质,毕竟这才第5个点,不可能用啥高端算法吧。用Mathematica画了个图,没看出啥性质。写了个找连通块的程序,每个连通块也不小。

最后我写了一个找强连通的程序,发现大多数强连通分量都是1,最大一个只有4。于是就可以每个强连通分量暴力枚举边,每个强连通分量方案相乘,强连通分量之间的边直接用$2^{个数}$乘在答案上即可。

这个点的性质真神奇…………………

#include <bits/stdc++.h>
using namespace std;
#define IL __inline__ __attribute__((always_inline))
#define RG register
const int mod = 1000000007;
const int MaxN = 1010;
#define pb push_back
#define mkp make_pair
#define fir first
#define sec second

namespace pb_ds
{
    vector<int> e[MaxN];
    int dfn[MaxN], low[MaxN], timer;
    int stack[MaxN], top;
    int bel[MaxN], bid[MaxN], total;
    vector<int> blo[MaxN];

    void dfs(RG int i)
    {
        dfn[i] = low[i] = ++timer;
        stack[++top] = i;
        for(RG unsigned j = 0; j != e[i].size(); ++j)
            if(!dfn[e[i][j]])
            {
                dfs(e[i][j]);
                low[i] = min(low[i], low[e[i][j]]);
            }
            else if(!bel[e[i][j]])
                low[i] = min(low[i], dfn[e[i][j]]);
        if(low[i] == dfn[i])
        {
            RG int tmp;
            ++total;
            do 
            {
                tmp = stack[top--];
                bel[tmp] = total;
                bid[tmp] = blo[total].size();
                blo[total].pb(tmp);
            }
            while(tmp != i);
        }
    }

    struct Edge{int x, y;};
}

int main()
{
    using namespace pb_ds;
    assert(freopen("uoip5.in", "r", stdin));
    assert(freopen("uoip5.out", "w", stdout));

    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        int x, y; cin >> x >> y;
        if(x == y) {--i, --m; continue;}
        e[x].pb(y);
    }
    for(int i = 1; i <= n; ++i) if(!dfn[i]) dfs(i);
    int ans = 1;
    for(int B = 1; B <= total; ++B)
    {
        //cout << blo[B].size() << endl;
        static Edge edge[MaxN];
        int M = 0, size = blo[B].size();
        for(int i = 0; i != size; ++i)
        {
            int p = blo[B][i];
            for(int j = 0; j != (int) e[p].size(); ++j)
                if(bel[e[p][j]] == B)
                {
                    edge[M++] = (Edge) {i, bid[e[p][j]]};
                }
        }
        m -= M;
        int cur = 0;
        for(int s = 0; s != (1 << M); ++s)
        {
            static bool v[20][20];
            for(int i = 0; i != size; ++i)
                memset(v[i], 0, size), v[i][i] = 1;
            for(int i = 0; i != M; ++i)
                if(s >> i & 1) v[edge[i].x][edge[i].y] = 1;
            for(int k = 0; k != size; ++k)
                for(int i = 0; i != size; ++i)
                    for(int j = 0; j != size; ++j)
                        v[i][j] |= v[i][k] && v[k][j];
            for(int i = 0; i != size; ++i)
                for(int j = 0; j != i; ++j)
                    if(v[i][j] && v[j][i]) goto failed;
            ++cur;
            failed: ;
        }
        ans = (long long) ans * cur % mod;
    }
    while(m--) ans = (ans << 1) % mod;
    cout << ans;
    cerr << "check = " << (ans ^ 597855228) % 181 << endl;
}

Case 6 & 7 & 8

开6,发现是100个点的完全图。据说是个挺难推的式子。先放着去看7、8。

7和8中,点数很少。想起陈老师的《主旋律》那题。似乎可以容斥?找了些资料,发现可以对于每个子集S枚举源点集合s,则我们就有这些规则:

  • 任何以s里面的点为右端点的边都不能选
  • s指向S-s中的点可以任意选择连不连
  • S-s必须也是DAG。

于是就可以状压DP。记f(S)表示S集合为DAG的方案数,枚举源点集合s,则贡献为$2^{s连向S-s的边数}f(S-s)$。注意到这里会算重,但是符合容斥的性质,因此乘上$(-1)^{|S|+1}$即可。但是直接这么做是$n3^n$的(求s向S-s连边数),8可能要跑很久。我们可以利用无重边的性质,利用位运算加速,优化到$3^n$,这样8就只要跑80s左右了。

再回去做6,现在6就很简单了。由于结构相同,相同大小的子集的f都相同。于是就转移时枚举|s|,乘组合数即可。似乎许多本来要暴力的容斥,有了特殊的性质后,就可以高效解决了。

Case 7 & 8 程序

#include <bits/stdc++.h>
using namespace std;
#define IL __inline__ __attribute__((always_inline))
#define RG register
typedef long long ll;
const int mod = 1000000007;
IL int F() 
{
    RG char ch;
    while(ch = getchar(), ch < '0' || ch > '9')    ;
    RG int ans = ch - '0';
    while(ch = getchar(), '0' <= ch && ch <= '9') ans = ans * 10 + ch - '0';
    return ans;
}
IL int inc(RG int x, RG int v) {x += v; return x >= mod ? x - mod : x;}
IL int dec(RG int x, RG int v) {x -= v; return x < 0 ? x + mod : x;}

const int MaxN = 22;
int f[1 << MaxN], g[1 << MaxN];
int e_i[MaxN], e_o[MaxN];
int Pow[MaxN * MaxN], Pop[1 << MaxN], Fir[1 << MaxN];
#define Bit(i) (1 << (i))

int main()
{
    assert(freopen("uoip8.in", "r", stdin));
    assert(freopen("uoip8.out", "w", stdout));

    RG int n = F(), m = F();
    Pow[0] = 1;
    for(RG int i = 1; i <= m; ++i)
    {
        RG int x = F() - 1, y = F() - 1;
        e_o[x] |= 1 << y;
        e_i[y] |= 1 << x;
        Pow[i] = inc(Pow[i - 1], Pow[i - 1]);
    }
    f[0] = 1;
    for(RG int set = 1, sub, tmp, rev, pos, val; set != Bit(n); ++set)
    {
        cerr << set << '\n';
        Pop[set] = __builtin_popcount(set);
        Fir[set] = __builtin_ctz(set);
        tmp = (Pop[set] & 1) ? 1 : mod - 1;
        for(sub = set & (set - 1); sub; sub = set & (sub - 1))
        {
            pos = Fir[rev = set - sub];
            val = g[rev] = g[rev - Bit(pos)] + Pop[e_o[pos] & sub] - Pop[e_i[pos] & rev];
            tmp = (Pop[sub] & 1)
                ? inc(tmp, (ll) Pow[val] * f[rev] % mod)
                : dec(tmp, (ll) Pow[val] * f[rev] % mod);
        }
        f[set] = tmp;
    }
    RG int ans = f[Bit(n) - 1];
    cout << ans;
    cerr << "check = " << (ans ^ 597855228) % 181 << endl;    
}

Case 6 程序

#include <bits/stdc++.h>
using namespace std;
#define IL __inline__ __attribute__((always_inline))
#define RG register
typedef long long ll;
const int mod = 1000000007;
IL int F() 
{
    RG char ch;
    while(ch = getchar(), ch < '0' || ch > '9')    ;
    RG int ans = ch - '0';
    while(ch = getchar(), '0' <= ch && ch <= '9') ans = ans * 10 + ch - '0';
    return ans;
}
const int MaxN = 3010;
int comb[MaxN][MaxN], p[MaxN * MaxN], f[MaxN];

int main()
{
    assert(freopen("uoip6.in", "r", stdin));
    assert(freopen("uoip6.out", "w", stdout));

    RG int n = F();
    comb[0][0] = p[0] = 1;
    for(RG int i = 1, u = n * n; i <= u; ++i)
        p[i] = (p[i - 1] << 1) % mod;
    f[0] = 1;
    for(RG int i = 1, j, tmp; i <= n; ++i)
    {
        tmp = 0;
        for(j = comb[i][0] = 1; j <= i; ++j)
        {
            comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % mod;
            tmp = (j & 1)
                ? int((tmp + (ll) comb[i][j] * p[j * (i - j)] % mod * f[i - j]) % mod)
                : int((tmp - (ll) comb[i][j] * p[j * (i - j)] % mod * f[i - j]) % mod);
        }
        f[i] = tmp;
    }
    RG int ans = (f[n] + mod) % mod;    
    cout << ans;
    cerr << "check = " << (ans ^ 597855228) % 181 << endl;    
}

Case 9

一眼还是没啥性质…

发现除了前面两三个点,接下来这么多行中,可以两行两行分成一组,每一组左端点或右端点中都有一个相同的。也就是相当于一个一个点加入图中,每个点朝已经加入的任意两个点连任意方向的边(似乎是一种广义的树?)。

然而发现了这个似乎并没有什么帮助。先拿5的程序来跑,最大的双连通分量非常大,这个方法不可行。然后想起某模拟赛的一题“图染色计数”,发现外向和内向DAG都可以直接删掉,答案是一个乘在外面的常数。试着写了一些代码,删掉了四五十个点,然而剩下的点还是很多。接下来就是那些度为1的点了,它们构成了一些链。注意到第8个点中那个DP之所以可行,是因为能计算出一条边连或不连的方案数。把链缩成边,一条由$k$条边组成的新边,连的方案数是1,不连的方案数是$2^k-1$。这样还有些重边,那么也可以用类似的方法求出重边合并后连和不连的方案数。

写代码中出现了各种逗比错误,我真是太弱。最后缩完链后,点只有23个了。然而我不太会继续往下缩,也不是特别会处理有具体方案数的边,就直接写了一个$m3^{23}$的算法……半夜去跑……跑了14h终于跑了出来……

要是在考场上肯定跑不出来了……据 WrongAnswer 说他手动缩掉了两个点,然后又强行优化成$3^{21}$,真是令人膜拜不已。

(千万不要尝试用这个程序去跑……)

#include <bits/stdc++.h>
using namespace std;
#define IL __inline__ __attribute__((always_inline))
#define RG register
typedef long long ll;
const int mod = 1000000007;
IL int F() 
{
    RG char ch;
    while(ch = getchar(), ch < '0' || ch > '9')    ;
    RG int ans = ch - '0';
    while(ch = getchar(), '0' <= ch && ch <= '9') ans = ans * 10 + ch - '0';
    return ans;
}

#define pb push_back
#define mkp make_pair
#define fir first
#define sec second

namespace pb_ds
{
    IL int inc(RG int x, RG int v) {x += v; return x >= mod ? x - mod : x;}
    IL int dec(RG int x, RG int v) {x -= v; return x < 0 ? x + mod : x;}

    const int MaxN = 10010;
    vector<int> e_i[MaxN], e_o[MaxN];
    int Pow[MaxN], d_i[MaxN], d_o[MaxN];
    int pid[MaxN];
    bool del[MaxN];

    vector< pair<int, pair<int, int> > > e[MaxN];
    #define ForSTL(it, mp) for(RG typeof(mp.begin()) it = mp.begin(), ___e = mp.end(); it != ___e; ++it)

    const int MaxT = 25;
    int f[1 << MaxT], Pop[1 << MaxT], Fir[1 << MaxT];
}

int main()
{
    using namespace pb_ds;
    assert(freopen("uoip9.in", "r", stdin));
    assert(freopen("uoip9.out", "w", stdout));

    RG int n = F(), m = F();
    Pow[0] = 1;
    for(RG int i = 1; i <= m; ++i)
    {
        RG int x = F(), y = F();
        if(x == y) {--i, --m; continue;}
        assert(!e[x][y]);
        e_o[x].pb(y); ++d_o[x];
        e_i[y].pb(x); ++d_i[y];
        Pow[i] = inc(Pow[i - 1], Pow[i - 1]);
    }
    RG int ans = 1;

    static int q[MaxN];
    RG int l = 1, r = 0;
    for(RG int i = 1; i <= n; ++i) if(!d_i[i]) q[++r] = i;
    while(l <= r) 
    {
        RG int i = q[l++]; del[i] = 1;
        ans = (ll) ans * Pow[d_o[i]] % mod;
        for(RG unsigned j = 0; j != e_o[i].size(); ++j)
            if(!--d_i[e_o[i][j]]) q[++r] = e_o[i][j];
    }
    for(RG int i = 1; i <= n; ++i) if(d_i[i] && !d_o[i]) q[++r] = i;
    while(l <= r) 
    {
        RG int i = q[l++]; del[i] = 1;
        ans = (ll) ans * Pow[d_i[i]] % mod;
        for(RG unsigned j = 0; j != e_i[i].size(); ++j)
            if(!--d_o[e_i[i][j]]) q[++r] = e_i[i][j];
    }
//for(RG int i = 1; i <= n; ++i) if(d_i[i] * d_o[i]) printf("%d\n", i);
    //step 1
    //if(0)
    {
        RG int N = n; n = 0;
        memset(pid + 1, -1, N << 2);
        for(RG int i = 1; i <= N; ++i) if(d_i[i] * d_o[i] > 1) pid[i] = n++;
        //for(RG int i = 1; i <= N; ++i) if(d_i[i] * d_o[i]) pid[i] = n++;
        map< pair<int, int>, pair<int, int> > edge;
        for(RG int i = 1; i <= N; ++i) if(pid[i] >= 0)
        {
            for(RG unsigned j = 0; j != e_o[i].size(); ++j)
            {
                if(del[e_o[i][j]]) continue;
                RG int p = e_o[i][j], v = 1;
                while(pid[p] == -1) 
                {
                    assert(!del[p]);
                    del[p] = 1;
                    ++v;
                    for(RG unsigned k = 0; ; ++k)
                        if(!del[e_o[p][k]])
                        {
                            p = e_o[p][k];
                            break;
                        }
                }
                edge[mkp(pid[i], pid[p])].fir += (v);
                if(!edge[mkp(pid[i], pid[p])].sec) edge[mkp(pid[i], pid[p])].sec = 1;
                edge[mkp(pid[i], pid[p])].sec = (ll) edge[mkp(pid[i], pid[p])].sec * dec(Pow[v], 1) % mod;
            }
            //del[i] = 1;
        }
        for(RG int i = 1; i <= N; ++i) if(pid[i] == -1 && !del[i]) 
        {
            //there is a ring
            RG int p = i, v = 1;
            for( ; ; )
            {
                del[p] = 1;
                ForSTL(k, e_o[p]) if(pid[*k] == -1 && !del[*k])
                    {p = *k, ++v; goto next_step;}
                break;
                next_step: ;
            }
            ans = (ll) ans * dec(Pow[v], 1) % mod;
        }
        ForSTL(k, edge)
        {
            k->sec.fir = Pow[k->sec.fir];
            e[k->fir.fir].pb(mkp(k->fir.sec, k->sec));
        }
    }
    f[0] = 1;
    #define Bit(i) (1 << (i))
    for(RG int set = 1, tmp, sub, rev, pos, sum, gay, j, s; set != Bit(n); ++set)
    {
        cerr << set << '\n';
        Pop[set] = __builtin_popcount(set);
        Fir[set] = __builtin_ctz(set);
        tmp = 0;
        for(sub = set; sub; sub = set & (sub - 1))
        {
            rev = set - sub;
            sum = 1;
            for(gay = rev; gay; gay -= 1 << pos)
            {
                pos = Fir[gay];
                for(j = 0, s = e[pos].size(); j != s; ++j)
                    if(Bit(e[pos][j].fir) & sub) sum = (ll) sum * e[pos][j].sec.sec % mod;
            }
            for(gay = sub; gay; gay -= 1 << pos)
            {
                pos = Fir[gay];
                for(j = 0, s = e[pos].size(); j != s; ++j)
                    if(Bit(e[pos][j].fir) & rev) sum = (ll) sum * e[pos][j].sec.fir % mod;
                    else if(Bit(e[pos][j].fir) & sub) sum = (ll) sum * e[pos][j].sec.sec % mod;
            }
            tmp = (Pop[sub] & 1)
                ? inc(tmp, (ll) sum * f[rev] % mod)
                : dec(tmp, (ll) sum * f[rev] % mod);
        }
        f[set] = tmp;
    }
    ans = (ll) ans * f[Bit(n) - 1] % mod;
    cout << ans;
    cerr << "check = " << (ans ^ 597855228) % 181 << endl;    
}

Case 10

这幅图的性质和9类似,但是是一个点向之前选3个点连边,而且点数多了10倍。这下就不容易缩边了……

听说貌似树分解能做这个测试点?然而我并没有去WC2015,并不是很熟悉这一套理论。于是b*i*u一发,然而只找到一篇收费的文章,而且讲的内容寥寥无几……G*o*l*了一发也没啥收获。最后我灵机一动,在b*i*u搜Tree Decomposition,就搜到了一篇不错的论文:

http://dept-info.labri.fr/~dicky/PUF/M1Projects/TreeDecomposition-2011-2012.pdf

然后就研究了一段时间。

一个无向图$G = (V, E)$的树分解$(T, X)$表示一棵树$T$,其每个节点都有一个点集$X_i$满足以下条件

  1. $\bigcup_{i} X_i = V$,即任意一个点至少属于一个集合
  2. $\forall (x, y) \in E, \exists i \in T, s.t. x \in X_i, y \in Y_i$,即任意一条边的两个端点,都存在一个树上点集同时包含它们
  3. 对于任意$x, y\in T$,若存在$p \in X_x, p\in X_y$,则对于$x$到$y$唯一路径上的所有点$z$,都有$p \in X_z$。即包含一个特定图上点的树上点构成一个连通块。

对有向图的基图执行树分解。如果每个$X_i$都不大,那么我们就可以用4的方法进行传递闭包状压DP。由于性质3成立,我们也可以像测试点4那样,只需要记录需要的点,因为如果一个点不再需要被记录,它在后面也不会影响转移。似乎可以设计一种树形DP来求方案数。然而我们要先构造一个树分解。

论文中提供了一种方法。每次选择一个点度最小的点p,将p相邻的点连成团,然后将二元组(p, 与p相连的点集合S)压入栈中,最后从原图上删除p及其所有边,一直重复到只剩下两个点。建树时,令剩下的两个点为根,每次取栈顶,寻找编号最小的且包含S的点作为其父亲,并设当前点的$X$集合为{p}$\cup$与p相连的点集合S。这样构造出来的树分解,每个儿子的$X$集合只和其父亲差1,给转移带来了莫大的方便。

试着实现了这个算法,发现所有点的$X$集合大小均不超过4。真棒!那就可以DP了。然而我们该如何DP呢?刚开始我想用map<ull, int>作为DP数组进行记忆化搜索DP,然而后来却发现这样的转移具有后效性——子树中加的点可能会影响连通性,因此这里的转移不能直接用乘法原理!

感觉怎么做复杂度都会炸的样子。我突发奇想,干脆不记方案数,而是用map<ull, map<ull, int> >记录一个状态队列,表示进入子树时状态是$s$,离开子树时会有多少种状态、它们的方案数分别是多少。这样就可以解决这个问题,在儿子与儿子之间轻松转移了。

代码要注意从父亲切换到儿子和从儿子回到父亲时,状压中点编号的变动,十分繁琐……拍了好久终于拍过了……虽然看起来复杂度很糟糕,然而也只跑了2s就出解了。

提示:下面这个代码可以直接用来跑9。

#include <bits/stdc++.h>
using namespace std;
#define IL __inline__ __attribute__((always_inline))
#define RG register
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1000000007;
IL int F() 
{
    RG char ch;
    while(ch = getchar(), ch < '0' || ch > '9')    ;
    RG int ans = ch - '0';
    while(ch = getchar(), '0' <= ch && ch <= '9') ans = ans * 10 + ch - '0';
    return ans;
}

#define pb push_back
#define mkp make_pair
#define fir first
#define sec second

namespace pb_ds
{
    IL int inc(RG int x, RG int v) {x += v; return x >= mod ? x - mod : x;}
    IL int dec(RG int x, RG int v) {x -= v; return x < 0 ? x + mod : x;}
    IL void add(RG int& x, RG int v) {x = inc(x, v);}

    const int MaxN = 10010;
    bool e[MaxN][MaxN];
    bool E[MaxN][MaxN];
    int d[MaxN];
    bool v[MaxN];

    struct Piece {int p; vector<int> s;} S[MaxN];

    const ull empty = 9241421688590303745ull;
    IL bool test(RG const ull& s, RG int x, RG int y) {return s >> (x << 3 | y) & 1;}
    IL void set(RG ull& s, RG int x, RG int y) {s |= 1ull << (x << 3 | y);}
    IL void flip(RG ull& s, RG int x, RG int y) {s ^= 1ull << (x << 3 | y);}
    IL int out_set(RG const ull& s, RG int i) {return (s >> (i << 3)) & 255;}
    IL void print(RG const ull& s, RG int n = 8)
    {
        for(RG int i = 0; i != n; ++i)
            for(RG int j = 0; j != n; ++j)
                printf("%d%c", test(s, i, j), " \n"[j + 1 == n]);
    }
    IL ull add_edge(RG ull s, RG int x, RG int y)
    {
        if(test(s, y, x)) return 0;
        for(RG int i = 0; i != 8; ++i) if(test(s, i, x))
            s |= (ull) out_set(s, y) << (i << 3);
        return s;
    }

    struct Edge{int x, y;};
    template<class T> void reinit(RG T& t) {t.~T(); new (&t)T; }
    #define formap(III, EEE, M) for(III = M.begin(), EEE = M.end(); III != EEE; ++III)

    IL int value(RG map<ull, int>& M)
    {
        RG int ans = 0;
        RG map<ull, int>::iterator iter, end;
        formap(iter, end, M) add(ans, iter->sec);
        return ans;
    }

    struct Node *_T;
    struct Node
    {
        int p;
        vector<int> vec, son;
        map<ull, map<ull, int> > mem;
        IL bool include(RG const vector<int> &_V) const
        {
            RG int s = vec.size(), j = 0, S = _V.size();
            RG const int *v = &*vec.begin(), *V = &*_V.begin();
            for(RG int i = 0; i != S; ++i)
            {
                while(j != s && v[j] < V[i]) ++j;
                if(j == s || v[j] != V[i]) return 0;
            }
            return 1;
        }
        map<ull, int>& dp(RG const ull& s)
        {
            if(mem.find(s) != mem.end())
                return mem.find(s)->sec;

            RG map<ull, int> Q[2]; RG bool d = 0;
            RG map<ull, int>::iterator iter, end;
            Q[d][s] = 1;
            for(RG unsigned k = 0; k != son.size(); ++k)
            {
                RG Node &T = _T[son[k]];
                vec.pb(T.p);
                RG int n = vec.size(), np = n - 1, m = 0;

                RG Edge e[10];
                for(RG int i = 0; i != np; ++i)
                {
                    if(pb_ds::e[vec[i]][T.p]) e[m++] = (Edge) {i, np};
                    if(pb_ds::e[T.p][vec[i]]) e[m++] = (Edge) {np, i};
                }
                for(RG int i = 0; i != m; ++i)
                {
                    reinit(Q[d ^= 1]);
                    formap(iter, end, Q[!d])
                    {
                        add(Q[d][iter->fir], iter->sec);
                        RG ull next = add_edge(iter->fir, e[i].x, e[i].y);
                        if(next) add(Q[d][next], iter->sec);
                    }
                }

                RG int id[10];
                for(RG int i = 0; i != n; ++i)
                {
                    RG const int *k = find(&*T.vec.begin(), &*T.vec.end(), vec[i]);
                    if(k == &*T.vec.end()) id[i] = -1;
                    else id[i] = k - &*T.vec.begin();
                }

                reinit(Q[d ^= 1]);
                formap(iter, end, Q[!d])
                {
                    RG ull set = iter->fir, conv = empty;
                    for(RG int i = 0; i != n; ++i) if(~id[i])
                        for(RG int j = 0; j != n; ++j) if(~id[j])
                            if(test(set, i, j))
                                pb_ds::set(conv, id[i], id[j]);
                    RG map<ull, int>& ret = T.dp(conv);
                    RG map<ull, int>::iterator Iter, End;
                    formap(Iter, End, ret)
                    {
                        RG ull set = Iter->fir, conv = iter->fir;
                        for(RG int i = 0; i != n; ++i) if(~id[i])
                            for(RG int j = 0; j != n; ++j) if(i != j && ~id[j])
                                if(test(set, id[i], id[j]))
                                    conv = add_edge(conv, i, j);
                        for(RG int i = 0; i != np; ++i)
                        {
                            if(test(conv, i, np)) flip(conv, i, np);
                            if(test(conv, np, i)) flip(conv, np, i);
                        }
                        add(Q[d][conv], (ll) iter->sec * Iter->sec % mod);
                    }
                }
                vec.pop_back();
            }
            mem.insert(mkp(s, Q[d]));
            return mem.find(s)->sec;
        }
    } T[MaxN];
}

int main()
{
    using namespace pb_ds;
    assert(freopen("uoip10.in", "r", stdin));
    assert(freopen("uoip10.out", "w", stdout));
    RG int n = F(), m = F();
    for(RG int i = 1; i <= m; ++i)
    {
        RG int x = F(), y = F();
        if(x == y) {--i, --m; continue;}
        ++d[x]; 
        ++d[y];
        E[x][y] = E[y][x] = 1;
        e[x][y] = 1;
        //e[y][x] = -1;
    }
    RG int top = 0;
    for(RG int lim = 1, k = n; k > 1; ++lim)
    {
        for(RG int p; k > 1; )
        {
            p = 0;
            for(RG int i = 1; i <= n; ++i)
                if(!v[i] && d[i] < lim) {p = i; break;}
            if(!p) break;
            --k;
            v[p] = 1;
            S[++top].p = p;
            for(RG int i = 1; i <= n; ++i)
                if(!v[i] && E[p][i]) 
                {
                    S[top].s.pb(i);
                    --d[i];
                }
            RG int D = d[p], *s = &*S[top].s.begin();
            for(RG int i = 0; i != D; ++i)
                for(RG int j = 0; j != i; ++j)
                    if(!E[s[i]][s[j]])
                    {
                        ++d[s[i]], ++d[s[j]];
                        E[s[i]][s[j]] = E[s[j]][s[i]] = 1;
                    }
        }
    }
    RG int N = 0;
    while(top)
    {
        RG Piece& P = S[top--];
        sort(&*P.s.begin(), &*P.s.end());
        RG Node cur = (Node) {P.p, P.s};
        cur.vec.pb(P.p);
        inplace_merge(&*cur.vec.begin(), &*cur.vec.end() - 1, &*cur.vec.end());
        if(!N) T[++N] = cur;
        else for(RG int i = 1; i <= N; ++i)
            if(T[i].include(P.s)) 
            {
                T[++N] = cur, T[i].son.pb(N);
                break;
            }
    }

    static Edge edge[10]; RG int tot = 0;
    for(RG unsigned i = 0; i != T[1].vec.size(); ++i)
        for(RG unsigned j = 0; j != T[1].vec.size(); ++j)
            if(e[T[1].vec[i]][T[1].vec[j]]) 
                edge[tot++] = (Edge) {(int) i, (int) j};
    _T = T;
    RG map<ull, int> Q[2];
    RG map<ull, int>::iterator iter, end;
    RG bool d = 0;
    Q[d][empty] = 1;
    for(RG int i = 0; i != tot; ++i)
    {
        reinit(Q[d ^= 1]);
        formap(iter, end, Q[!d])
        {
            add(Q[d][iter->fir], iter->sec);
            RG ull next = add_edge(iter->fir, edge[i].x, edge[i].y);
            if(next) add(Q[d][next], iter->sec);
        }
    }
    RG int ans = 0;
    formap(iter, end, Q[d]) 
        ans = (ans + (ll) iter->sec * value(T[1].dp(iter->fir))) % mod;

    cout << ans;// << endl;
    cerr << "check = " << (ans ^ 597855228) % 181 << endl;
}

/*
5 7
2 1
1 3
2 3
4 1
3 4
5 2
4 5

^/\*lgg\*/

总结

这真是一道神题啊!

orz matthew99

orz WrongAnswer

我真是太弱了!

完结撒花!

评论

zhouzixuan
前排好评
matthew99
前排好评

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。