题解：P12405 「CZOI-R3」星光闪耀

· · 题解

Let a_{j,x}=|\{i:S_{j,i}=x\}| where S_j denotes S_0 after j operations. Let b_{j,x}=a_{j,n-x}. Then the initial state is b_{0,0}=a_{0,n}=1 and the jth operation can be expressed as \forall x=1,2,\dots,n: b_{j,x}\gets \sum_{t=0}^x b_{j-1,t} \space (a_{j,x} \gets \sum_{t=x}^n a_{j-1,t}). The final answer is obviously \sum_{x=1}^n a_{m,x} k^x.

Let B_j(z)=\sum_{k\geqslant 0}b_{j,k} z^k. Then B_0(z)=1 and B_j(z)=\frac{1}{1-z} B_{j-1}(z). Thus B_j(z)=(1-z)^{-j}=\sum_{k\geqslant 0}\binom{k+j-1}{j-1}z^k \implies a_{m,x}=b_{m,n-x}=\binom{m'+n-x}{m'} where m'=m-1.

Denote the final answer as S_{m'}=\sum_{x=1}^n \binom{m'+n-x}{m'} k^x. Let S_j=\sum_{x=1}^n \binom{j+n-x}{j} k^x=k^n \sum_{x=0}^{n-1} \binom{j+x}{j} k^{-x}=k^n s_j(\frac{1}{k}). Then

s_j(t)&=\sum_{x=0}^{n-1} \binom{j+x}{j} t^x\\ &=\sum_{x=0}^{n-1} \left(\binom{j+x-1}{j}+\binom{j+x-1}{j-1}\right) t^x\\ &=t\sum_{x=-1}^{n-2} \binom{j+x}{j} t^x + s_{j-1}(t)\\ &=t s_j(t) - \binom{j+n-1}{j} t^n+ s_{j-1}(t)\\ s_j(t)&=\frac{s_{j-1}(t)-\binom{j+n-1}{j} t^n}{1-t}\quad(t\neq 1) \end{aligned}

and s_0(t)=\sum_{x=0}^{n-1}t^x=\frac{1-t^n}{1-t}\space(t\neq 1). If t=1 then k=1 and S_{m'}=\sum_{x=0}^{n-1} \binom{m'+x}{m'}=\frac{n}{m}\binom{m'+n}{n}. A direct implementation of this with proper precalculation can achieve a time complexity of O(n+\sum m).

#include<bits/stdc++.h>
using I=uint64_t;
template<class T>using V=std::vector<T>;
template<class T,I N>using A=std::array<T,N>;
int main(){
  const I P=998244353;
  A<I,10+(I)4e6>inv,fac,finv;
  fac[0]=finv[0]=fac[1]=finv[1]=inv[1]=1;
  for(I i=2;i<inv.size();i++){
    inv[i]=(P-P/i)*inv[P%i]%P;
    fac[i]=i*fac[i-1]%P;
    finv[i]=inv[i]*finv[i-1]%P;
  }

  auto C=[&](I n,I k){return fac[n]*finv[k]%P*finv[n-k]%P;};
  auto pw=[&](I x,I y){I w=1;for(;y;x=x*x%P,y>>=1)if(y&1)w=w*x%P;return w;};

  auto solve=[&](){
    I n,m,k;std::cin>>n>>m>>k;m--;
    if(k==0){std::cout<<"0\n";return;}
    if(k==1){std::cout<<n*C(m+n,m)%P*inv[m+1]%P<<'\n';return;}
    I v=pw(k,P-2);  

    I vn=pw(v,n),vv=pw(1-v+P,P-2);
    I w=(1-pw(v,n)+P)%P*vv%P;
    for(I i=1;i<=m;i++)w=(w-C(i+n-1,i)*vn%P+P)*vv%P;
    w=w*pw(k,n)%P;
    std::cout<<w<<'\n';
  };

  std::cin.tie(0)->sync_with_stdio(0);
  I t;std::cin>>t;while(t--)solve();
  return 0;
}

After the contest, many have claimed that they had easily simplified the expression of the final answer. As my solution is quite complicated, I wonder what simple solutions they had thought of.