在去年R2众多毒瘤题中唯一显得清新的一道
看到下标反复(/2)的形式我们就可以想到完全二叉树，于是我们2就把题目转化成了
修改一些点的点权，使得一棵完全二叉树上所有长度为(k+1)的上行路径上点权和(mod m=0)
现在就需要发掘一下题目的性质，首先是这棵完全二叉树的前(k+1)层，这里好像没有什么特殊的性质，就是需要满足(k+1)层的每一个节点到根的点权和(mod m=0)
接下来就出现一些有趣的东西啦
对于第(k+2)层的节点，我们需要让第(2)层到这一层的路径的点权和(mod m=0)，但是注意到(1)层到(k+1)层的路径和已经(mod m=0)了
少了一个第(1)层的点，但是多了一个(k+2)层的点，点权和在模(m)意义下没有什么变化
这说明了什么，第(1)层和(k+2)层的点权在模(m)意义下是相等的
相应的，我们还会发现第(2)层和(k+2)层要相等，(3)层和(k+4)层要相等...
最后我们发现剩下的这些层竟然都被前(k+1)层的节点给控制了，我们确定了前(k+1)层的点权，剩下的点权就都确定了，大概就是牵一发而动全身
我们对于前(k+1)层的每一个节点预处理出(f_{i,j})表示节点(i)控制的节点中点权在(mod m)意义下等于(j)的所有点点权之和是多少，这个我们一边(O(n))递推就能完成
之后对于每一个点，我们以(O(m^2))的时间预处理出这个点的点权修改成(0)到(m-1)这些数的花费是多少
设(dp_{i,j})表示第(i)个点从这个点到(k+1)的所有路径都被处理成了在模(m)意义下为(j)的最小花费
对于每一个点来说，这个点到(k+1)层的所有路径长度都应该是相等的，于是我们自底向上来一遍树形(dp)就好了，具体的就是枚举两个儿子到(k+1)层的点权和是多少，枚举这个点点权修改成什么，这样就能转移啦
最后的答案就是(dp_{1,0})
但是我们交上去就发现怎么过了后面两个(subtask)却(wa)了第一个点
结果发现第一个点的二叉树甚至不够(k+1)层，于是我们直接补全成(k+1)层，多补出来的那些点点权修改成什么都为(0)就好啦
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=1e7+5;
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
int n,k,m,h,a[maxn],b[maxn],T;
LL val[2096][205],co[2096][205],dp[2096][205];
int id[maxn];
unsigned int SA,SB,SC;int p,A,B;
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 gen() {
scanf("%d%d%d%d%u%u%u%d%d",&n,&k,&m,&p,&SA,&SB,&SC,&A,&B);
for(re int i=1;i<=p;i++) a[i]=read(),b[i]=read();
for(re int i=p+1;i<=n;i++) {
a[i]=rng61()%A+1;
b[i]=rng61()%B+1;
}
for(re int i=1;i<=n;i++) a[i]%=m;
}
int main() {
T=read();
while(T--) {
memset(dp,20,sizeof(dp));
memset(co,0,sizeof(co));
memset(val,0,sizeof(val));
gen();int g=(1<<(k+1));h=g-1;
for(re int i=1;i<=n;i++) {
if(i/g) id[i]=id[i/g];
else id[i]=i;
val[id[i]][a[i]]+=b[i];
}
for(re int i=1;i<=n;i++) {
if(id[i]!=i) {h=i-1;break;}
for(re int j=0;j<m;j++)
for(re int k=0;k<m;k++)
co[i][j]+=((j-k+m)%m)*val[i][k];
}
for(re int i=h;i;--i) {
if((i<<1)>h&&(i<<1|1)>h) {
for(re int j=0;j<m;j++)
dp[i][j]=co[i][j];
continue;
}
int ls=i<<1,rs=i<<1|1;
for(re int j=0;j<m;j++)
for(re int k=0;k<m;k++)
dp[i][(j+k)%m]=min(dp[i][(j+k)%m],co[i][j]+dp[ls][k]+dp[rs][k]);
}
printf("%lld
",dp[1][0]);
}
return 0;
}