A – 走格子
其实就是靠墙走，然后乱七八糟的东西全部用 Djisktra 来搞就行了。
这道题的式子跟 Codeforces 一道 F 题是一样的，让我误以为是 BSGS 之类的玩意，最后发现其实算是矩阵乘法的题。
考虑任意一个答案都是由\(\{f_n\}\)的幂的积组成的，由于\(k\)很小，所以我们可以考虑计算每一个\(f\)的指数，然后就可以用快速幂来计算这些东西。
首先，这道题是概率和期望分开算的，进行 DP 时实质上是对概率进行 DP。考虑拆位，设\(dp_b [u]\)为从\(u \to n\)在第\(b\)位为\(1\)的概率，那么显然：
\[ dp_b[u] = \frac{1}{deg[u]}( \sum_{weight(u, v) !\& b} dp_b[v] \sum_{weight(u, v) \& b} (1 – dp_b[v]) ) \]
其中，\((1 – dp_b[v])\)为\(v\)为\(0\)的概率，最后答案消元完就是\(\sum_{i = 1} ans[i] 2^i\)。
这道题看了题解之后发现就是一道 sb 题。
考虑将每一列看成一个数，发现如果忽略掉列的操作，这些数仍然满足等差的条件，所以我们只要暴力算完第一列就可以进行等差了。如果考虑列的操作，那么我们就大力暴力就行了，时间复杂度是\(O(n + m)\)。
今天被各路神仙吊打，顺利 gg。
在考场上我推了个有后效性的 DP，还以为是高斯消元，然后看到数据范围就 GG 了。这道题主要是把一些东西给转换掉了。
首先，对一个概率为\(p\)的事件，它的期望次数是\(\frac{1}{p}\)（参见这里）。然后，考虑一个状态\(dp[i]\)代表合成第\(i\)级武器的期望花费。显然\(dp[0] = a\)。
考虑\(dp[1]\)的求法，首先需要两个级别为\(0\)的武器，然后发现无论失败与否都可以保证至少又一个\(0\)级武器，所以我们只需要注意另外一个武器的花费就可以了：
\[ dp[1] = dp[0] + dp[1] \times \frac{1}{p} \]
这道题在 JZOJ 上面开 10s，遂 AC。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 60100;
struct point
{
int x, y, prop, id;
bool operator<(const point &pt) const { return prop < pt.prop; }
} nodes[MAX_N], *cur[MAX_N];
int n, m;
char opt[10];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d%d%d", &nodes[i].x, &nodes[i].y, &nodes[i].prop), nodes[i].id = i;
sort(nodes + 1, nodes + 1 + n);
for (int i = 1; i <= n; i++)
cur[nodes[i].id] = &nodes[i];
while (m--)
{
scanf("%s", opt + 1);
int x, y, x_, y_, k;
if (opt[1] == 'Q')
{
scanf("%d%d%d%d%d", &x, &y, &x_, &y_, &k);
bool flag = false;
for (int i = 1; i <= n; i++)
if (nodes[i].x <= max(x, x_) && nodes[i].x >= min(x, x_) && nodes[i].y <= max(y, y_) && nodes[i].y >= min(y, y_))
{
k--;
if (k == 0)
{
printf("%d\n", nodes[i].prop), flag = true;
break;
}
}
if (!flag)
puts("It doesn't exist.");
}
else
{
scanf("%d%d", &x, &y), x++, y++;
swap(cur[x]->x, cur[y]->x), swap(cur[x]->y, cur[y]->y);
swap(cur[x]->id, cur[y]->id), swap(cur[x], cur[y]);
}
}
return 0;
}