widsnoy's blog

其实我在一年多前就在老刘的专题训练做过这个题了，队友问起这个题又复习了一下，还是有很多收获。唉唉，转眼都要退役了，时间过得真快

题意

度度熊最近迷上一个小游戏：Flip it。游戏的规则很简单，在一个N*M的格子上，有一些格子是黑色，有一些是白色。每选择一个格子按一次，格子以及周围边相邻的格子都会翻转颜色（边相邻指至少与该格子有一条公共边的格子），黑变白，白变黑。

度度熊希望把所有格子都变成白色的。不幸的是，有一些格子坏掉了，无法被按下。这时，它可以完成游戏吗？

题解

首先可以发现，如果确定了第一行或者第一列的每一个开关是否按下，那么其他所有开关是否被按就是确定的。

不妨设第一行的每个开关的状态为 \(x_i\)，显然按两次以上开关没有意义，所以 \(x_i \in \{0, 1\}\)。设 \(f(i, j)\) 表示开关 \((i,j)\) 的状态, \(f\) 是一个关于 \(x_1,x_2,x_3\dots x_m,x_{m+1}\) 的 \(m+1\) 元一次函数，且系数为 \(0\) 或者 \(1\)。这里多了一个变量 \(x_{m+1}\)，之后会解释。

对于第一行 \(f(1,j)=x_i\)。考虑一行一行的转移 \(f\)，因为 \((i, j)\) 开关恰好会影响 \((i-1,j)\) 的格子颜色，而影响那个格子颜色的其他四个开关的状态 \(f(i-1,j)\), \(f(i-1,j-1)\), \(f(i-1,j+1)\), \(f(i-2,j)\) 已经算出，再结合 \((i-1,j)\) 本来的颜色就可以递推出 \(f(i,j)\)，这也解释了为什么要多设一个 \(x_{m+1}\)，实际上 \(x_{m+1}\) 是一个恒 \(1\) 的变量，作用是考虑格子本来的颜色带来的影响。

可能有人会疑惑，递推 \(f\) 的时候为什么不考虑相邻两列互相影响。这是因为 \(f\) 表示的是开关是否按下，而不是格子的颜色状态。

实际上这样做之后，保证了当前这一行无论是什么颜色，下一行的开关始终能让它们变成白色。但是最后一行就需要自身保证操作完之后是白色的，这也是约束条件。

这把罚时战神，还好过了个百人题，才没在队内垫底

对 \(f(x)=\sum\limits_{i=0}^nc_ix^i\) 进行 \(m\) 次平移，每次向右平移 \(a_i\)，问最终得到的表达式 \(g(x)\)

画图发现平移 \(m\) 次和一次平移 \(\sum a_i\) 的结果是一样的，所以只考虑计算一次平移。

\[ \begin{aligned} g(x)&=\sum_{i=0}^{n}c_i(x-a)^i\\ &=\sum_{i=0}^{n}c_i\sum_{j=0}^i\binom{i}{j}(-a)^{i-j}x^j\\ &=\sum_{j=0}^n\sum_{i=j}^nc_i\binom{i}{j}(-a)^{i-j}x^j\\ \Rightarrow [x^j]g(x)&=\sum_{i=j}^nc_i\binom{i}{j}(-a)^{i-j}\\ &=\sum_{i=0}^{n-j}c_{i+j}\dfrac{(i+j)!}{i!j!}(-a)^i\\ &=\dfrac{1}{j!}\sum_{i=0}^{n-j}c_{i+j}(i+j)!\dfrac{(-a)^i}{i!} \end{aligned} \]

令 \(p_i=c_{i}i!\), \(b_{n-i}=\dfrac{(-a)^i}{i!}\), 得到 \([x^j]g(x)=\dfrac{1}{j!}\sum\limits_{i=0}^{n-j}p_{i+j}b_{n-i}\)，很显然只需要用 NTT 算出 \(p*b\) 即可。

这个多测一开始没注意到，太难崩了。。。
> There are 11 test cases.

生成函数

• 常用封闭形式

1. \(a=\langle 0,1,1,1,1,\cdots\rangle \rightarrow \dfrac{x}{1-x}\)

