这集神了。

先考虑一条链怎么做，即求 $\sum_{i=0}^k a_{x+i}\text{ xor } i$。因为先异或后求和，可以考虑拆位来算，不难发现，$\forall j\in [x,x+2^p)$，$a_j$ 的第 $p$ 位都异或上了 $0$，如果我们将第 $p$ 位去掉并只考虑小于 $p$ 位的贡献，不难发现区间分成了 $[x,x+2^{p-1}),[x+2^{p-1},x+2^p)$ 两个子区间，且他们要解决的问题结构完全相同，这启发我们用倍增去解决问题。

设 $f_{i,j}$ 表示只考虑小于 $j$ 位的值对于 $\sum_{p=0}^{2^j-1} a_{i+p}\text{ xor } p$，设 $g_{i,j,0/1}$ 表示 $1\sim i$ 中第 $j$ 位为 $0/1$ 的位置个数，则有：
$$f_{i,j}=f_{i,j-1}+f_{i+2^{j-1},j-1}+(g_{i+2^{j-1}-1,j-1,1}-g_{i-1,j-1,1}+g_{i+2^j-1,j-1,0}-g_{i+2^{j-1},j-1,0})2^{j-1}$$

这个转移式子大概意思是：对于一个长度为 $2^j$ 的区间，先将这个东西小于 $j-1$ 位的贡献求出来，然后考虑第 $j-1$ 位的贡献，前一半区间只有第 $j-1$ 位为 $0$ 能贡献，后一半只有为 $1$ 才能贡献。

然后我们回到询问，从高到低位拆位算贡献，同时倍增跳，能跳就跳，不能跳就将当前位置到终点部分剩余位置在当前拆的这一位上的贡献算出来。

for(int j=30;j>=0;j--){
	if((k>>j)&1){
		nxt=u+(1<<j);ans+=f[j][u];
		c1=g[1][j][nxt-1]-g[1][j][u-1];
		c0=g[0][j][r]-g[0][j][nxt-1];
		ans+=(c1+c0)*(1ll<<j);u=nxt;
	}else{
		ans+=(g[1][j][r]-g[1][j][u-1])*(1ll<<j);
	}
}

具体的，我们将倍增数组 $f_{i,j}$ 的定义改为从 $i$ 到 $i$ 所在长链往下 $2^j$ 步。对于轻重儿子合并，可以直接将轻儿子的倍增数组加到重儿子的倍增数组上，然后直接对当前点的 $\log$ 个位置倍增。对于 $g$ 也这样更改定义，但是从前缀和变成了后缀和，这样可能会出现很多问题：如倍增数组空位无法合并，后缀和可能访问到不该访问的值，但总而言之是小问题，模仿上面的倍增过程跳下去即可。

时间复杂度为 $O(n\log V)$。

真（ru）的（yi）是（ke）签（ai）到（miao）。

看到 $n$ 大得吓人，于是我们不乱想，考虑贪心。具体来说就是我们发现每次从根结点往下走一定是走到一个叶子的地方，具体来说就是我们可以把树上的一堆边看作一条条链之后贪心的选。

具体来说就是对于一个结点记录以它为起点往下走到叶子能够得到的最优价值，所以我们可以遍历每个结点的时候可以更新其父结点能够得到的最优价值，因为当前父结点已经确定了除去走向当前结点的那条路径的最优价值，我们只需要看一下走向当前结点的是不是更优就可以了，注意要是我们成功更新了，就需要把原本的那条价值较高的链和父结点断开，因为我们到重复的点是不重复计算的，没有重复更新就断开当前结点和父亲的连边。

代码实现就是可以把当前结点确定的路径全部都设置成它原本的价值，然后遍历结点更新答案，每次确定了一条链的时候（假如我们知道了当前父节点连哪一条与儿子的边最大或者确定了某一个结点与它父亲的连边要断开就能确定）就直接把它丢进一个数组里，最后把这个数组排序取前 $k$ 大就做完了，因为我们最多访问 $k$ 个叶子。代码很好写，因为观察父节点的生成方式，$i$ 的父节点一定是小于 $i$ 的，那我们甚至连递归都不用了。

