題解：

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; }

　　

轉載于:https://www.cnblogs.com/clrs97/p/9064630.html

總結

以上是生活随笔為你收集整理的SDOI2018：荣誉称号的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。