XJOI 操作

这题的式子好诡异啊！！！
差不多就是算一段乘积的一种期望，再搞一搞。
形式化地说，就是算
\[ \prod_{i=1}^n f_i(x) \sum_{i=1}^n \frac{b_i}{f_i(x)} \]
其中\(f_i(x)\)是关于\(x\)的多项式
直接维护两个多项式，分治FFT即可。

考虑另一个问题，给你一个数列a，
要求a的和，a的平方和，a的三次方和.......
做法1是根据\(ln\)的定义
\(ln(1-ax)=- \int \frac{a}{1-ax}\)
\(=- a \int \sum_{i=0}^{\infty}a^i x^i\)
\(=- a \sum_{i=1}^{\infty} \frac{a^{i-1}}{i} x^i\)
\(= - \sum_{i=1}^{\infty} \frac{a^i}{i} x^i\)

然后考虑求sigma，直接先分治FFT撑起来然后ln一下。

做法2考虑套用这题的做法，注意到式子的后半部分实际上是带系数的原问题，直接求个逆乘回去就行了。

纯属口胡，感觉不是很靠谱。
此题代码

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
const int M=998244353;
const int G=3;
namespace{
  int HALF(int x){
    return (x&1)?(x+M>>1):(x>>1);
  }
  int ADD(int x,int y){
    return (x+=y)>=M?x-M:x;
  }
  int SUB(int x,int y){
    return (x-=y)<0?x+M:x;
  }
  int MUL(int x,int y){
    return (ll)x*y%M;
  }
  int fp(int x,int y){
    int ret=1;
    for (; y; y>>=1,x=MUL(x,x)) if (y&1) ret=MUL(ret,x);
    return ret;
  }
  int fac[N],invfac[N];
  void precalc(int n){
    fac[0]=1;
    for (int i=1; i<=n; ++i) fac[i]=MUL(fac[i-1],i);
    invfac[n]=fp(fac[n],M-2);
    for (int i=n-1; i>=0; --i) invfac[i]=MUL(invfac[i+1],i+1);
  }
  int c(int x,int y){
    return MUL(MUL(fac[x],invfac[y]),invfac[x-y]);
  }
}
const int D=270000;
int a[D],b[D],rev[D],w[D];
void NTT(int *a,int n){
  for (int i=0; i<n; ++i) if (i>rev[i]) swap(a[i],a[rev[i]]);
  for (int i=1; i<n; i<<=1){
    w[0]=1;
    w[1]=fp(G,(M-1)/(i<<1));
    for (int j=2; j<i; ++j) w[j]=MUL(w[j-1],w[1]);
    for (int j=0; j<n; j+=(i<<1))
      for (int k=j; k<j+i; ++k){
    int x=a[k],y=MUL(a[k+i],w[k-j]);
    a[k]=ADD(x,y);
    a[k+i]=SUB(x,y);
      }
  }
}
void INTT(int *a,int n){
  reverse(a+1,a+n);
  NTT(a,n);
  int ni=fp(n,M-2);
  for (int i=0; i<n; ++i) a[i]=MUL(a[i],ni);
}
typedef vector<int> vi;
vi operator *(const vi &u,const vi &v){
  int len=1;
  for (; len<u.size()+v.size()-1; len<<=1);
  for (int i=1; i<len; ++i) rev[i]=rev[i>>1]>>1|(i&1?len>>1:0);
  for (int i=0; i<u.size(); ++i) a[i]=u[i];
  for (int i=u.size(); i<len; ++i) a[i]=0;
  for (int i=0; i<v.size(); ++i) b[i]=v[i];
  for (int i=v.size(); i<len; ++i) b[i]=0;
  NTT(a,len);
  NTT(b,len);
  for (int i=0; i<len; ++i) a[i]=MUL(a[i],b[i]);
  INTT(a,len);
  vi ret(u.size()+v.size()-1);
  for (int i=0; i<ret.size(); ++i) ret[i]=a[i];
  return ret;
}
vi operator +(const vi &u,const vi &v){
  vi ret(max(u.size(),v.size()));
  for (int i=0; i<ret.size(); ++i)
    ret[i]=ADD((i<u.size()?u[i]:0),(i<v.size()?v[i]:0));
  return ret;
}
void test(){
  vi a({1,2,1});
  a=a*vi({2,3,5,1,4});
  for (auto i:a) cerr<<i<<" ";
  cerr<<endl;
}
vi aa[N],bb[N];
int n;
int P[N],A[N],B[N];
 void ups(vi &v){
   v.clear();
   v.shrink_to_fit();
 }
void dfs(int l,int r){
  if (l==r){
    aa[l]={1,B[l]};
    bb[l]={A[l]};
    return;
  }
  int mid=(l+r)>>1;
  dfs(l,mid);
  dfs(mid+1,r);
  bb[l]=aa[l]*bb[mid+1]+bb[l]*aa[mid+1];
  aa[l]=aa[l]*aa[mid+1];
  ups(aa[mid+1]);
  ups(bb[mid+1]);
  //cerr<<"l r"<<l<<" "<<r<<endl;
  //for (auto i:bb[l]) cerr<<i<<" "; cerr<<endl;
  //exit(0);
}
int main(){
  //test();
  scanf("%d",&n);
  precalc(n);
  for (int i=1; i<=n; ++i){
    scanf("%d%d%d",&P[i],&A[i],&B[i]);
    A[i]=MUL(P[i],A[i]);
    B[i]=ADD(P[i],MUL(B[i],SUB(1,P[i])));
    //cerr<<A[i]<<" "<<B[i]<<endl;
  }
  dfs(1,n);
  int ans=0;
  for (int i=0; i<n; ++i){
    //cerr<<bb[1][i]<<",";
    ans=ADD(ans,MUL(MUL(fac[n-1-i],bb[1][i]),fac[i]));
  }
  //cerr<<endl;
  ans=MUL(ans,invfac[n]);
  cout<<ans;
}

XJOI 操作

原文：https://www.cnblogs.com/Yuhuger/p/10392784.html