题目链接
题解
看到式子，立即想到二叉树上一个点及其\(k\)个父亲权值和【如果有的话】模\(m\)意义下为\(0\)
考虑如何满足条件
我们假设\(1\)号为第\(0\)层
那么我们先满足第\(k\)层的条件
由于第\(k + 1\)层也满足条件
由同余的性质第\(k + 1\)层的权值等于第\(1\)层的权值
同理可以往下推
所以在超过第\(k\)层后，每个节点往上都会与某个节点相联结
我们就不妨求出\(w[i][j]\)表示前\(k\)层的节点\(i\)权值变为\(j\)所需要付出的最小代价
显然\(w[i][j]\)就是与\(i\)联结的包括\(i\)的所有节点权值加到\(j\)的代价和
暴力转移是\(O(nm)\)的，但是发现加的是一个等差数列
所以我们双层差分即可\(O(n + 2^{k}m)\)计算出\(w[i][j]\)
然后就可以树形\(dp\)了
有了\(w[i][j]\)，我们只需求出第\(k\)层往上权值和为\(0\)的最小代价，其它点就默认满足要求了
我们设\(f[i][j]\)表示点\(i\)到第\(k\)层权值和为\(j\)的最小代价即可
交上去第一个点\(WA\)了，为什么？
考虑\(f[i][j]\)表示的是到第\(k\)层权值和为\(j\)，如果这个第\(k\)层根本不存在，这个限制就没有意义了
换言之，\(i\)取什么值都不影响结果
怎么解决这个问题？
我们人为加满至第\(k\)层，多出来的节点的\(b\)设为\(0\)即可
复杂度\(O(n + 2^{k}m^2)\)
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long long int
using namespace std;
const int maxn = 100005,maxm = 100005,N = 10000005;
const LL INF = 100000000000000000ll;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
LL b[N];
int a[N],fa[N],n,m,K;
unsigned int SA, SB, SC;int p, AA, BB;
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;
}
void gen(){
scanf("%d%d%d%d%u%u%u%d%d", &n, &K, &m, &p, &SA, &SB, &SC, &AA, &BB);
for(int i = 1; i <= p; i++)scanf("%d%lld", &a[i], &b[i]);
for(int i = p + 1; i <= n; i++){
a[i] = rng61() % AA + 1;
b[i] = rng61() % BB + 1;
}
if (n < (1 << K + 1) - 1){
for (int i = n + 1; i < (1 << K + 1); i++)
a[i] = b[i] = 0;
n = (1 << K + 1) - 1;
}
for (int i = 1; i <= n; i++){
a[i] %= m;
if (i < (1 << K + 1)) fa[i] = i;
else fa[i] = fa[i / (1 << K + 1)];
}
}
LL w[2100][205];
void calw(){
int u; cls(w);
for (int i = 1; i <= n; i++){
u = fa[i];
if (!a[i]){
w[u][1] += b[i];
}
else {
w[u][0] += b[i] * (m - a[i]);
if (a[i] > 1){
w[u][1] -= b[i] * (m - a[i] - 1);
w[u][a[i]] -= b[i] * m;
}
else {
w[u][1] -= 2 * b[i] * (m - 1);
}
w[u][a[i] + 1] += b[i] * m;
}
}
int E = min(n,(1 << K + 1) - 1);
for (int i = 1; i <= E; i++){
for (int j = 1; j < m; j++)
w[i][j] += w[i][j - 1];
for (int j = 1; j < m; j++)
w[i][j] += w[i][j - 1];
}
}
LL f[2100][205];
void work(){
int E = min((1 << K + 1) - 1,n);
for (int i = E; i; i--){
int ls = i << 1,rs = i << 1 | 1;
if (ls > E) ls = 0;
if (rs > E) rs = 0;
if (!ls && !rs){
for (int j = 0; j < m; j++) f[i][j] = w[i][j];
}
else if (ls && !rs){
for (int j = 0; j < m; j++){
f[i][j] = INF;
for (int k = 0; k < m; k++){
f[i][j] = min(f[i][j],w[i][(m + j - k) % m] + f[ls][k]);
}
}
}
else {
for (int j = 0; j < m; j++){
f[i][j] = INF;
for (int k = 0; k < m; k++){
f[i][j] = min(f[i][j],w[i][(m + j - k) % m] + f[ls][k] + f[rs][k]);
}
}
}
}
printf("%lld\n",f[1][0]);
}
int main(){
int T = read();
while (T--){
gen();
calw();
work();
}
return 0;
}