最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

Atcoder Grand Contest AGC 060 D Same Descent Set 题解 (容斥，多项式)

来源：博客园


【资料图】

题目链接

计数技巧大杂烩，好题

先来定义一下"间隔"，间隔指的是两个相邻的数之间的大小关系，有两种状态，上坡和下坡，分别指的是\(p_ip_{i+1}\)。这题要求的就是长度为\(n\)的间隔序列相同的排列对(a,b)的个数。

先考虑这样一个问题：在间隔序列确定的情况下有多少不同的排列。也就是给出间隔集合\(S\)，要求\(S\)中间隔的值都为下坡，其他的都为上坡，这样的排列有多少个。可以使用容斥，令\(f_i\)表示集合i中的间隔的值任意取、其他的间隔必须取上坡的排列数，再乘上\((-1)^{|i|}\)。(\(f_i\)的求法后面再说) 则这个问题的答案为\((-1)^{|S|}\sum_{i\subseteq S}f_i\)。那么间隔序列为\(S\)的集合对数就是\(((-1)^{|S|}\sum_{i\subseteq S}f_i)^2=(\sum_{i\subseteq S}f_i)^2=\sum_{i,j\subseteq S}f_if_j\)。原问题的答案为\(\sum_S\sum_{i,j\subseteq S}f_if_j\)。

对于任意\(i,j\)，能取到\(f_if_j\)的贡献的\(S\)的数量是\(2^{n-1-|i|-|j|+w_{i,j}}\)，其中\(w_{i,j}\)表示集合i和j同为1的位数，也就是\(|i\&j|\)。则\(ans=\sum_{i,j} 2^{n-1-|i|-|j|+w_{i,j}}f_if_j=2^{n-1}\sum_{i,j}\frac{f_i}{2^{|i|}}\cdot \frac{f_j}{2^{|j|}}\cdot 2^{w_{i,j}}\)。(1)如果没有后面的那个\(2^{w_{i,j}}\)，其实只要算出\(f\)就能求出答案了。考虑用组合意义解决\(2^{w_{i,j}}\)。假设现在已经确定了间隔集合i和j。一个间隔集合其实是把排列切成了若干段，每个在集合中的间隔处都是一个切口。现在我们其实是把i和j表示的两个排列放在一起，令它们共有的切口位置集合为\(t\)，则如果我们对每个\(c\subseteq t\)都计入1的贡献，总贡献就是\(2^{w_{i,j}}\)。如果搞明白以上所有思想，到这里应该已经会写了。下面还是说一下实现方法。

令\(T\)表示一行i-1个间隔的全集，定义\(h_i=\sum_{j\subseteq T}\frac{f_j}{2^{|j|}}\)，这里的\(f_j\)排列数是长度为i的排列。那么我们可以把整个长度为n的排列切成一些段(切口的集合就是上面说的c集合)，令这些段的长度为\(l_1\cdots l_k\)，则此时的方案数是\(2^{n-1}n!\prod_{i=1}^k \frac{h_{l_i}}{l_i!}\prod_{i=1}^{k-1}\frac{(-1)^2}{2^2}=2^{n-1}(\frac 14)^{k-1}n!\prod_{i=1}^k \frac{h_{l_i}}{l_i!}\)，对于每种切口集合，直接把这个贡献到最终答案里即可。其中\(2^{n-1}\)是上面(1)式开头带的系数；\(n!和\frac{1}{l_i!}\)是个组合数，是用来把1~n分散到每一段里的；\(\prod_{i=1}^{k-1}\frac{(-1)^2}{2^2}\)是k-1个切口的系数。众所周知普通生成函数复合的组合意义是把序列分成若干段，每一段执行某种操作的方案总数，这同样适用于这题。这里内层的生成函数是\(h\)，外层的是\(\sum_i 1 \cdot x^i=\frac 1{1-x}\)，所以求出了h数组之后只需要用多项式求逆求出\(\frac 1{1-H(x)}\)就行了。当然用分治fft也不是不行，但是多一个log。

求\(h\)数组的过程也是类似的，对于\(h_i\)，我们其实是把一个长度为i的序列分成若干段，要求每一段构成一个上升序列，且相邻两端的分界线处有\((-1)\cdot 2\)的系数。同样用生成函数复合去搞即可。注意到先求h再求最终答案的过程其实用了两次组合数，其实改变一下h的定义就能只用一次。下面代码里也是这么写的。

时间复杂度\(O(nlogn)\)。

