题解 P4389 【付公主的背包】

command_block · 2019-05-23 23:19:04 · 题解

前置芝士：NTT与多项式全家桶+生成函数OGF+(无标号计数)

这道题好像是WC2019讲义上的经典例题?

大家都直接OGF然后丢式子,我觉得不太友好,实际上这是一道Euler无标号计数的模板题。

先讲一讲这题为啥是无标号计数。

设C[i]为大小为i的物品个数,相当于我们有C[i]种方案得到一个大小为i的元素。

随后,我们要选取若干个元素使得他们的大小和为m,元素之间无顺序之分。

这不就是背包问题吗?所以背包问题是最经典的无标号计数。

EGF的 \exp

大家都知道,如果是有标号计数,选用EGF的话:

我们得到了单个元素的EGF,只要EXP一下就能得到这些元素生成的集合的EGF,这个可以泰勒展开然后观察式子。

有\exp(F(x))=\sum\limits_{i=0}\dfrac{F(x)^i}{i!}

注意\dfrac{F(x)^i}{i!}的意义 : 选择i个元素映射到标号上,但他们之间没有关联,顺序不用考虑。

现在是无标号计数,我们自然也想要优美的变换啦。

无标号计数中,如果两个元素大小相同且内部相同,则无法区分。

也就是说,我们考虑单独的F[i],其贡献为 : (1+x^i+x^{2i}+...)^{F[i]}

意思就是对大小为i的每种方案分别建立OGF然后乘起来。

我们就得到了Euler变换:

Euler(F(x))=\prod\limits_{i=0}\Big(\dfrac{1}{1-x^i}\Big)^{F[i]}

那么问题来了,怎么计算这个东西?

容易想到 \ln 之后变为加法,再 \exp ,则有:

\exp\sum\limits_{i=0}\ln\Big(\dfrac{1}{1-x^i}\Big)^{F[i]}

\ln\Big(\dfrac{1}{1-x^p}\Big)^{c}
考虑\ln(x^c)=c·\ln x,次数c我们就暂且按下不表。

先来搞\frac{1}{1-x},这东西的展开是\{1,1,1,1,1...\}

