2021杭电多校第7场1011Problem - 7054 (hdu.edu.cn)

题意：

给一个长度为 \(n\) 的序列 \(a\) ，对所有的 \(1\le b_i \le n,k\ge 1\)，求出

\(\prod\limits_{b_1<b_2<\cdots<b_k}(a_{b_1}+a_{b_2}+\cdots+a_{b_k})\)，对 \(998244353\) 取模

\(1\le n\le 10^5,0\le \sum a_i\le 10^5\)

思路：

令 \(cnt_x\) 为所有和为 \(x\) 的的子序列的个数，答案即为 \(\prod x^{cnt_x}\)

考虑如何去求 \(cnt_x\) 即为一道经典的01背包计数问题

将每个 \(a_i\) 放到多项式的系数上，使之转化为 \(1+x^{a_i}\) 全部乘起来后统计系数即为答案，这块可以分治FFT

注意 \(cnt_x\) 在指数上，需要欧拉降幂，即需要对 \(mod-1\) 取模，因此需要任意模数

照抄了题解任意模数以及分治FFT的模板

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N=262144,M=998244353;
const ld pi=acosl(-1);
namespace GTI
{
	char gc(void)
	{
		const int S=1<<17;
		static char buf[S],*s=buf,*t=buf;
		if (s==t) t=buf+fread(s=buf,1,S,stdin);
		if (s==t) return EOF;
		return *s++;
	}
	int gti(void)
	{
		int a=0,b=1,c=gc();
		for (;!isdigit(c);c=gc()) b^=(c=='-');
		for (;isdigit(c);c=gc()) a=a*10+c-'0';
		return b?a:-a;
	}
};
using GTI::gti;
int fpw(int a,int b)
{
	a%=M,b%=M-1;
	if (b<0) b+=M-1;
	int c=1;
	for (;b;b>>=1,a=1ll*a*a%M)
		if (b&1)
			c=1ll*c*a%M;
	return c;
}
namespace Poly
{
    const long double pi=acosl(-1);
    struct C
    {
        long double x,y;
        C():x(0),y(0){}
        C(long double a,long double b):x(a),y(b){}
        C operator+(const C &b){return C(x+b.x,y+b.y);}
        C operator-(const C &b){return C(x-b.x,y-b.y);}
        C operator*(const C &b){return C(x*b.x-y*b.y,x*b.y+y*b.x);}
        C operator/(long double b){return C(x/b,y/b);}
    };
    int id[N];
    int init(int n)
    {
        int ret=1;
        for (;1<<ret<n;ret++);
        for (int i=0;i<1<<ret;i++)
            id[i]=id[i>>1]>>1|((i&1)<<(ret-1));
        return 1<<ret;
    }
    C getwl(int x,int tag)
    {
        return C(cosl(2*pi/x),tag*sinl(2*pi/x));
    }
    void fft(C *a,int len,int tag=1)
    {
        for (int i=0;i<len;i++)
            if (id[i]>i)
                std::swap(a[i],a[id[i]]);
        for (int l=1;l<len;l<<=1)
        {
            C wl=getwl(l*2,tag);
            for (int st=0;st<len;st+=l<<1)
            {
                C w(1,0),tmp;
                for (int i=st;i<st+l;i++,w=w*wl)
                    tmp=a[i+l]*w,a[i+l]=a[i]-tmp,a[i]=a[i]+tmp;
            }
        }
        if (tag<0)
            for (int i=0;i<len;i++)
                a[i]=a[i]/len;
    }
    int mul(int *ret,int *a,int alen,int *b,int blen,int M)
    {
        static C c[N],d[N],e[N];
        int s=alen+blen-1,len=init(s);
        for (int i=0;i<alen;i++)
            c[i]=C(a[i]>>15,a[i]&0x7fff);
		std::fill(c+alen,c+len,C());
        for (int i=0;i<blen;i++)
            d[i]=C(b[i]>>15,b[i]&0x7fff);
		std::fill(d+blen,d+len,C());
        fft(c,len),fft(d,len);
        for (int i=0;i<len;i++)
        {
            int j=(len-i)&(len-1);
            e[i]=d[i]*C(0.5*(c[i].x+c[j].x),0.5*(c[i].y-c[j].y));
            d[i]=d[i]*C(0.5*(c[i].y+c[j].y),0.5*(c[j].x-c[i].x));
        }
        fft(e,len,-1),fft(d,len,-1);
        for (int i=0;i<s;i++)
        {
            ll x=roundl(e[i].x),y=roundl(e[i].y),z=roundl(d[i].x),w=roundl(d[i].y);
            ret[i]=(((x%M<<30)%M+((y+z)%M<<15)%M+w%M)%M+M)%M;
        }
        return s;
    }
}
int a[N<<1],tot,b[N<<1],c[N<<1];
struct P
{
	int *p,len;
	P()
	{
		p=NULL;
		len=0;
	}
	void init(int len)
	{
		p=a+tot;
		this->len=len;
		for (int i=0;i<len;i++)
			p[i]=0;
		++p[0],++p[len-1];
		tot+=len;
	}
	void mul(const P &b,int mod)
	{
		len=Poly::mul(p,p,len,b.p,b.len,mod);
	}
};
P solve(int l,int r,int mod)
{
	P ans;
	if(l==r)
	{
		ans.init(gti()+1);
	}
	else
	{
		int mid=(l+r)>>1;
		ans=solve(l,mid,mod);
		ans.mul(solve(mid+1,r,mod),mod);
	}
	return ans;
}
int main()
{
	int t;
	t=gti();
	while(t--)
	{
		int n,ans=1;tot=0;
		n=gti();
		P now=solve(1,n,M-1);
		if(now.p[0]>1)
		{
			printf("0\n");
		}
		else
		{
			for(int i=1;i<now.len;i++)
			ans=1ll*ans*fpw(i,now.p[i])%M;
			printf("%d\n",ans);
		}
	}
	return 0;
}