SDOI2018：荣誉称号

题解：

https://files.cnblogs.com/files/clrs97/title-solution.pdf

Code：

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=2100,M=205,BUF=15000000;

const ll inf=1LL<<60;

unsigned int SA,SB,SC;

int Case,p,A,B,n,K,m,i,j,x,y,lim,d[N];

ll sum[N],w[N][M],f[N][M];

char Buf[BUF],*buf=Buf;

inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}

inline void read(unsigned int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}

inline unsigned int rng61(){

  SA^=SA<<16;

  SA^=SA>>5;

  SA^=SA<<1;

  unsigned int t=SA;

  SA=SB;

  SB=SC;

  SC^=t^SA;

  return SC;

}

inline void input(int x,int A,int B){

  while((x>>j)>lim)j+=K;

  x>>=j;

  A%=m;

  sum[x]+=B;

  w[x][0]+=(m-A)*B;

  w[x][A]-=m*B;

}

inline void up(ll&a,ll b){a>b?(a=b):0;}

void dfs(int x){

  int l=x<<1,r=x<<1|1,i,j;

  if(l>lim){

    for(i=0;i<m;i++)f[x][i]=w[x][i];

    return;

  }

  for(i=0;i<m;i++)f[x][i]=inf;

  dfs(l);

  if(r>lim||d[l]!=d[r]){

    for(i=0;i<m;i++)for(j=0;j<m;j++)up(f[x][(i+j)%m],w[x][i]+f[l][j]);

    return;

  }

  dfs(r);

  for(i=0;i<m;i++)for(j=0;j<m;j++)up(f[x][(i+j)%m],w[x][i]+f[l][j]+f[r][j]);

}

void solve(){

  read(n),read(K),read(m),read(p),read(SA),read(SB),read(SC),read(A),read(B);

  K++;

  lim=min((1<<K)-1,n);

  for(i=1;i<=lim;i++){

    sum[i]=0;

    for(j=0;j<m;j++)w[i][j]=0;

  }

  for(i=1,j=0;i<=p;i++){

    read(x),read(y);

    input(i,x,y);

  }

  for(i=p+1;i<=n;i++){

    x=rng61()%A+1;

    y=rng61()%B+1;

    input(i,x,y);

  }

  for(i=1;i<=lim;i++){

    for(j=1;j<m;j++)w[i][j]+=w[i][j-1];

    for(j=1;j<m;j++)w[i][j]+=sum[i]*j;

  }

  for(i=lim;i;i--){

    d[i]=0;

    if((i<<1)<=lim)d[i]=d[i<<1];

    d[i]++;

  }

  dfs(1);

  printf("%lld\n",f[1][0]);

}

int main(){

  fread(Buf,1,BUF,stdin);

  read(Case);

  while(Case--)solve();

  return 0;

}