题目
题解
可以发现题目中给定的是个完全二叉树的形式，然后题目给定的限制可以转换成树上每一条长度为$k+1$的链$a$值和$\%m=0$
发现深度为$x(x> k+1)$的点的值$a_1$与它深度为$x-k-1$祖先的值$a_2$满足$a_1\equiv a_2(\bmod m)$，这样只用确定前$k+1$层的值即可，把下面的信息都压到前 $k+1$层即可
处理出点$t$的$a$值为$x$时的最小花费（花费包括深度$>k+1$的点）$w_{t,x}$，设$f_{i,j}$表示点$i$的点值为$j(\bmod m)$时它的子树的最小花费
对于$x\in k+1层$，$f_{x,j}$肯定就是$w_{k+1,j}$，对于$x\in k层$，$f_{x,j}=w_{2x,m-j}+w_{2x+1,m-j}$，上面层的就可以分别按左右子树的代价最小值取值了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl (i<<1)
# define tr (i<<1|1)
# define LL long long
using namespace std;
const int MAX=1e7+5,N=2e3+100;
int p,A,B,n,k,m,T;
unsigned int SA,SB,SC;
LL ans;
int a[MAX],b[MAX],fa[MAX];
LL sum[N];
LL w[N][N],Aw[N][N],f[N][N];
unsigned int rng61()
{
SA^=SA<<16,SA^=SA>>5,SA^=SA<<1;
unsigned int t=SA;
return SA=SB,SB=SC,SC^=t^SA,SC;
}
void gen()
{
scanf("%d%d%d%d%u%u%u%d%d",&n,&k,&m,&p,&SA,&SB,&SC,&A,&B);
for(int i=1;i<=p;++i)
scanf("%d%d",&a[i],&b[i]);
for(int i=p+1;i<=n;++i)
a[i]=rng61()%A+1,b[i]=rng61()%B+1;
}
int main()
{
scanf("%d",&T);
while(T--)
{
gen();
memset(Aw,0,sizeof(Aw));
memset(w,0,sizeof(w));
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;++i)
a[i]%=m;
for(int i=1;i<=n;++i)
fa[i]=(i>>k+1)?fa[i>>k+1]:i,sum[fa[i]]+=b[i],Aw[fa[i]][a[i]]+=b[i],w[fa[i]][0]+=a[i]?1ll*(m-a[i])*b[i]:0;
for(int i=1;i<(1<<k+1);++i)
for(int j=1;j<m;++j)
w[i][j]=w[i][j-1]+sum[i]-m*Aw[i][j];
for(int i=(1<<k-1);i<(1<<k);++i)
{
f[i][0]=w[tl][0]+w[tr][0];
for(int j=1;j<m;++j)
f[i][j]=w[tl][m-j]+w[tr][m-j];
}
for(int i=(1<<k-1)-1;i>=1;--i)
for(int j=0;j<=m;++j)
{
LL ans1=1e18,ans2=1e18;
for(int l=0;l<m;++l)
ans1=min(ans1,f[tl][(j+l)%m]+w[tl][l]),ans2=min(ans2,f[tr][(j+l)%m]+w[tr][l]);
f[i][j]=ans1+ans2;
}
ans=1e18;
for(int i=0;i<m;++i)
ans=min(ans,f[1][i]+w[1][i]);
printf("%lld\n",ans);
}
return 0;
}
