题面
https://atcoder.jp/contests/agc034/tasks/agc034_f
题解
前置知识
首先设得到i的期望步数为E[i]。容易看出E[0]=0以及对i>0，(E[i]=sum_{j=0}^{2^n-1}p[j]E[i igoplus j]+1)。
将1移到左边，可以得到(E[i]-1=sum_{j=0}^{2^n-1}p[j]E[i igoplus j])。①
发现这个式子很像一个异或卷积，它可以描述为三个数组之间的关系：
其中(igoplus)表示两个数列之间的异或卷积。?的存在是因为E[0]并不满足①式。不过没关系，我们可以算出?是什么。中间的p数组满足一个性质——它们的和是1。所以，左边所有数的和一定等于右边所有数的和。所以(?=2^n-1)。
之后，我们将中间数组的第一项-=1，就可以完美地消掉右边的E：
看上去我们已经做完了，因为中间和右边的数组都已知，求左边还不容易吗？只需要把右边进行FWT，再与中间FWT后的结果的逆元逐项相乘，再UFWT就是左边了。
问题就出在“逆元”上。
0是没有逆元的，而我们仔细思考，发现中间FWT以后，是会出现0的！出现0的就是第一项，这一项在FWT以后会变成(p[0]-1+p[1]+…+p[2^n-1])，也就是0。其他项可以证明不是0。核对右边的第一项，FWT以后变成(2^n-1-1-1…-1)也是0。感觉我们少了个条件，做不下去了。
并不是！其实E中也有一项已知的，就是(E[0]=0)。它可是有巨大的用途的。根据我们的推导，({{}E[0],E[1],…,E[2^n-1]{}})FWT以后的结果是({{}q[0],q[1],…,q[2^n-1]{}})，这个q的1到(2^n-1)都已知了，只有q[0]未知。左边是E[0]已知，其他未知。根据异或卷积的公式，一定存在下列关系
其中(q^{(i)}[j])表示FWT中进行第i轮循环时，q[j]的值。由于(q^{(1)}[2^0],q^{(2)}[2^1]，…,q^{(n)}[2^{n-1}])这些值都与q[0]线性无关，所以简化为
这个M极其繁琐，怎么求？
强行代q[0]=0，算一个UFWT，算出来(E[0]=k)。这代表了(frac{0}{2^n}+M=k)，M自然求出。
至此，q[0]求出，本题结束。总时间复杂度(O(n2^n))。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register
#define In inline
const int N = 262144;
const ll mod = 998244353;
const ll iv2 = 499122177;
In ll read(){
ll s = 0,ww = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')ww = -1;ch = getchar();}
while('0' <= ch && ch <= '9'){s = 10 * s + ch - '0';ch = getchar();}
return s * ww;
}
In void write(ll x){
if(x < 0)putchar('-'),x = -x;
if(x > 9)write(x / 10);
putchar('0' + x % 10);
}
namespace ModCalc{
In void Inc(ll &x,ll y){
x += y;if(x >= mod)x -= mod;
}
In void Dec(ll &x,ll y){
x -= y;if(x < 0)x += mod;
}
In ll Add(ll x,ll y){
Inc(x,y);return x;
}
In ll Sub(ll x,ll y){
Dec(x,y);return x;
}
}
using namespace ModCalc;
In ll power(ll a,ll n){
ll s = 1,x = a;
while(n){
if(n & 1)s = s * x % mod;
x = x * x % mod;
n >>= 1;
}
return s;
}
ll n,deg;
ll p[N+5],q[N+5],temp[N+5];
In void calc(ll &x,ll &y,int opt){
if(opt == 1){
ll X = Add(x,y),Y = Sub(x,y);
x = X,y = Y;
}
else{
ll X = Add(x,y) * iv2 % mod,Y = Sub(x,y) * iv2 % mod;
x = X,y = Y;
}
}
void FWT(ll a[],ll deg,int opt){
for(rg int n = 2;n <= deg;n <<= 1){
int m = n >> 1;
for(rg int i = 0;i < deg;i += n){
for(rg int j = 0;j < m;j++)calc(a[i+j],a[i+j+m],opt);
}
}
}
int main(){
n = read();
deg = 1ll << n;
ll s = 0;
for(rg int i = 0;i < deg;i++)p[i] = read(),s += p[i];
ll iv = power(s,mod - 2);
for(rg int i = 0;i < deg;i++)p[i] = p[i] * iv % mod;
Dec(p[0],1);
FWT(p,deg,1);
for(rg int i = 0;i < deg;i++)q[i] = (i == 0 ? deg - 1 : -1);
FWT(q,deg,1);
for(rg int i = 1;i < deg;i++)q[i] = q[i] * power(p[i],mod - 2) % mod;
memcpy(temp,q,sizeof(temp));
FWT(temp,deg,-1);
Dec(q[0],temp[0] * deg % mod);
FWT(q,deg,-1);
for(rg int i = 0;i < deg;i++)write(q[i]),putchar('
');
return 0;
}