最新要闻

广告

手机

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

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

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

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

家电

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

【天天时快讯】HDU 6801 Game on a Circle 题解 (推式子，多项式)

来源：博客园


【资料图】

题目链接

首先注意到我们对这个环的扫描是一轮一轮进行的，每轮都会从左到右对每个没被删除的元素以p的概率删除。如果我们能对每个\(t(t\in [0,\infin],t是整数)和i\)求出c号点在第\(t+1\)轮被删掉，且是第i个被删除的元素，那么就能求出答案了。不幸的是我们不能枚举所有的t。但是不管怎么样先把式子列出来看看。

令\(f_i=\)最后i+1的答案，\(F(x)=\sum_{i=0}^{n-1}f_ix^i\)。我们要求出这个多项式(生成函数)F。

令\(p=\frac ab,q=1-p\)。我们现在枚举t，把F写成\(\sum_{t=0}^{\infin}\cdots\)的形式。c必须在第t+1轮被删掉发生的概率是\(pq^t\)。c前面的c-1个元素在c被删掉之前经理了t+1轮，每个点被删掉的概率为\(1-q^{t+1}\)，没被删掉的概率为\(q^{t+1}\)。c后面的n-c个元素在c被删掉之前经历了t轮，概率同理。所以\(F(x)=\sum_{t=0}^{\infin}pq^t\cdot(q^{t+1}+(1-q^{t+1})x)^{c-1}\cdot(q^t+(1-q^t)x)^{n-c}\)。这一步是核心思想，后面只要不断化简这个式子就行了。式子的化简并不是很难，用到的技巧也就是二项式定理啥的。

大量公式警告(其实都很容易看懂)

\[\begin{align}F(x)&=\sum_{t=0}^{\infin}pq^t\cdot(q^{t+1}+(1-q^{t+1})x)^{c-1}\cdot(q^t+(1-q^t)x)^{n-c}\\&=\sum_{t=0}^{\infin}pq^t\cdot (x+q^{t+1}(1-x))^{c-1}\cdot (x+q^t(1-x))^{n-c}\\&=\sum_{t=0}^{\infin}pq^t\cdot[\sum_{i=0}^{c-1}\binom{c-1}{i}x^iq^{(t+1)(c-1-i)}(1-x)^{c-1-i}]\cdot[\sum_{j=0}^{n-c}\binom{n-c}{j}x^j q^{t(n-c-i)}(1-x)^{n-c-i}]\ \ (二项式定理)\\&=p\sum_{i=0}^{c-1}\binom{c-1}{i}x^i\sum_{j=0}^{n-c}\binom{n-c}{j}x^j\cdot\sum_{t=0}^{\infin}q^{t(n-i-j)+c-1-i}\cdot(1-x)^{n-1-i-j}\ \ (交换sigma)\\&=p[\sum_{i=0}^{c-1}\binom{c-1}{i}x^iq^{c-1-i}\sum_{j=0}^{n-c}\binom{n-c}{j}x^j]\cdot[\sum_{t=0}^{\infin}q^{t(n-i-j)}]\cdot[(1-x)^{n-1-i-j}]\end{align}\]

上面最后一个式子除了最开头的一个p，其余部分用方括号分成了三部分(方括号仅仅用来划分式子，不表示运算顺序)。先用一次卷积求出第一部分两个sigma的乘积。注意到第二部分是一个等比数列，如果知道了i+j可以直接\(O(1)\)求出；而第一部分在枚举了i和j的情况下它们乘积的下标也是i+j，所以算出第一部分之后把前两部分做一个按位乘就行了。第三部分继续二项式定理展开，与前两部分的乘积再做一次卷积就得到最终结果\(F(x)\)了。

一共就做了两次卷积，总复杂度\(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){  if(x==0) return 0;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 NTT{  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)  {    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;  }}LL n,p,q,c,fac[1000010],inv[1000010];LL CC(LL nn,LL mm){return fac[nn]*inv[mm]%MOD*inv[nn-mm]%MOD;}int main(){  fileio();  fac[0]=1;repn(i,1000005) fac[i]=fac[i-1]*i%MOD;  rep(i,1000003) inv[i]=qpow(fac[i],MOD-2);  int T;  cin>>T;  while(T--)  {    LL a,b;    cin>>n>>a>>b>>c;    p=a*qpow(b,MOD-2)%MOD;    q=(MOD+1-p)%MOD;    vector  A,B,C;    rep(i,c) A.pb(CC(c-1,i)*qpow(q,c-1-i)%MOD);    rep(i,n-c+1) B.pb(CC(n-c,i));    C=NTT::convolution(A,B,3);    rep(i,C.size())    {      LL val=qpow((1-qpow(q,n-i)+MOD)%MOD,MOD-2);      (C[i]*=val)%=MOD;    }    A.clear();B.clear();    rep(i,C.size()) A.pb(C[i]*fac[n-1-i]%MOD);    rep(i,n)    {      LL val=inv[i];      if(i%2) val=(MOD-val)%MOD;      B.pb(val);    }    C=NTT::convolution(A,B,3);    rep(i,n) (C[i]*=inv[n-1-i])%=MOD;    rep(i,n) (C[i]*=p)%=MOD;    rep(i,n) printf("%lld\n",C[i]);  }  termin();}

关键词： 第一部分 二项式定理 等比数列