2. \(a=\langle 1,0,1,0,1,\cdots \rangle\)
   \[ \begin{aligned} F(x)&=\sum_{n\ge 0}x^{2n}\\ &=\sum_{n\ge 0}(x^2)^{n}\\ &=\frac{1}{1-x^2} \end{aligned} \]

3. \(a=\langle 1,2,3,4,\cdots \rangle\) \[\begin{aligned}F(x)&=\sum_{n\ge 0}(n+1)x^n\\&=\sum_{n\ge 1}nx^{n-1}\\&=\sum_{n\ge 0}(x^n)'\\&=\left(\frac{1}{1-x}\right)'\\&=\frac{1}{(1-x)^2}\end{aligned}\]

4. \(a_n=\binom{m}{n}\)（\(m\) 是常数，\(n\ge 0\)） \[ F(x)=\sum_{n\ge 0}\binom{m}{n}x^n=(1+x)^m\]

5. \(a_n=\binom{m+n}{n}\)（\(m\) 是常数，\(n\ge 0\)） \[F(x)=\sum_{n\ge 0}\binom{m+n}{n}x^n=\frac{1}{(1-x)^{m+1}}\]

• 牛顿二项式定理

我们重新定义组合数的运算：

\[ \binom{r}{k}=\frac{r^{\underline{k}}}{k!}\quad(r\in\mathbf{C},k\in\mathbf{N}) \]

注意 \(r\) 的范围是复数域。在这种情况下。对于 \(\alpha\in\mathbf{C}\)，有

\[ (1+x)^{\alpha}=\sum_{n\ge 0}\binom{\alpha}{n}x^n \]

二项式定理其实是牛顿二项式定理的一个特殊情况。

• 例题: BZOJ 3028 食物

Taking Candies

Emofunc 和 Cnufome 进行 \(n\) 轮拍卖。两人初始时候分别有 \(x\)，\(y\) 枚金币，每次 Emofunc 先手，成功拍卖的人将钱给对方，然后从 \(n\) 件物品中随意选择一个拿走。如果两个人都执行最优策略，Emofunc 能得到的物品价值和最大是多少？ \(n\le1e5,x,y\le 100\)

观察到金币数很少，尝试用它来划分状态。\(f[n][x][y]\) 表示还剩下 \(n\) 个物品，Emofunc 和 Cnufome 分别有 \(x\)，\(y\) 枚金币的情况下，Emofunc 先手最多能得到多大价值和的物品。

枚举 Emofunc 提出多大的竞拍价格 \(t\)，能获得的收益是 \(\min\limits_{t'>t}(f[n-1][x-t][y+t]+a[n],f[n-1][x+t][y-t])\)。取 min 是因为 Cnufome 可以提出一个更高的竞拍价格来最小化 Emofunc 的收益。只需要考虑一轮是因为，如果考虑多轮，发现是和只考虑一轮一样的问题。

发现 \(x+y\) 是定值，所以可以压缩一维状态。而且对于同一个 \(n\)，\(f[n][x]\) 显然关于 \(x\) 单调。因为钱更多肯定在拍卖中占优势。

1
2
3
4
5
6
7
8
9

for (int i = 1; i <= n; i++) {
    for (int x = 0; x <= xy; x++) {
        for (int t = 0; t <= x; t++) {
            ll res = dp[i - 1][x - t] + a[i];
            if (x + t + 1 <= xy) res = min(res, dp[i - 1][x + t + 1]);
            dp[i][x] = max(dp[i][x], res);
        }
    }
}

考虑怎么优化 \(t\) 那一层循环，发现如果某个 \(t\) 满足 \(dp[i - 1][x - t] + a[i]<dp[i - 1][x + t + 1]\) 那么更大的 \(t\) 也满足，可以直接二分出转折点，并且我们还发现最优的转移点一定是转折点相邻的两个点！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;

#define fi first
#define se second
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
//mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int mod = 998244353;
const int N = 1e5 + 5;

ll dp[N][201];
int n, a[N], xy;
ll sum[N];

void MAIN() {
    int n, x, y;
    cin >> n >> x >> y;
    xy = x + y;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        for (int x = 0; x <= xy; x++) {
            int l = 0, r = x, ans = -1;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (x + mid + 1 > xy || dp[i - 1][x + mid + 1] > dp[i - 1][x - mid] + a[i]) r = mid - 1, ans = mid;
                else l = mid + 1;
            }
            if (ans == -1) dp[i][x] = dp[i - 1][x + x + 1];
            else dp[i][x] = max(dp[i - 1][x - ans] + a[i], dp[i - 1][x + ans]);
        }
    }
    cout << dp[n][x] << '\n';
}

