P5472 [noi2019] douzhudi (expectation, Mathematics)

Preface

Why didn't I even type my watch .
too vegetable.

analysis

The shuffle form given by the title doesn't look good , Reasonable guess can find , In fact, this is equivalent to all possible situations with equal probability .
And then it won't
You can find out by typing your watch ： When tp=1 when ,dp An array is a sequence of arithmetical numbers . When tp=2 when ,dp The difference of an array is an equal difference sequence .

Further speculation ： If the original dp An array is i Sub polynomial , Then after the shuffle, or $i$ Sub polynomial .
However, I can't prove

With this conclusion , Keep maintaining the coefficients of this polynomial that is not more than quadratic .

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("line: %d\n",__LINE__)

inline ll read(){
    
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)) {
    if(c=='-')f=-1;c=getchar();}
  while(isdigit(c)) {
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}
bool mem1;

const int N=1e7+100;
const int inf=1e9+100;
const int mod=998244353;
const bool Flag=0;

#define add(x,y) ((((x)+=(y))>=mod)&&((x)-=mod))
inline ll ksm(ll x,ll k){
    
  ll res(1);
  while(k){
    
    if(k&1) res=res*x%mod;
    x=x*x%mod;
    k>>=1;
  }
  return res;
}

int n,m;

ll a,b,c;
inline ll calc(ll x){
    return (x*x%mod*a+b*x+c)%mod;}

bool mem2;
signed main(){
    
#ifndef ONLINE_JUDGE
  freopen("a.in","r",stdin);
  freopen("a.out","w",stdout);
#endif
  debug("mem=%lf\n",abs(&mem2-&mem1)/1024./1024);
  n=read();m=read();int tp=read();
  //n=1e7;m=5e5;int tp=2;
  a=tp==2;b=tp==1;c=0;
  ll niv1=ksm((1ll*n*n-1-3*(n-1))%mod,mod-2);
  ll nin=ksm(n,mod-2),nin1=ksm(n-1,mod-2);
  for(int i=1;i<=m;i++){
    
    int A=read();
    //int A=rand()%n+1;
    ll f1=calc(1),f2=calc(2),fa=calc(A),fa1=calc(A+1),fa2=calc(A+2),fn=calc(n);
    ll x=(A*f1+(n-A)%mod*fa1)%mod*nin%mod;
    ll y=(A*((A-1)*f2%mod+(n-A)*fa1%mod)+(n-A)*(A*f1%mod+(n-A-1)*fa2%mod))%mod*nin%mod*nin1%mod;
    ll z=(A*fa+(n-A)*fn)%mod*nin%mod;
    //printf("x=%lld y=%lld z=%lld\n",x,y,z);
    a=(z-x-(n-1)*(y+mod-x)%mod+mod+mod)%mod*niv1%mod;
    b=(y-x-3*a%mod+mod+mod)%mod;
    c=(x-a-b+mod+mod)%mod;
  }
  int ask=read();
  while(ask--){
    
    printf("%lld\n",calc(read()));
  }
  
  return 0;
}