烷基计数 加强版 加强版[loj6538]

发表于 分类于

题目链接

烷基计数

烷基计数 加强版

烷基计数 加强版 加强版

题解

主要是想记录下自己第一道牛顿迭代的题qwq

设 $f_i$ 表示 $i$ 个节点时的答案，那么有：

$f_0=1,f_i=\sum_{j+k+l+1=i}f_j f_k f_l$。

显然这个是错的。因为没有考虑树同构的情况。

设 $F(x)$ 表示 $f$ 的OGF。

这里有 $3!=6$ 种置换。

由Burnside引理得，总方案数=每个置换的不动点个数的平均数。

  • 对于 $(1,2,3)$ 这种情况，随你便，也就是 $F^3(x)$。
  • 对于 $(2,1,3),(3,2,1),(1,3,2)$ 这三种情况，有两个是需要一样的，也就是 $F(x^2)F(x)$。
  • 对于剩下两种情况，三个都必须一样，也就是 $F(x^3)$。

那么就有：

$$F(x)=x\frac{F^3(x)+3F(x^2)F(x)+2F(x^3)}{6}+1$$

设 $G(F(x))=x\frac{F^3(x)+3F(x^2)F(x)+2F(x^3)}{6}+1-F(x)$

假设求出了在模 $x^{\frac{n}{2}}$ 意义下的 $F(x)$，由牛顿迭代得：

$$F_{new}(x)=F(x)-\frac{G(F(x))}{G’(F(x))}$$

而如果求出了在模 $x^{\frac{n}{2}}$ 意义下的 $F(x)$，那么模 $x^n$ 意义下的 $F(x^2),F(x^3)$ 也已经知道了。

对 $G(F(x))$ 求导得：

$$\frac{G(F(x))}{G’(F(x))}=\frac{x(F^3(x)+3F(x^2)F(x)+2F(x^3))-6F(x)-6}{x(3F^2(x)+3F(x^2))-6}$$

那么有：

$$F_{new}(x)=F(x)-\frac{x(F^3(x)+3F(x^2)F(x)+2F(x^3))-6F(x)-6}{x(3F^2(x)+3F(x^2))-6}$$

时间复杂度 $O(n\log 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
#include <vector>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
    int x=0; char ch=getchar(); bool f=0;
    for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return f?-x:x;
}
#define CASET fo(___,1,read())
const ll mod=998244353;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y){y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;return ans;}

typedef vector<ll> Poly;

const int M=1<<19;
namespace NTT{
    int R[M]; ll W[M];
    inline void init()
    {
        ll wn;
        for(int i=1;i<M;i<<=1)
        {
            W[i]=1; wn=Pow(3,(mod-1)/2/i);
            fo(j,1,i-1) W[i+j]=W[i+j-1]*wn%mod;
        }
    }
    inline void ntt(ll *a,int n,int opt)
    {
        fo(i,0,n-1)
        {
            R[i]=(R[i>>1]>>1)|((i&1)*(n>>1));
            if(i<R[i]) swap(a[i],a[R[i]]);
        }
        ll w;
        for(int i=1;i<n;i<<=1)
            for(int j=0;j<n;j+=(i<<1))
                for(int k=0;k<i;k++)
                    w=W[i+k]*a[i+j+k]%mod,
                    a[i+j+k]=Dec(a[j+k],w),
                    a[j+k]=Add(a[j+k],w);
        if(opt==1) return;
        reverse(a+1,a+n);
        w=Pow(n,mod-2);
        fo(i,0,n-1) a[i]=w*a[i]%mod;
    }
    inline void ntt(Poly &A,int n,int opt){ntt(&A[0],n,opt);}
}
using NTT::ntt;
inline Poly operator +(Poly A,Poly B)
{
    A.resize(max(A.size(),B.size()));
    fo(i,0,B.size()-1) A[i]=Add(A[i],B[i]);
    return A;
}
inline Poly operator -(Poly A,Poly B)
{
    A.resize(max(A.size(),B.size()));
    fo(i,0,B.size()-1) A[i]=Dec(A[i],B[i]);
    return A;
}
inline Poly operator *(Poly A,ll x)
{
    fo(i,0,A.size()-1) A[i]=A[i]*x%mod;
    return A;
}
inline Poly operator *(Poly A,Poly B)
{
    int n=A.size(),m=B.size(),k=n+m-1,len=1;
    for(;len<=k;len<<=1);
    A.resize(len); ntt(A,len,1);
    B.resize(len); ntt(B,len,1);
    fo(i,0,len-1) A[i]=A[i]*B[i]%mod;
    ntt(A,len,-1);
    A.resize(k);
    return A;
}
inline Poly operator ~(Poly f)
{
    int n=f.size();
    Poly g,h;
    g.pb(Pow(f[0],mod-2));
    int m=2;
    for(;m<n;m<<=1)
    {
        h.resize(m<<1);
        fo(i,0,m-1) h[i]=f[i];
        g.resize(m<<1);
        ntt(h,m<<1,1); ntt(g,m<<1,1);
        fo(i,0,(m<<1)-1) g[i]=Mul(2+mod-Mul(g[i],h[i]),g[i]);
        ntt(g,m<<1,-1); g.resize(m);
    }
    g.resize(m<<1); f.resize(m<<1);
    ntt(f,m<<1,1); ntt(g,m<<1,1);
    fo(i,0,(m<<1)-1) g[i]=Mul(2+mod-Mul(g[i],f[i]),g[i]);
    ntt(g,m<<1,-1); g.resize(n);
    return g;
}
Poly solve(int n)
{
    Poly f; f.clear(); f.pb(1);
    if(n==1) return f;
    int m=1;
    Poly f2,f3,g,h,a;
    for(;m<(n<<1);m<<=1)
    {
        f.resize(m); f2.resize(m); f3.resize(m);
        fo(i,0,m-1) f2[i]=f3[i]=0;
        for(int i=0;i<m;i+=2) f2[i]=f[i/2];
        for(int i=0;i<m;i+=3) f3[i]=f[i/3];
        a=f*f; a.resize(m);
        h=(a+f2)*3; h.insert(h.begin(),mod-6);
        a=f*a; a.resize(m);
        g=a+((f2*f)*3)+(f3*2);
        g.insert(g.begin(),6);
        g=g-(f*6); g.resize(m);
        g=g*(~h); g.resize(m);
        f=f-g;
    }
    f.resize(n);
    return f;
}
int n;
int main()
{
    NTT::init();
    n=read();
    Poly f=solve(n+1);
    printf("%lld",f[n]);
    return 0;
}