Processing math: 89%

LibreOJ 155 Tutte 多项式

发表于 | 分类于 | 28

因为不太想写长篇笔记就随便记篇题解吧……

我们考虑一个图 G=(V,E) 的 Tutte 多项式 TG(x,y)=∑A⊆E(x−1)k(A)−k(E)(y−1)k(A)+|A|−|V|

容易知道指数都是非负的，因此我们可以尝试给出一个在任意环上的算法。

首先我们知道其 Tutte 多项式等价于每个连通分量的 Tutte 多项式的乘积。因此不妨先假设 G 为连通图。
考虑 A 作为边集时的一个连通分量 S，令其导出子图的边集为 B，则定义其权值 fS(B)=(y−1)k(B)+|B|−|S|=(y−1)|B|−(|S|−1)

于是对于 A，其在 G 的 Tutte 多项式中的贡献即为各个连通分量的 f 的乘积乘上 (x−1)k(A)−k(E)=(x−1)k(A)−1。
因此若定义 gS 为 ∑fS(B)，其中 B 使得 S 为一个连通分量，则 G 的 Tutte 多项式即为 [wV]∑i≥1(x−1)i−1(∑S≠∅gSwS)ii!

这个地方乍一看要算任意 EGF 复合一个集合幂级数（虽然也是可做的），但是我们考虑给每个 gS 乘进一个 x−1，然后想办法除掉一个贡献（比如强制去掉编号最小的结点所在连通分量的贡献）即可转化为 exp。
并且，容易发现这个东西可以直接扩展到任意图上而不需要其他操作。

然后下一步是求出 gS。考虑进行逐点牛顿迭代。
对于 S∋n，考虑从 S 中删去 n 所构成的连通分量。
若一个连通分量与 n 连有 m 条边，则其贡献为 \sum\limits_{i=1}^m \binom mi (y-1)^i = y^m-1

然后由于新加入的点，需要另外除以一个 y-1。有趣的是由于这个东西恰好就是等比数列求和，所以可以方便地预处理。

