题意

有 $n$ 个变量，第 $i$ 个变量 $x_i$ 初始值是 $a_i$，让它加一的代价是 $b_i$。每次操作选择一个变量加一。问最少需要多少代价能对于任意的 $2^k \leq i \leq n$，都有：

$$ \sum_{b=0}^k a_{\lfloor \frac{i}{2^b}\rfloor} \equiv 0 \pmod m $$

$1 \leq T \leq 10,1 \leq k \leq 10,1 \leq m \leq 200$。

题解

首先看到 $\lfloor \frac{x}{2^i} \rfloor$ 这种神奇结构直接想到二叉树：定义 $i$ 的父亲为 $\lfloor \frac{i}{2} \rfloor$。限制变为：对于二叉树上任意一个长度为 $k$ 的父子链，都要求和是 $m$ 的倍数。

那么我们发现，对于编号 $x \geq 2^k$ 的节点，都要求和 $\lfloor \frac{x}{2^k}\rfloor$ 同余，所以我们只需要考虑前 $2^k-1$ 个点。预处理出 $w_{i,j}$ 表示 $i$ 这个点，改成同余 $j$ 的代价是什么。

这个预处理其实就是要求对于每个在外面的点，要求从 $a_i$ 开始，循环加上一个等差数列，这操作要求 $O(1)$ 。可以通过差分打两次标记计算，也可以对于每个 $<2^k$ 的点，开一个 $s_{i,j}$ 表示要求和点 $i$ 相同的所有点中，$a_i \equiv j \pmod m$ 的所有点的 $b_i$ 的和。然后类似暴力枚举计算。这一部分预处理是 $O(n+2^km)$ 或 $O(n+2^km^2)$ 的。

接下来就简单了：限制只有在儿子上。设 $f_{v,i}$ 表示满足了 $v$ 子树内所有叶子的限制，当前 $v$ 到根（不包括 $v$）的权值和是 $i$ 的方案数，转移枚举一下 $v$ 填什么就好。复杂度 $O(2^km^2)$。

代码

#include <bits/stdc++.h>

#define fi first
#define se second
#define DB double
#define U unsigned
#define P std::pair
#define LL long long
#define LD long double
#define pb emplace_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

inline char nc(){
    #define SIZE 1000003
    static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE;
    if(p1 == p2){
        p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin);
        if(p1 == p2) return -1;
    }
    return *p1++;
}

template <typename T>
inline void read(T &x){
    x = 0;char ch = nc();bool flag = 0;
    while(!isdigit(ch)){
        if(ch == '-') flag = 1;
        ch = nc();
    }
    while(isdigit(ch)){
        x = (x<<1)+(x<<3)+(ch^'0');
        ch = nc();
    }
    if(flag) x = -x;
}

unsigned int SA, SB, SC; int p, A, B;
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;
}

int n,m,k;
const int MAXN = 2048 + 5;
const int MAXM = 1e7 + 5;
int ta[MAXM],tb[MAXM],mx[MAXN];
LL w[MAXN][205],s[MAXN][205];
LL f[MAXN][205];

void gen(){
    read(n);read(k);read(m);read(p);read(SA);read(SB);read(SC);read(A);read(B);
    ++k;
    FOR(i,1,p) read(ta[i]),read(tb[i]);
    FOR(i,p+1,n) ta[i] = rng61()%A+1,tb[i] = rng61()%B+1;
    FOR(i,1,(1<<k)-1) FOR(j,0,m-1) w[i][j] = s[i][j] = 0;
    FOR(i,1,n){
        int x = i;while(x >= (1<<k)) x >>= k;
        s[x][ta[i]%m] += tb[i];
    }
    FOR(i,1,(1<<k)-1){
        FOR(j,0,m-1){
            FOR(k,0,m-1){
                w[i][j] += 1ll*s[i][k]*((j-k+m)%m);
            }
        }
    }
}

inline void dfs(int v){
    FOR(i,0,m-1) f[v][i] = 1e18;
    if((v<<1) >= (1<<k)){
        FOR(i,0,m-1) f[v][(m-i)%m] = w[v][i];
        return;
    }
    dfs(v<<1);dfs(v<<1|1);
    FOR(i,0,m-1){
        FOR(j,0,m-1){
            f[v][i] = std::min(f[v][i],f[v<<1][(i+j)%m]+f[v<<1|1][(i+j)%m]+w[v][j]);
        }
    }
}

inline void Solve(){
    gen();
    dfs(1);
    printf("%lld\n",f[1][0]);
}

int main(){
    int T;read(T);
    while(T--) Solve();
    return 0;
}