众所周知 \ln A(x)=∫(\frac{A'(x)}{A(x)})

先对这东西求导,得到\{1,2,3,4,5...\}=\dfrac{1}{(1-x)^2}

然后求逆,是1-x,乘在一起又回到了\frac{1}{1-x}

然后是积分,得到\{0,1,\frac{1}{2},\frac{1}{3},\frac{1}{4},...\}

也就是\ln \frac{1}{1-x}=\sum\limits_{i=1}\dfrac{x}{i}

现在用x^p替换x得到\ln \frac{1}{1-x^p}=\sum\limits_{i=1}\dfrac{x^{ip}}{i}

在\!\pmod{x^n}下也就n/p个有效项。

给出一个比较方便化简的中间结果 : Euler(F(x))=\exp\sum\limits_{i=0}-F[i]*\ln(1-x^i)

对于每个p暴力求和复杂度是O(\sum_{i=1}^n\frac{n}{i})=O(nlogn)的,随后EXP即可。

这题就是直接计算Euler(C(x)),非常的模板啊。

Code:

// luogu-judger-enable-o2
#include<algorithm>
#include<cstdio>
#define mod 998244353
#define G 3
#define Maxn 100500
using namespace std;
inline int read()
{
  register int X=0;
  register char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
int n,m,r[Maxn<<2],invn,invG;
long long powM(long long a,long long t=mod-2)
{
  long long ans=1,buf=a;
  while(t){
    if(t&1)ans=(ans*buf)%mod;
    buf=(buf*buf)%mod;
    t>>=1;
  }return ans;
}
void NTT(long long *f,int n,short op)
{
  for (int i=0;i<n;i++)
   if (r[i]<i)swap(f[r[i]],f[i]);
  for (int p=2;p<=n;p<<=1){
    int len=p>>1,
        w=powM(op==1 ?G:invG,(mod-1)/p);
    for (int k=0;k<n;k+=p){
      long long buf=1;
      for (int i=k;i<k+len;i++){
        int sav=f[len+i]*buf%mod;
        f[len+i]=(f[i]-sav+mod)%mod;
        f[i]=(f[i]+sav)%mod;
        buf=buf*w%mod;
      }
    }
  }
}
long long _g[Maxn<<2];
void times(long long *f,long long *gg,int len1,int len2,int limit)
{
  int n=1;
  for(;n<len1+len2;n<<=1);
  long long *g=_g;
  for (int i=0;i<len2;i++)g[i]=gg[i];
  for (int i=len2;i<n;i++)g[i]=0;
  invn=powM(n);
  for(int i=0;i<n;i++)
   r[i]=(r[i>>1]>>1)|((i&1)?n>>1:0);
  NTT(f,n,1);NTT(g,n,1);
  for(int i=0;i<n;++i)f[i]=(f[i]*g[i])%mod;
  NTT(f,n,-1);
  for(int i=0;i<limit;++i)f[i]=f[i]*invn%mod;
  for(int i=limit;i<n;++i)f[i]=0;
}
long long _r[Maxn<<2],_rr[Maxn<<2];
void invp(long long *f,int plen)
{
  long long *r=_r,*rr=_rr;
  int n=1;for(;n<plen;n<<=1);
  rr[0]=powM(f[0]);
  for (int len=2;len<=n;len<<=1){
    for (int i=0;i<len;i++)
      r[i]=rr[i]*2%mod;
    times(rr,rr,len/2,len/2,len);
    times(rr,f,len,len,len);
    for (int i=0;i<len;i++)
      rr[i]=(r[i]-rr[i]+mod)%mod;
  }for (int i=0;i<plen;i++)
    f[i]=rr[i];
  for (int i=0;i<n;i++)rr[i]=r[i]=0;
}
void dao(long long *f,int m)
{
  for (int i=1;i<m;i++)
   f[i-1]=f[i]*i%mod;
  f[m-1]=0;
}
void jifen(long long *f,int m)
{
  for (int i=m;i;i--)
   f[i]=f[i-1]*powM(i)%mod;
  f[0]=0;
}
long long _lns[Maxn<<2];
void lnp(long long *f,int m)
{
  long long *sav=_lns;
  for (int i=0;i<m;i++)sav[i]=f[i];
  invp(sav,m);dao(f,m);
  times(f,sav,m-1,m,m);
  jifen(f,m-1);
  for (int i=0;i<m;i++)sav[i]=0;
}
long long _xp[Maxn<<2],_xp2[Maxn<<2];
void exp(long long *f,int m)
{
  long long *s=_xp,*ss=_xp2;
  int n=1;for(;n<m;n<<=1);
  ss[0]=1;
  for (int len=2;len<=n;len<<=1){
    for (int i=0;i<len/2;i++)s[i]=ss[i];
    for (int i=len/2;i<len;i++)s[i]=0;
    lnp(s,len);
    for (int i=0;i<len;i++)
     s[i]=(f[i]-s[i]+mod)%mod;
    s[0]=(s[0]+1)%mod;
    times(ss,s,len/2,len,len);
  }for (int i=0;i<m;i++)f[i]=ss[i];
  for (int i=0;i<n;i++)s[i]=ss[i]=0;
}
long long f[Maxn<<2],inv[Maxn];
int c[Maxn];
int main()
{
  invG=powM(G);
  scanf("%d%d",&n,&m);m++;
  for (int i=0;i<n;i++)c[read()]++;
  inv[0]=inv[1]=1;
  for (int i=2;i<m;i++)
    inv[i]=(mod-mod/i)*inv[mod%i]%mod;
  for (int i=0;i<m;i++)
   if (c[i])
    for (int j=i;j<m;j+=i)
     f[j]=(f[j]+inv[j/i]*c[i])%mod;
  exp(f,m);
  for (int i=1;i<m;i++)
    printf("%lld\n",f[i]);
  return 0;
}

附 : Eular(F(x))=\exp\bigg(\sum\limits_{i=1}\dfrac{F(x^i)}{i}\bigg)

其实就是这道题的正解人话换成了公式。

Eular(F(x))=\exp\sum\limits_{i=0}\ln\Big(\dfrac{1}{1-x^i}\Big)^{F[i]}

=\exp\sum\limits_{i=0}F[i]\sum\limits_{j=1}\dfrac{x^{ij}}{j}

=\exp\sum\limits_{j=1}\frac{1}{j}\sum\limits_{i=0}F[i]x^{ij}

=\exp\bigg(\sum\limits_{i=1}\frac{F(x^i)}{i}\bigg)

更多技巧请见Link