题面

在这里插入图片描述

题解

如果我们把这个 $w$ 定义为某一种距离的follow可连的边数，那么就很清楚了：对于所有 $1\leq i,j\leq n$ ， $i$ 向 $j$ 连有 $w_{i-j+n\mod n}$ 条有向边，而每个点向 0 号点连有 1 条有向边。求以 0 为根的内向生成树个数。

直接上矩阵树定理，由于最终求余子式，干脆就忽略 0 号点，那么答案就是
$\det\left[\begin{matrix} 1+\sum w & -w_1 & -w_2 &\cdots& -w_n\\ -w_n & 1+\sum w & -w_1 &\cdots& -w_{n-1}\\ -w_{n-1} & -w_{n} & 1+\sum w &\cdots& -w_{n-2}\\ \vdots & \vdots &\vdots & \ddots & \vdots\\ -w_1 & -w_2 & -w_3 & \cdots & 1+\sum w \end{matrix}\right]$

我们发现这是个循环矩阵。循环矩阵怎么求呢？

题解里用到了一个特殊的范德蒙矩阵 B =
$\left[\begin{matrix} 1 & 1 &\cdots& 1\\ ω_n^0 & ω_n^1 &\cdots& ω_n^{n-1}\\ \vdots & \vdots & \ddots & \vdots\\ ω_n^0 & ω_n^{1(n-1)} & \cdots & ω_n^{(n-1)(n-1)} \end{matrix}\right]$

然后若循环矩阵 A =
$\left[\begin{matrix} a_0 & a_1 &\cdots& a_{n-1}\\ a_{n-1} & a_0 &\cdots& a_{n-2}\\ \vdots & \vdots & \ddots & \vdots\\ a_1 & a_2 & \cdots & a_0 \end{matrix}\right]$

令函数 $f (x) =$
$a_0+a_1x+a_2x^2+...+a_{n-1}x^{n-1}$

那么把两个矩阵相乘，
$AB=\left[\begin{matrix} f(ω_n^0) & f(ω_n^1) &\cdots& f(ω_n^{n-1})\\ ω_n^0f(ω_n^0) & ω_n^1f(ω_n^1) &\cdots& ω_n^{n-1}f(ω_n^{n-1})\\ \vdots & \vdots & \ddots & \vdots\\ ω_n^0f(ω_n^0) & ω_n^{1(n-1)}f(ω_n^1) & \cdots & ω_n^{(n-1)(n-1)}f(ω_n^{n-1}) \end{matrix}\right]$

而这又刚好等于
$B\cdot\left[\begin{matrix} f(ω_n^0) & 0 & \cdots & 0\\ 0 & f(ω_n^1) & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \cdots & f(ω_n^{n-1}) \end{matrix}\right]$

于是算行列式
$\det(A)\cdot \det(B)=\det(B)\cdot \prod_{i=0}^{n-1}f(\omega_{n}^i)\\ \Rightarrow \det(A)=\prod_{i=0}^{n-1}f(\omega_{n}^i)$

在取模意义下，单位根可以用原根替代，

最为神奇的是，这道题 n 刚好是 2 的幂。

所以，我们对多项式 $(1+\sum w) -w_1x -w_2x^2-...-w_nx^{n}$ 进行一次 $N T T$ 正变换，再把每一位乘起来就得出答案。

时间复杂度 $O(n\log n)$ 。

CODE

#include<map>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 1048581
#define LL long long
#define DB double
#define lowbit(x) ((-x) & (x))
#define ENDL putchar('\n')
#define FI first
#define SE second
int xchar() {
    static const int mxn = 1000000;
    static char b[mxn];
    static int pos = 0,len = 0;
    if(pos == len) pos = 0,len = fread(b,1,mxn,stdin);
    if(pos == len) return -1;
    return b[pos ++];
}
//#define getchar() xchar()
LL read() {
    LL f=1,x=0;int s = getchar();
    while(s<'0' || s>'9') {if(s<0)return -1;if(s=='-')f=-f;s=getchar();}
    while(s>='0'&&s<='9') {x = (x<<3)+(x<<1)+(s^48);s = getchar();}
    return f*x;
}
void putpos(LL x) {
    if(!x) return ;
    putpos(x/10); putchar((x%10)^48);
}
void putnum(LL x) {
    if(!x) {putchar('0');return ;}
    if(x<0) putchar('-'),x=-x;
    return putpos(x);
}
void AIput(LL x,int c) {putnum(x);putchar(c);}

const int MOD = 998244353;
int n,m,s,o,k;
int w[MAXN];
int a[MAXN];
int qkpow(int a,int b) {
	int res = 1;
	while(b > 0) {
		if(b & 1) res = res *1ll* a % MOD;
		a = a*1ll*a % MOD; b >>= 1;
	}return res;
}
int xm[MAXN],om,rev[MAXN];
void NTT(int *s,int n) {
	for(int i = 1;i < n;i ++) {
		rev[i] = (rev[i>>1]>>1) | ((i&1) ? (n>>1):0);
		if(rev[i] < i) swap(s[rev[i]],s[i]);
	}
	om = qkpow(3,(MOD-1)/n); xm[0] = 1;
	for(int i = 1;i <= n;i ++) xm[i] = xm[i-1] *1ll* om % MOD;
	for(int k = 2,t = n>>1;k <= n;k <<= 1,t >>= 1) {
		for(int j = 0;j < n;j += k) {
			for(int i = j,l = 0;i < j+(k>>1);i ++,l += t) {
				int A = s[i],B = s[i+(k>>1)];
				s[i] = (A + B*1ll*xm[l] % MOD) % MOD;
				s[i+(k>>1)] = (A +MOD- B*1ll*xm[l]%MOD) % MOD;
			}
		}
	}return ;
}
int main() {
	freopen("federation.in","r",stdin);
	freopen("federation.out","w",stdout);
	k = read(); n = 1<<k;
	a[0] = 1;
	for(int i = 1;i < n;i ++) {
		w[i] = read();
		(a[0] += w[i]) %= MOD;
		a[i] = (MOD-w[i]) % MOD;
	}
	NTT(a,n);
	int ans = 1;
	for(int i = 0;i < n;i ++) {
		ans = ans *1ll* a[i] % MOD;
	}
	AIput(ans,'\n');
    return 0;
}