int main() {
    //int size(512 << 20); // 512M
    //__asm__("movq %0, %%rsp
    ios::sync_with_stdio(0); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) MAIN();
    return 0;
}

The Set of Squares

A Bit More Common

有多少个长度为 \(n\) 的序列，值域范围 \([0,2^m)\)，满足至少存在两个不同的子序列并为 \(1\)。

如果是至少存在一个子序列，考虑用一个极长的合法子序列来映射一个序列。假设极长的合法子序列长度为 \(k\)，即只有这些第一位是 \(1\)，并且剩下的位不能全为 \(1\)。方案数是 \(\sum\limits_{i=1}^{n}\binom{n}{i}(2^{i}-1)^{m-1}2^{(n-i)(m-1)}\)

考虑恰好只有一个子序列合法的序列个数。同样枚举极长合法子序列的长度 \(k\)。只有一个合法子序列即不能删除其中任何一个数，也就是每一位都要拿到至少一个位，只有它在这一位是 \(0\)，否则的话一定可以删它。

枚举 \(t\) 个这样的特殊的位，这里也就相当于将 \(t\) 个有标号小球放入 \(k\) 个有标号的盒子，方案数是 \(\begin{Bmatrix}n\\m\end{Bmatrix}\times m!\) 。比赛的时候竟然没看出来这一步，真是离谱。当时想到是算不定方程所有解的多重集全排列，然而根本不会。

XOR of Suffix Sums

给一个操作序列。每次删除序列末尾的一些数字，求所有后缀和的异或值。

很妙的一个题，第一眼看到的时候，所有和的异或值，这东西没法拆位做啊。想了一下这个东西有点像去年杭电多校 2 的 1005，第 k 位的数字一定是连续模 \(2^{k+1}\) 之后不小于 \(2^k\) 的数字，然后就想到开 \(21\) 个权值线段树，每个树都相当于一个 \(modint\)，于是就可以查有多少个 1 了。考虑增加或者删除一个数字，也就是给这个线段树做一个循环位移，然而根本不知道怎么维护...

于是就一直卡 B，D 两题，也不开新题，为什么我总是拿不起放不下啊。

如果这题把后缀和改成前缀和我肯定就会做了，因为区间修改变成了单点修改。那么这个题是不是能转化为前缀和呢，\(suf_i=sum-pre_{i-1}\)，我们想知道 \(\mod 2^{k+1}\) 的那颗树有多少后缀和在 \([2^k,2^{k+1})\)，也就得到答案的第 \(k\) 位。

好像有首叫 ラビットホール 的小黄歌来着

有一个无向联通图 \(G<V,E>\)，在某一个点上有一只兔子。从某时刻开始，每个周期你可以选择一个点查看兔子是否在这个点，然后兔子移动到相邻的点（不能停留在原点）。问你是否存在一种查看的顺序能够保证找到兔子。

这个问题也等价于，每个点上有无数只兔子，同样的游戏规则，问你是否能有一种方法找到所有兔子。一只能找到那么所有的当然也可以。反过来所有地方有兔子都能全部找到，那么一只兔子无论开始在哪里都可以找到。

首先我们可以考虑几种特殊的情况。

1. 如果这个图不是树的话，那么一定存在环。如果有环，兔子可以一直沿着环走，不存在一种查看方式能将兔子活动范围限制在某个区域。

2. \(|G|\) 比较小。这时候可以考虑状压 \(dp\)。状态 \(dp[mask]\) 表示这些点都有无限只兔子的时候，能不能找出所有兔子。转移就枚举看了哪个点，然后剩下的兔子走到相邻节点。

3. 这个图是一条链。
   

不妨假设兔子最开始在的点为黑点，这就意味着奇数时刻兔子一定在黑点，而偶数时刻兔子在白点。所以我们奇数时刻看黑点，偶数时刻看白点。