时间复杂度 O(n^2 2^n)。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include <cstdio>
#include <cstring>
#define add(x,y) (x + y >= mod ? x + y - mod : x + y)
#define dec(x,y) (x < y ? x - y + mod : x - y)
#define popcnt __builtin_popcount
using namespace std;
const int LG = 21;
const int N = 1 << LG;
const int mod = 998244353;
inline int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
int lg,n;
int e[LG + 1];
int f[N],g[N],t[N];
int x,y;
namespace Set
{
    int fac[LG + 1],ifac[LG + 1],inv[LG + 1];
    inline void init()
    {
        fac[0] = 1;
        for(register int i = 1;i <= LG;++i)
            fac[i] = (long long)fac[i - 1] * i % mod;
        ifac[LG] = fpow(fac[LG],mod - 2);
        for(register int i = LG;i;--i)
            ifac[i - 1] = (long long)ifac[i] * i % mod;
        for(register int i = 1;i <= LG;++i)
            inv[i] = (long long)ifac[i] * fac[i - 1] % mod;
    }
    template<class T>
    inline void fmt(T a,int lg,int type)
    {
        for(register int w = 2,m = 1;w <= (1 << lg);w <<= 1,m <<= 1)
            for(register int i = 0;i < (1 << lg);i += w)
                for(register int j = 0;j < m;++j)
                    for(register int k = 0;k <= lg;++k)
                        a[i | j | m][k] = type == 1 ? add(a[i | j | m][k],a[i | j][k]) : dec(a[i | j | m][k],a[i | j][k]);
    }
    int t1[N][LG + 1];
    /*int t1[N][LG + 1],t2[N][LG + 1],t3[N][LG + 1];
    inline void mul(int *f,int *g,int *h,int lg)
    {
        int n = 1 << lg;
        for(register int i = 0;i < n;++i)
            memset(t1[i],0,sizeof(int) * (lg + 1)),
            memset(t2[i],0,sizeof(int) * (lg + 1)),
            memset(t3[i],0,sizeof(int) * (lg + 1));
        for(register int i = 0;i < n;++i)
            t1[i][popcnt(i)] = f[i],
            t2[i][popcnt(i)] = g[i];
        fmt(t1,lg,1);
        fmt(t2,lg,1);
        for(register int i = 0;i <= lg;++i)
            for(register int j = 0;j <= i;++j)
                for(register int k = 0;k < n;++k)
                    t3[i][k] = (t3[i][k] + (long long)t1[j][k] * t2[i - j][k]) % mod;
        fmt(t3,lg,-1);
        for(register int i = 0;i < n;++i)
            h[i] = t3[popcnt(i)][i];
    }
    inline void comp(int *f,int *g,int *h,int lg)
    {
        int n = 1 << lg;
        for(register int i = 0;i <= lg;++i)
            t1[i][0] = f[i];
        for(register int k = 0;k < lg;++k)
        {
            for(register int s = 0;s < (1 << k);++s)
                memset(t3[s],0,sizeof(int) * (k + 1)),
                t3[s][popcnt(s)] = g[(1 << k) | s];
            fmt(t3,k,1);
            for(register int i = 0;i < lg - k;++i)
                memcpy(t2 + (i << k + 1),t1 + (i << k),sizeof(int) * (LG + 1) << k);
            for(register int i = 1;i <= lg - k;++i)
            {
                auto arr = t1 + (i << k);
                static int tt[LG + 1];
                for(register int s = 0;s < (1 << k);++s)
                {
                    for(register int t = 0;t <= k;++t)
                    {
                        int v = 0;
                        for(register int l = 0;l <= t;++l)
                            v = (v + (long long)arr[s][l] * t3[s][t - l]) % mod;
                        tt[t] = v;
                    }
                    memcpy(arr[s],tt,sizeof(int) * (k + 1));
                }
                for(register int s = 0;s < (1 << k);++s)
                {
                    for(register int j = 0;j <= k;++j)
                        t2[(2 * i - 1 << k) + s][j + 1] = (t2[(i - 1 << k + 1) + s][j + 1] + arr[s][j]) % mod;
                    t2[(2 * i - 1 << k) + s][0] = t2[(i - 1 << k + 1) + s][0];
                }
            }
            memcpy(t1,t2,sizeof(int) * (LG + 1) * (lg - k) << k + 1);
        }
        fmt(t1,lg,-1);
        for(register int i = 0;i < n;++i)
            h[i] = t1[i][popcnt(i)];
    }*/
    inline void exp(int *g,int *h,int lg)
    {
        int n = 1 << lg;
        for(register int i = 0;i < n;++i)
            memset(t1[i],0,sizeof(int) * (lg + 1));
        for(register int i = 0;i < n;++i)
            t1[i][popcnt(i)] = g[i];
        fmt(t1,lg,1);
        for(register int s = 0;s < n;++s)
        {
            static int tt[LG + 1];
            memcpy(tt,t1[s],sizeof tt);
            t1[s][0] = 1;
            for(register int i = 1;i <= lg;++i)
            {
                int v = 0;
                for(register int j = 1;j <= i;++j)
                    v = (v + (long long)tt[j] * j % mod * t1[s][i - j]) % mod;
                t1[s][i] = (long long)v * inv[i] % mod;
            }
        }
        fmt(t1,lg,-1);
        for(register int i = 0;i < n;++i)
            h[i] = t1[i][popcnt(i)];
    }
}
int vis[LG + 1],crit[N],coe[LG + 1];
void dfs(int p)
{
    vis[p] = 1;
    for(register int i = 0;i < lg;++i)
        if(((e[p] >> i) & 1) && !vis[i])
            dfs(i);
}
int main()
{
    Set::init();
    scanf("%d",&lg),n = 1 << lg;
    for(register int i = 0;i < lg;++i)
        for(register int j = 0;j < lg;++j)
        {
            int x;
            scanf("%d",&x),e[i] |= x << j;
        }
    scanf("%d%d",&x,&y),x = dec(x,1);
    for(register int i = 0;i < lg;++i)
        if(!vis[i])
        {
            dfs(i);
            for(register int s = 0;s < n;++s)
                if((s >> i) & 1)
                    crit[s] = 1;
        }
    for(register int i = 1;i <= lg;++i)
        coe[i] = ((long long)coe[i - 1] * y + 1) % mod;
    for(register int i = 0;i < lg;++i)
    {
        for(register int s = 0;s < (1 << i);++s)
            t[s] = (long long)g[s] * coe[popcnt(e[i] & s)] % mod;
        Set::exp(t,g + (1 << i),i);
    }
    for(register int s = 1;s < n;++s)
        if(!crit[s])
            g[s] = (long long)g[s] * x % mod;
    Set::exp(g,f,lg);
    printf("%d\n",f[n - 1]);
}

Gitalking ...