[COGS 4161] hope I can sort 题目解析

 引入

 注意到本题的01序列的排序过程可简化为错位数 k（前 c0 个位置中 1 的个数）的链。

 因此可以考虑动态规划。

 分析

#include<bits/stdc++.h>
using namespace std;

const int MOD=998244353,N=5005;
int a[N],dp[N],nd[N];

int qp(int a,int b){
	int r=1;
	while(b){
		if(b&1)r=1ll*r*a%MOD;
		a=1ll*a*a%MOD;
		b>>=1;
	}
	return r;
}

int main(){
    freopen("hopeicansort.in","r",stdin);
    freopen("hopeicansort.out","w",stdout); 
	int n,m;
	cin>>n>>m;
	int c0=0;
	for(int i=1;i<=n;++i)
    {
		cin>>a[i];
		if(!a[i]) ++c0;
	}
	int k0=0;
	for(int i=1;i<=c0;++i) 
        if(a[i]) 
            ++k0;
	int mx=k0<c0?k0:n-c0;
	if(mx<k0) mx=k0;
	int T=1ll*n*(n-1)/2%MOD,invT=qp(T,MOD-2);
	dp[k0]=1;
	for(int t=0;t<m;++t)
    {
		for(int k=0;k<=mx;++k) nd[k]=0;
		nd[0]=(dp[0]+1ll*dp[1]*invT)%MOD;
		for(int k=1;k<=mx;++k)
        {
			int d=1ll*k*k%MOD*invT%MOD;
			nd[k]=(1ll*dp[k]*(1-d+MOD)+1ll*dp[k+1]*(k+1)%MOD*(k+1)%MOD*invT)%MOD;
		}
		for(int k=0;k<=mx;++k) dp[k]=nd[k];
	}
	cout<<dp[0];
	return 0;
}

T4 - Constructive 题解

题目简述

题目大意：
给定 $N$ 种二维向量 $v_i = (a_i, b_i)$ 及其代价 $c_i$，每种向量可无限次使用。求构造出目标向量 $u = (x, y)$ 的最小总代价。

• 向量数量 $N \le 90$
• 目标坐标 $x, y \le 10^9$
• 向量分量 $a_i, b_i \le 10$
• 向量代价 $c_i \le 10^9$

子任务简析

从简单情况到一般情况的思考过程：

• Subtask 1: 步长为 1 的坐标移动，结果显而易见。
• Subtask 2 & 3: 坐标范围小，直接建图跑 Dijkstra。
• Subtask 4: 降维打击，转化为一维无界背包。
• Subtask 5: 大坐标直线路径，引入同余类 BFS/DP 思想。

正解

解法 1：分治（官方题解）

几何中点引理：
如果一组短向量的和为 $(x, y)$，那么我们通过调整顺序，一定可以把他们分成两半，使得每一半的和都在 $(\frac{x}{2}, \frac{y}{2})$ 的常数范围内。

转移方程：

$f(x, y) = \min_{\delta_x, \delta_y} \{ f(\lfloor \frac{x}{2} \rfloor + \delta_x, \lfloor \frac{y}{2} \rfloor + \delta_y) + f(\lceil \frac{x}{2} \rceil - \delta_x, \lceil \frac{y}{2} \rceil - \delta_y) \}$

#include <bits/stdc++.h>
using namespace std;

const long long INF = 4e18;
const int MAX_LENGTH = 10;
long long one_vec[MAX_LENGTH + 1][MAX_LENGTH + 1];
unordered_map <long long, long long> dp;
const int MAX_X = 1000000001;

