Description
Solution
First, consider the properties of the product of graphs
Considering \ (G_1\times G_2 \), it may be assumed that \ (G_1,G_2 \) is connected. If it is not connected, it can be divided into the product of several connected blocks
If a graph is an outlier, there are \ (|g_1|g_2124\) Unicom blocks
Let's assume that \ (G_1,G_2 \) are not isolated points
It is found that \ ((x_1,y_1) \) and \ ((x_2,y_2) \) are connected if and only if there are two paths with the same length from \ (x_1 \) to \ (x_2 \) in \ (G_1 \) and from \ (y_1 \) to \ (y_2 \) in \ (G_2 \)
It is found that if you can jump repeatedly on one edge, you only care about the parity of the path
It can be discussed according to whether the original graph is a bipartite graph or not, so it is obvious that:
- If neither graph is bipartite, it will form a connected block of non bipartite graph
- Two graphs have exactly one bipartite graph, which will form a connected block of bipartite graph
- Both graphs are bipartite graphs, which will form two connected blocks of bipartite graphs
Calculate the contribution of outliers to the answer
If the number of non isolated points in each figure is \ (a_i \)
Then the contribution of outliers to the answer under this scheme is \ (\ prod m_i-\prod a_i \)
Just calculate the expectation of \ (\ prod a_i \), and it is easy to get \ (\ displaystyle E(a_i)=m_i(1-(\frac12)^{m_i-1})\)
Calculate the contribution of other points to the answer
Consider the product of graphs without outliers
Let the connected blocks in \ (G_0, G_1 \) and the number of connected blocks in bipartite graph be \ (A_0,A_1,B_0,B_1 \)
Then we can see from the above conclusion
The number of connected blocks in product \ (G_2=G_0\times G_1 \) and bipartite graph are \ (A_0B_0+A_1B_1,A_1B_0+A_0B_1 \)
If it is found to be in the form of XOR convolution, you can first FWT, then multiply the corresponding point values, and finally IFWT
Then the problem now is to find the sum of the number of connected blocks of a graph with \ (n \) points in all cases and the sum of the number of connected blocks of a bipartite graph with \ (n \) points in all cases
Calculate the number of connected blocks
Let the EGF of the number of graphs with \ (n \) points be \ (f (x) \), and the EGF of the number of connected graphs with \ (n \) points be \ (G(x) \)
Obviously \ (\ displaystyle F(x)=\sum\limits_i\frac{2^{\binom i2}}{i!}x^i\).
Considering that a graph can be disassembled into several connected graphs, there are \ (F(x)=e^{G(x)},G(x)=\ln F(x) \)
Let the EGF of the number of connected blocks of a graph with \ (n \) points be \ (H(x) \)
Then there are \ (H(n)=\sum\limits_i F(n-i)G(i),H(x)=F(x)G(x) \), which means the contribution of connected blocks with statistical size \ (I \) to the answer
Calculate the number of connected blocks of bipartite graph
Let the EGF of the number of bipartite coloring graphs with \ (n \) points be \ (f (x) \), and the EGF of the number of bipartite coloring graphs with \ (n \) points be \ (G(x) \)
Bipartite coloring graph is defined as coloring each point, and the same color points cannot be connected
Then there is \ (F(x)=G^2(x) \), which can be proved by considering the color of the smallest point in each binary connected block
have
\(\begin{aligned}F(x)&=\sum\limits_ix^i\sum\limits_{j=0}^i\frac{2^{(i-j)j}}{j!(i-j)!}\\&=\sum\limits_ix^i2^{\binom i2}\sum\limits_{j=0}^i \frac{2^{-\binom j2}}{j!}\frac{2^{-\binom {i-j}2}}{(i-j)!} \end{aligned}\)
Then you can find \ (F(x) \)
Let \ (H(x) \) be the EGF of the number of connected bipartite graphs with \ (n \) points
Then there are still \ (\ displaystyle G(x)=e^{H(x)},H(x)=\ln G(x)=\frac12\ln F(x) \)
Let the EGF of the number of graphs with \ (n \) points be \ (A(x) \)
Then, as above, the answer is \ (A(x)H(x) \)
Time complexity \ (O(n\log n) \)
Code#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int read()
{
int ret=0;bool f=0;char c=getchar();
while(c>'9'||c<'0')f|=(c=='-'),c=getchar();
while(c>='0'&&c<='9')ret=(ret<<3)+(ret<<1)+(c^48),c=getchar();
return f?-ret:ret;
}
const int mod=998244353;
const int maxn=1e5+5;
int n,a[maxn],mx,pow2[maxn],fac[maxn],ifac[maxn];
int qpow(int a,int b){int ret=1;for(;b;b>>=1,a=(ll)a*a%mod)if(b&1)ret=(ll)ret*a%mod;return ret;}
int R[1<<21],W[1<<21],inv[maxn];
void prework()
{
inv[1]=1;for(int i=2;i<=mx;i++)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
for(int i=0;i<=mx;i++)pow2[i]=qpow(2,((ll)i*(i-1)/2)%(mod-1));
fac[0]=1;for(int i=1;i<=mx;i++)fac[i]=(ll)fac[i-1]*i%mod;
ifac[0]=1;for(int i=1;i<=mx;i++)ifac[i]=(ll)ifac[i-1]*inv[i]%mod;
}
struct poly
{
vector<int>v;
int&operator[](const int &i){return v[i];}
void set(int l){v.resize(l);}
int len(){return v.size();}
void ntt(int L,int typ)
{
int n=1<<L;
for(int i=0;i<n;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
W[0]=1;W[1]=qpow(3,(mod-1)/n);if(typ==-1)W[1]=qpow(W[1],mod-2);
for(int i=2;i<n;i++)W[i]=(ll)W[i-1]*W[1]%mod;
set(n);
for(int i=0;i<n;i++)if(R[i]>i)swap(v[R[i]],v[i]);
for(int t=n>>1,d=1;d<n;d<<=1,t>>=1)
for(int i=0;i<n;i+=(d<<1))
for(int j=0;j<d;j++)
{
int tmp=(ll)W[t*j]*v[i+j+d]%mod;
v[i+j+d]=(v[i+j]-tmp+mod)%mod;
v[i+j]=(v[i+j]+tmp)%mod;
}
if(typ==-1){int inv=qpow(n,mod-2);for(int i=0;i<n;i++)v[i]=(ll)v[i]*inv%mod;}
}
void adjust(){while(len()>1&&v.back()==0)v.pop_back();}
poly operator *(poly &x)
{
poly ret,tmp0=*this,tmp1=x;
int L=ceil(log2(len()+x.len())),n=1<<L;
ntt(L,1);x.ntt(L,1);
ret.set(n);
for(int i=0;i<n;i++)ret[i]=(ll)v[i]*x[i]%mod;
ret.ntt(L,-1);ret.adjust();*this=tmp0;x=tmp1;return ret;
}
void operator *=(poly &x)
{
poly tmp=x;
int L=ceil(log2(len()+x.len())),n=1<<L;
ntt(L,1);x.ntt(L,1);
for(int i=0;i<n;i++)v[i]=(ll)v[i]*x[i]%mod;
ntt(L,-1);x=tmp;adjust();
}
void squ()
{
int L=ceil(log2(len()))+1,n=1<<L;
ntt(L,1);
for(int i=0;i<n;i++)v[i]=(ll)v[i]*v[i]%mod;
ntt(L,-1);adjust();
}
poly getinv(int deg=-1)
{
if(deg==-1)deg=len();
if(deg==1)return {{qpow(v[0],mod-2)}};
poly ret=getinv((deg+1)>>1);
int L=ceil(log2(deg))+1,n=1<<L;
poly tmp;tmp.set(deg);
for(int i=0;i<deg;i++)tmp[i]=v[i];
tmp.ntt(L,1);ret.ntt(L,1);
for(int i=0;i<n;i++)ret[i]=(ll)ret[i]*(2-(ll)tmp[i]*ret[i]%mod+mod)%mod;
ret.ntt(L,-1);ret.set(deg);return ret;
}
poly getln(int deg=-1)
{
if(deg==-1)deg=len();
poly ret,rev=getinv();
ret.set(deg);
for(int i=0;i+1<len();i++)ret[i]=(ll)v[i+1]*(i+1)%mod;
ret*=rev;
ret.set(deg);
for(int i=deg-1;i>=1;i--)ret[i]=(ll)ret[i-1]*inv[i]%mod;
ret[0]=0;
return ret;
}
};
int solve_independent_node()
{
int mul1=1,mul2=1;
for(int i=1;i<=n;i++)mul1=(ll)mul1*a[i]%mod;
for(int i=1;i<=n;i++)mul2=(ll)mul2*a[i]%mod*(1-qpow(inv[2],a[i]-1)+mod)%mod;
mul1=(mul1-mul2+mod)%mod;
for(int i=1;i<=n;i++)mul1=(ll)mul1*pow2[a[i]]%mod;
return mul1;
}
poly get_connnect_blocks()
{
poly graphnum;
graphnum.set(mx+1);
for(int i=0;i<=mx;i++)graphnum[i]=(ll)pow2[i]*ifac[i]%mod;
poly ln=graphnum.getln();
graphnum*=ln;
graphnum.set(mx+1);
return graphnum;
}
poly get_bipartie_connect_blocks()
{
poly graphnum;
graphnum.set(mx+1);
for(int i=0;i<=mx;i++)graphnum[i]=(ll)pow2[i]*ifac[i]%mod;
poly f;
f.set(mx+1);
for(int i=0;i<=mx;i++)f[i]=(ll)ifac[i]*qpow(pow2[i],mod-2)%mod;
f.squ();f.set(mx+1);
for(int i=0;i<=mx;i++)f[i]=(ll)f[i]*pow2[i]%mod;
f=f.getln();
for(int i=0;i<=mx;i++)f[i]=(ll)f[i]*inv[2]%mod;
graphnum*=f;
graphnum.set(mx+1);
return graphnum;
}
int solve_connected_block()
{
poly f=get_connnect_blocks(),g=get_bipartie_connect_blocks();
for(int i=1;i<=mx;i++)// substract independent nodes
{
f[i]=((ll)f[i]*fac[i]%mod-(ll)i*pow2[i-1]%mod+mod)%mod;
g[i]=((ll)g[i]*fac[i]%mod-(ll)i*pow2[i-1]%mod+mod)%mod;
}
int mul1=1,mul2=1;
for(int i=1;i<=n;i++)
{
mul1=(ll)mul1*(f[a[i]]+g[a[i]])%mod;
mul2=(ll)mul2*(f[a[i]]-g[a[i]]+mod)%mod;
}
return (ll)(mul1+mul2)*inv[2]%mod;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)mx=max(mx,a[i]=read());
prework();
printf("%d\n",(solve_independent_node()+solve_connected_block())%mod);
return 0;
}