最新要闻

广告

手机

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

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

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

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

家电

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

LOJ 3395 集训队作业 Yet Another Permutation Problem 题解 (生成函数技巧)

来源：博客园


(资料图片)

题目链接

原排列进行k次操作后，一定会剩下一个长度至少为\(n-k\)的上升区间。观察发现，一个排列能用\(\le k\)次操作得到的充要条件是：其中的最长上升区间长度\(\ge n-k\)。

我们枚举k，对每个k计算答案。最长上升区间长度\(\ge n-k\)的排列个数不太好算，我们可以算出最长上升区间长度\(\le n-k-1\)的排列个数，然后用总数减。为了方便，接下来的\(k\)表示上面的\(n-k-1\)。

我们先把序列划分成一些段，要求每一段都是单调递增，且每段长度\(\le k\)，求总方案数(我知道会重复计数，但你先别急)。这是一个经典的生成函数计数题。令\(f_i\)表示i个不同元素排成上升序列的方案数，显然\(f_i=1(i\le k)\)，为了方便使用生成函数，我们令\(f_0=0\)。令\(F(x)\)为f的指数型生成函数，\(G(x)\)为f的普通生成函数。\(F(x)=\sum_{i=1}^k \frac{x^i}{i!}\)，\(G(x)=\sum_{i=1}^k x^i\)。根据EGF的组合意义，这个问题的答案为：\(([x^n]\sum_{i=0}^\infin F^i(x))\cdot n!\)，其中\([x^n]\)表示这个多项式的n次项系数。

再来看看这个问题与原问题的关系。原问题中每个排列在这个问题中都被计数了多次。具体来说，对于一个排列，我们先把他划分成若干极长的上升区间，令它们的长度从左到右为\(l_1\cdots l_m\)。这个排列在这个问题中其实被计数了这么多次：\(\prod_{i=1}^m ([x^{l_i}]\sum_{j=0}^\infin G^j(x))\)，从组合意义的角度这个式子也非常好理解。那么我们希望这个排列被计数多少次呢？其实是\(\prod_{i=1}^m [l_i\le k]\)次。如果我们能适当地修改f数组，使得对于任意\(l\)，\([x^{l}]\sum_{i=0}^\infin G^i(x)=[l\le k]\)，那么只要按照这个问题的流程跑一遍，就得到原问题的答案了。这其实是可以做到的。

\[\begin{align}[x^{l}]\sum_{i=0}^\infin G^i(x)&=[l\le k]\\\sum_{i=0}^\infin G^i(x)&=\sum_{i=0}^k x^i\\\frac 1{1-G(x)}&=\frac{1-x^{k+1}}{1-x}\\G(x)&=\frac{x-x^{k+1}}{1-x^{k+1}}\\\end{align}\]

如果能求出\(G(x)\)，也就确定了f，也就能求出\(F(x)\)从而求出答案了。这里似乎可以用多项式求逆，但是模数不是998244353所以会有问题。写任意模NTT的话常数又似乎太大了。我们来观察一下暴力多项式求逆的过程，看看能不能投机取巧：

\[\begin{align}令b为多&项式a的逆\\b_0&=\frac 1{a_0}\\b_i&=\frac{-\sum_{j=0}^{i-1}b_ja_{i-j}}{a_0}\\\end{align}\]

为了避免混淆，重申一下"多项式求逆"的含义：对于一个多项式\(A(x)\)，求出一个多项式\(B(x)\)，使得\(A,B\)乘积的常数项为1，且1次项到\(n\)次项的系数都为0，更高次项的系数不管。

观察上面的暴力，发现其复杂度与\(a\)中不为0的项的数量有关(求那个sigma的时候可以只枚举a中不为0的项)。在求\(G(x)\)的过程中我们要给\(1-x^{k+1}\)求逆，打表(划掉)手画(划掉)观察一下发现\(1-x^{k+1}\)的逆中只有大约\(\frac nk\)项不为0，所以\(G(x),F(x)\)中不为0的项数也差不多是这个数量级。这部分的复杂度是\(O(n^2)\)(算上之前枚举k)。

然后是求出\(F(x)\)之后计算答案。我们需要计算\(\sum_{i=0}^\infin F^i(x)=\frac 1{1-F(x)}\)这个多项式。对\(1-F(x)\)求逆时，由于其中非0项的个数是\(\frac nk\)级别，求逆的复杂度是\(O(\frac {n^2}k)\)的。算上枚举\(k\)，总复杂度是\(O(n^2logn)\)的。

点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define pb push_back#define mpr make_pairusing namespace std;void 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);}LL n,MOD,fac[1010],inv[1010];LL qpow(LL x,LL a){LL res=x,ret=1;while(a>0){if(a&1) (ret*=res)%=MOD;a>>=1;(res*=res)%=MOD;}return ret;}vector  getInv(vector  A){  vector  v;  rep(i,A.size()) if(A[i]!=0) v.pb(mpr(i,A[i]));  vector  ret;  ret.pb(qpow(A[0],MOD-2));  repn(i,A.size()-1)  {    LL hv=0;    rep(j,v.size())    {      if(v[j].fi>i) break;      if(i-v[j].fi polyMul(vector  A,LL mns){  vector  ret;ret.pb(0);rep(i,A.size()-1) ret.pb(A[i]);  LL mul=MOD-1;  rep(i,A.size()) if(i+mns A;  A.pb(1);repn(i,k) A.pb(0);A.pb(MOD-1);while(A.size() B=getInv(A);  vector  F=polyMul(B,k+1);  rep(i,F.size()) (F[i]*=inv[i])%=MOD;  rep(i,F.size()) F[i]=(MOD-F[i])%MOD;  (++F[0])%=MOD;  F=getInv(F);  LL ret=F[n]*fac[n]%MOD;  return ret;}int main(){  fileio();    cin>>n>>MOD;  fac[0]=1;repn(i,1005) fac[i]=fac[i-1]*i%MOD;  rep(i,1003) inv[i]=qpow(fac[i],MOD-2);  rep(nk,n)  {    LL k=n-nk-1;    //答案=总数-所有上升子段的长度都<=k的排列数量    LL ans=(fac[n]-calc(k)+MOD)%MOD;    printf("%lld\n",ans);  }  termin();}

关键词： 生成函数 这个问题 看看这个