点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;const LL MOD=998244353;LL qpow(LL x,LL a){LL res=x,ret=1;while(a>0){if((a&1)==1) ret=ret*res%MOD;a>>=1;res=res*res%MOD;}return ret;}namespace poly{  vector  rev;  void ntt(vector  &a,LL G)  {    LL nn=a.size(),gn,g,x,y;vector  tmp=a;    rep(i,nn) a[i]=tmp[rev[i]];    for(int len=1;len convolution(vector  a,vector  b,LL G)  {    if(a.size()<=20&&b.size()<=20)    {      vector  ret(a.size()+b.size()-1,0);      rep(i,a.size()) rep(j,b.size()) (ret[i+j]+=a[i]*b[j])%=MOD;      return ret;    }    LL nn=1,bt=0,sv=a.size()+b.size()-1;while(nn>1]>>1)|((i&1)<<(bt-1));    }    ntt(a,G);ntt(b,G);    rep(i,nn) (a[i]*=b[i])%=MOD;    ntt(a,qpow(G,MOD-2));    while(a.size()>sv) a.pop_back();    LL inv=qpow(nn,MOD-2);    rep(i,a.size()) (a[i]*=inv)%=MOD;    return a;  }  vector  deriv(vector  a)  {    rep(i,(int)a.size()-1) a[i]=a[i+1]*(i+1)%MOD;a[a.size()-1]=0;    return a;  }  vector  integ(vector  a)  {    for(int i=a.size()-1;i>0;--i) a[i]=a[i-1]*qpow(i,MOD-2)%MOD;a[0]=0;    return a;  }  vector  inverse(vector  a,LL G)  {    if(a.size()==1) return vector {qpow(a[0],MOD-2)};    vector  aa=a;while(aa.size()>(a.size()+1)>>1) aa.pop_back();    vector  bb=inverse(aa,G);    LL nn=1,bt=0,sv=a.size();while(nn>1]>>1)|((i&1)<<(bt-1));    }    ntt(a,G);ntt(bb,G);    rep(i,nn) a[i]=(2LL-a[i]*bb[i]%MOD+MOD)*bb[i]%MOD;    ntt(a,qpow(G,MOD-2));    while(a.size()>sv) a.pop_back();    LL inv=qpow(nn,MOD-2);    rep(i,a.size()) (a[i]*=inv)%=MOD;    return a;  }  vector  sqrt1(vector  a,LL G)//常数项为1  {    if(a.size()==1) return vector {1};    vector  aa=a;while(aa.size()>(a.size()+1)>>1) aa.pop_back();    vector  bb=sqrt1(aa,G);while(bb.size() bbb=inverse(bb,G);    LL nn=1,bt=0,sv=a.size();while(nn>1]>>1)|((i&1)<<(bt-1));    }    LL mul=qpow(2,MOD-2);    ntt(a,G);ntt(bb,G);ntt(bbb,G);    rep(i,nn) a[i]=mul*(bb[i]+bbb[i]*a[i]%MOD)%MOD;    ntt(a,qpow(G,MOD-2));    while(a.size()>sv) a.pop_back();    LL inv=qpow(nn,MOD-2);    rep(i,a.size()) (a[i]*=inv)%=MOD;    return a;  }  vector  ln(vector  a,LL G)//求导，乘逆元，整体积分  {    int sz=a.size();    a=convolution(deriv(a),inverse(a,G),G);while(a.size()>sz) a.pop_back();    return integ(a);  }  vector  Exp(vector  a,LL G)//B(x)=B0(x)*(1-lnB0(x)+A(x)) 取ln前加长  {    if(a.size()==1) return vector {1};    LL nlen=(a.size()+1)>>1;vector  aa;    rep(i,nlen) aa.pb(a[i]);    vector  b0=Exp(aa,G);while(b0.size() lnb0=ln(b0,G),res;    rep(i,a.size()) res.pb((a[i]+MOD-lnb0[i]+(i==0))%MOD);    res=convolution(b0,res,3);while(res.size()>a.size()) res.pop_back();    return res;  }  vector  qpow1log(vector  a,LL k,LL G)//常数项!=0  {    a=ln(a,G);rep(i,a.size()) (a[i]*=k)%=MOD;    return Exp(a,G);  }  vector  qpow2log(vector  a,LL k,LL G)  {    if(k==0)    {      vector  ret;ret.pb(1);rep(i,a.size()-1) ret.pb(0);      return ret;    }    vector  ret;    LL sz=a.size();    while(k>0)    {      if(k&1)      {        if(ret.empty()) ret=a;        else{ret=convolution(ret,a,3);while(ret.size()>sz) ret.pop_back();}      }      a=convolution(a,a,3);while(a.size()>sz) a.pop_back();      k>>=1;    }    return ret;  }}LL n,fac[200010],inv[200010],h[200010];void calcH(){  vector  A;  A.pb(1);repn(i,n+3) A.pb((MOD-inv[i]*inv[2]%MOD)%MOD);  repn(i,A.size()-1) A[i]=(MOD-A[i])%MOD;  A=poly::inverse(A,3);  repn(i,n)  {    LL val=A[i]*(MOD-2)%MOD;    (val*=val)%=MOD;    h[i]=val;  }}LL calcAns(){  vector  A;  LL mul=qpow(4,MOD-2);  A.pb(1);repn(i,n) A.pb(h[i]*mul%MOD);  repn(i,A.size()-1) A[i]=(MOD-A[i])%MOD;  A=poly::inverse(A,3);  LL ret=A[n]*4%MOD;  return ret;}int main(){  fileio();  fac[0]=1;repn(i,200005) fac[i]=fac[i-1]*i%MOD;  rep(i,200003) inv[i]=qpow(fac[i],MOD-2);  cin>>n;  calcH();  LL ans=calcAns();  (ans*=fac[n]*fac[n]%MOD)%=MOD;  (ans*=qpow(2,n-1))%=MOD;  cout<

关键词： 生成函数 可以使用 这个问题