long long DP(long long x, long long y){
    long long pos = x * MAX_X + y;
    if(dp.count(pos)) return dp[pos];

    long long tmp = INF;
    if(x <= MAX_LENGTH && y <= MAX_LENGTH) tmp = one_vec[x][y];

    for (long long dx = -MAX_LENGTH; dx <= MAX_LENGTH; dx++){
        for (long long dy = -MAX_LENGTH; dy <= MAX_LENGTH; dy++){
            long long x1 = x / 2 + dx, y1 = y / 2 + dy;
            long long x2 = x - x1, y2 = y - y1;
            if(min({x1, x2, y1, y2}) < 0) continue;
            if(x1 + y1 == 0 || x2 + y2 == 0) continue;
            tmp = min(tmp, DP(x1, y1) + DP(x2, y2));
        }
    }
    return dp[pos] = tmp;
}

int main(){
    int N; long long x, y;
    cin >> N >> x >> y;
    for (int i = 0; i <= MAX_LENGTH; i++)
        for (int j = 0; j <= MAX_LENGTH; j++) one_vec[i][j] = INF;

    for (int a, b, c; N--;){
        cin >> a >> b >> c;
        one_vec[a][b] = min(one_vec[a][b], (long long)c);
    }
    long long ans = DP(x, y);
    if(ans >= INF) cout << "-1\n";
    else cout << ans << '\n';
    return 0;
}

解法 2：基底 + 小范围微调

核心逻辑：我们先在原点附近进行小范围的精确搜索（微调），然后通过解二元一次方程组，利用“性价比”最高的基底向量组快速跨越远距离。

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const ll INF = 4e18;

struct vec { int a, b; ll c; } v[105];
struct node {
    int x, y; ll d;
    bool operator > (const node& o) const { return d > o.d; }
};

int n; ll tx, ty, res = INF;
ll dp[205][205];

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> tx >> ty;
    for(int i = 1; i <= n; i++) cin >> v[i].a >> v[i].b >> v[i].c;
    
    for(int i = 0; i <= 30; i++)
        for(int j = 0; j <= 30; j++) dp[i][j] = INF;

    priority_queue<node, vector<node>, greater<node>> pq;
    dp[0][0] = 0; pq.push({0, 0, 0});
    while(!pq.empty()){
        node cur = pq.top(); pq.pop();
        if(cur.d > dp[cur.x][cur.y]) continue;
        for(int i = 1; i <= n; i++){
            int nx = cur.x + v[i].a, ny = cur.y + v[i].b;
            if(nx <= 30 && ny <= 30 && dp[nx][ny] > cur.d + v[i].c){
                dp[nx][ny] = cur.d + v[i].c;
                pq.push({nx, ny, dp[nx][ny]});
            }
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            ll det = 1LL * v[i].a * v[j].b - 1LL * v[j].a * v[i].b;
            for(int dx = 0; dx <= 30; dx++){
                for(int dy = 0; dy <= 30; dy++){
                    if(dp[dx][dy] == INF) continue;
                    ll rx = tx - dx, ry = ty - dy;
                    if(rx < 0 || ry < 0) continue;
                    if(det != 0){
                        ll na = rx * v[j].b - ry * v[j].a;
                        ll nb = ry * v[i].a - rx * v[i].b;
                        ll d = det;
                        if(d < 0) { d = -d; na = -na; nb = -nb; }
                        if(na >= 0 && nb >= 0 && na % d == 0 && nb % d == 0)
                            res = min(res, dp[dx][dy] + (na / d) * v[i].c + (nb / d) * v[j].c);
                    } else if(1LL * v[i].a * ry == 1LL * v[i].b * rx){
                        ll k = -1;
                        if(v[i].a != 0 && rx % v[i].a == 0) k = rx / v[i].a;
                        else if(v[i].b != 0 && ry % v[i].b == 0) k = ry / v[i].b;
                        else if(v[i].a == 0 && v[i].b == 0 && rx == 0 && ry == 0) k = 0;
                        if(k >= 0) res = min(res, dp[dx][dy] + k * v[i].c);
                    }
                }
            }
        }
    }
    if(res >= INF) cout << -1 << '\n';
    else cout << res << '\n';
    return 0;
}