从点 \(1\)（黑点） 开始依次看右边的点，这时候兔子如果不在 1 就在右边的点。可以发现，当我们在看 \(i\) 点的时候，兔子不可能出现在更小的点。因为发生交换只有在看某个 \(j\) 点的时候兔子在 \(j + 1\) 处然后下一时刻看 \(j+1\) 兔子在 \(j\)。但是这种情况是不可能的，因为我们看的点一定和兔子所在点颜色相同。

然后因为兔子最开始不一定在黑点，所以要从 \(n\) 开始倒着看一遍，多看一次 \(n\) 刚好交换了奇偶性。

可以从一条链入手考虑更一般的情况，不妨考虑以一条链为基础挂上一些点和边来形成一棵树。直觉为了满足要求，挂的点越少越好。

接下来我们都假设兔子一开始在黑点，从左到右查看。如果是在白点，那么反之亦然。

画图可以发现，对于每个点做右下顶点的时候，合法的另一个顶点是其右上方的一个下凸壳。
下凸壳可以用单调队列维护，但每次都建立一个单调队列肯定不行。按照 x 的值建立树状数组，用树状数组的区间划分一个后缀，对每个区间都维护其中的点的单调队列。合并两个单调队列，二分即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;

#define fi first
#define se second
typedef pair<int, int> pii;
typedef long long ll;
//std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int mod = 998244353;
const int N = 1e5 + 5;
int n;
pii a[N];
vector<pii> tr[N];
void insert(int x, int y) {
    for (int i = x; i; i -= i & -i) {
        while (!tr[i].empty() && tr[i].back().se >= x) tr[i].pop_back();
        tr[i].push_back({y, x});
    }
}
int qry(int x, int y) {
    int res = 0, lst = 2000000005;
    for (; x <= n; x += x & -x) {
        if (tr[x].empty()) continue;
        int l = 0, r = tr[x].size() - 1, pos = -1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (tr[x][mid].fi < lst) r = mid - 1, pos = mid;
            else l = mid + 1;
        }
        if (pos == -1) continue;
        res += tr[x].size() - pos;
        lst = tr[x].back().fi;
    }
    return res;
}

ll solve() {
    for (int i = 1; i <= n; i++) tr[i].clear();
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += qry(a[i].fi, a[i].se);
        insert(a[i].fi, a[i].se);
    }
    return ans;
}
void MAIN() {
    cin >> n;
    vector<int> vec;
    map<int, int> rx, ry;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].fi >> a[i].se, vec.push_back(a[i].fi);
        rx[a[i].fi]++, ry[a[i].se]++;
    }
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    auto cmp = [](pii x, pii y) {return x.se > y.se || (x.se == y.se && x.fi > y.fi);};
    for (int i = 1; i <= n; i++) a[i].fi = lower_bound(vec.begin(), vec.end(), a[i].fi) - vec.begin() + 1;
    sort(a + 1, a + n + 1, cmp);
    ll ans = solve();
    for (int i = 1; i <= n; i++) a[i].se = -a[i].se;
    sort(a + 1, a + n + 1, cmp);
    ans += solve();
    for (auto [x, r] : rx) ans -= r - 1;
    for (auto [x, r] : ry) ans -= r - 1;
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T--) MAIN();
    return 0;
}

考虑倒着做，从起点开始扩展打印出可能的形状。比如从起点是 16, 向四周扩展一个格子，变为 8、8...可以发现最大填的数是 16，合法的形状不大于 9x9。
实际上预处理可行的形状是非常麻烦的，这里提供一个全网最简单的做法，反正我没看懂 Claris 大神的代码 qwq（
反正数据范围很小，我们直接用一个单调队列保存状态来搜索，判断重复可以重载一个比较结构体用 map 判重。保存形状可以用一个 __int128。

好吧，我是标题党x

请各位完成一份杭州电子科技大学院系逻辑结构，以树形结构描述出来，叶子结点为各专业，可去各分院官网搜索信息，作为本学期的思政作业。

我发现学校总是喜欢布置些奇怪的任务x
不过不会真有人手写吧（x
记录一下我是怎么做这个作业的（
这个应该算可以公开的信息吧（？