DEL 至少作为一个 OIer 已经死去了。
省选退役。
第一天代码版本没有核对好，交了个一半的，丢了100.
第二天读入优化写错。windows 拍不出错 linux RE. 200 全没有.
我的竞赛生涯就是笑话。
有了这 400 分会怎样？
那么多“如果”漏了出来。如果我把那天的咖喱全都吃光是不是好一点。
抱歉。真的抱歉。
只能走到一半，就走不下去了。
我尽力了可是运气不站在我这边。当时我在逞能。现在我也是。
有几十篇存货一起放上来吧。排版大概是不会排的了。更新也不会更了。
为了方便都设为了前一天的日期。也算是纪念至少在一天前 DEL 还是一个 OIer 吧。
不过这里大概很快就被人忘记了吧。
给一棵以 1 号点为根的树。每一个点有一些怪，移动速度和在 1 号点的人一样。
对每一个终点，问最多碰到多少怪。
裸的长链剖分。
听了题解以及跟 @whj 讨论了一下，其实只需两遍 dfs。一遍收集深度$\times2$，另一遍收集深度$\times2-2$.
#include <bits/stdc++.h>
using namespace std;
template<class T>
inline void read(T&x)
{
T p = 1, n = 0; char c = getchar();
while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T, class U>inline void read(T&x,U&y){read(x), read(y);}
template<class T,class U,class V>inline void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 1e5 + 10;
struct E{int v, n;}e[maxn << 1];
int h[maxn], ec = 1;
inline void add_edge(int u, int v)
{
e[ec] = (E){v, h[u]};
h[u] = ec++;
e[ec] = (E){u, h[v]};
h[v] = ec++;
}
int depth[maxn], size[maxn], hson[maxn], maxd[maxn];
void dfs(int u = 1, int f = 0)
{
size[u] = 1; hson[u] = 0;
maxd[u] = depth[u];
for(int i = h[u], v = e[i].v ;i; i = e[i].n, v = e[i].v)
if(v != f)
{
depth[v] = depth[u] + 1, dfs(v, u);
size[u] += size[v];
if(maxd[v] > maxd[hson[u]]) maxd[u] = maxd[v], hson[u] = v;
}
}
int w[maxn], a[maxn];
bool flag[maxn];
void collect(int u, int f)
{
w[depth[u]] += a[u];
for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v)
if(v != f && !flag[v])
collect(v, u);
}
int ans[maxn];
void dfs2(int u = 1, int f = 0, bool ff = false)
{
for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v)
if(v != f && v != hson[u])
dfs2(v, u, true);
if(hson[u])
{
dfs2(hson[u], u, false);
flag[hson[u]] = 1;
}
collect(u, f);
ans[u] = w[depth[u] * 2 - 2] + w[depth[u] * 2 - 1];
if(ff)
{
memset(w, 0, sizeof w);
memset(flag, 0, sizeof flag);
}
}
void dfs3(int u = 1, int f = 0)
{
for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f)
ans[v] += ans[u], dfs3(v, u);
}
int main()
{
freopen("escape.in", "r", stdin);
freopen("escape.out", "w", stdout);
int n; read(n);
for(int i = 1; i <= n; ++i) read(a[i]);
for(int i = 1, u, v; i < n; ++i) read(u, v), add_edge(u, v);
depth[1] = 1; dfs();
dfs2();
dfs3();
for(int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
return 0;
}定义 $ f_k(n)=f_{k-1}*1(n)=\sum_{d|n} f_{k-1}(d) $ . 给 $ x,k,f_0 $ ， 求 $ f_k(n) $ .
卷积满足结合律，考虑使用快速幂计算 $ 1^k $ ，其中乘法定义为卷积。要注意到只求某一项的值，这一项的因数级别在 $ O(n^{3/4}) $ （@whj 语），所以可以过。
还有一种使用牛顿级数的做法。
注意到 $ 1^k=\sum_i{k\choose i}(\Delta^i1^x)^0 $ ，$ k $ 很小且 $ (\Delta^i1^x)^0(v) $ 是很容易预处理出来的。
#include <bits/stdc++.h>
using namespace std;
template<class T>
inline void read(T&x)
{
T p = 1, n = 0; char c = getchar();
while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T, class U>inline void read(T&x,U&y){read(x), read(y);}
template<class T,class U,class V>inline void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 1e5 + 10, mod = 998244353;
int f[maxn], a[maxn], tmp[maxn], ret[maxn], t2[maxn], ac;
int calc(int k)
{
for(int i = 0; i < ac; ++i) ret[a[i]] = 0;
ret[1] = 1;
for(int i = 0; i < ac; ++i) t2[a[i]] = 1;
for(; k; k >>= 1)
{
if(k & 1)
{
for(int i = 0; i < ac; ++i) tmp[a[i]] = 0;
for(int i = 0; i < ac; ++i) for(int j = 0; j <= i; ++j) if(a[i] % a[j] == 0)
(tmp[a[i]] += 1ll * ret[a[j]] * t2[a[i] / a[j]] % mod) %= mod;
for(int i = 0; i < ac; ++i) ret[a[i]] = tmp[a[i]];
}
for(int i = 0; i < ac; ++i) tmp[a[i]] = 0;
for(int i = 0; i < ac; ++i) for(int j = 0; j <= i; ++j) if(a[i] % a[j] == 0)
(tmp[a[i]] += 1ll * t2[a[j]] * t2[a[i] / a[j]] % mod) %= mod;
for(int i = 0; i < ac; ++i) t2[a[i]] = tmp[a[i]];
}
}
int main()
{
freopen("machine.in", "r", stdin);
freopen("machine.out", "w", stdout);
int n; read(n);
for(int i = 1; i <= n; ++i) read(f[i]);
int m; read(m);
while(m--)
{
int k, x; read(k, x);
ac = 0;
for(int i = 1; i * i <= x; ++i) if(x % i == 0)
{
a[ac++] = i;
if(i * i != x) a[ac++] = x / i;
}
sort(a, a + ac);
calc(k);
int ans = 0;
for(int i = 0; i < ac; ++i) (ans += 1ll * f[a[i]] * ret[x / a[i]] % mod) %= mod;
printf("%d\n", ans);
}
return 0;
}交互题。
一棵二叉树，每条边有颜色，告诉你现在的起点深度。你可以调用 move 使用某一颜色的边，query 查询当前点深度，你要跳到深度为 0 的点。
100 分初始深度为 $10^5$ 要求 query 调用不超过 $51000$ 次， move 调用不超过 $ 10^6 $ 次。
每次走 $ 6 $ 步，分类讨论 $ 2^6=64 $ 种情况。期望每次询问能跳 $ 63\over32 $ 步，能过。其实写丑了，根本不必要手写讨论。
#include "maze.h"
int seed = 20180323, x = 3;
int rrand()
{
return (x = (x + seed + x % 41 * seed % 41) % 41) % 32;
}
int excl(int i, int j)
{
if(i != 0 && j != 0) return 0;
if(i != 1 && j != 1) return 1;
if(i != 2 && j != 2) return 2;
}
int fi[100], se[100], th[100], fo[100], fif[100], six[100];
void findpath(int initialDeep, int T)
{
if(!query()) return;
int last = -1; bool flag = false;
for(int i = 0; i < 2; ++i)
{
if(move(i)) return;
if(query() > initialDeep) move(i);
else {last = i; flag = true; break;}
}
if(!flag) move(2), last = 2;
int curdep = initialDeep - 1;
while(curdep > 4)
{
int cnt = 0;
for(int i = 0; i <= 2; ++i) if(i != last)
{
for(int ii = 0; ii < 32; ++ii)
fi[cnt + ii] = i;
for(int j = 0; j <= 2; ++j) if(j != i)
{
for(int jj = 0; jj < 16; ++jj)
se[cnt + jj] = j;
for(int k = 0; k <= 2; ++k) if(k != j)
{
for(int kk = 0; kk < 8; ++kk) th[cnt + kk] = k;
for(int l = 0; l <= 2; ++l) if(l != k)
{
for(int ll = 0; ll < 4; ++ll) fo[cnt + ll] = l;
for(int m = 0; m <= 2; ++m) if(m != l)
{
for(int mm = 0; mm < 2; ++mm) fif[cnt + mm] = m;
for(int n = 0; n <= 2; ++n) if(n != m)
six[cnt++] = n;
}
}
}
}
}
int pa = rrand();
move(fi[pa]); move(se[pa]); move(th[pa]); move(fo[pa]); move(fif[pa]); move(six[pa]);
int d = query();
if(d == curdep + 6)
move(six[pa]), move(fif[pa]), move(fo[pa]), move(th[pa]), move(se[pa]), move(fi[pa]), move(last = excl(fi[pa], last)), curdep -= 1;
else if(d == curdep + 4)
move(six[pa]), move(fif[pa]), move(fo[pa]), move(th[pa]), move(se[pa]), move(last = excl(se[pa], fi[pa])), curdep -= 2;
else if(d == curdep + 2)
move(six[pa]), move(fif[pa]), move(fo[pa]), move(th[pa]), move(last = excl(th[pa], se[pa])), curdep -= 3;
else if(d == curdep)
move(six[pa]), move(fif[pa]), move(fo[pa]), move(last = excl(fo[pa], th[pa])), curdep -= 4;
else if(d == curdep - 2)
move(six[pa]), move(fif[pa]), move(last = excl(fif[pa], fo[pa])), curdep -= 5;
else if(d == curdep - 4)
move(six[pa]), move(last = excl(six[pa], fif[pa])), curdep -= 6;
else
last = six[pa], curdep -= 6;
}
if(curdep == 0) return;
for(int i = curdep; i; --i)
{
bool flag = false;
for(int j = 0; j < 2; ++j) if(j != last)
{
move(j);
if(query() > i)
{
move(j);
if(last == 2) {move(1), last = 1, flag = true; break;}
}
else {last = j; flag = true; break;}
}
if(!flag) move(2), last = 2;
}
}即便是原题大战又怎样。。还是菜到打不出来QAQ
给出一个长度为 m 的序列 A, 请你求出有多少种 1..n 的排列, 满足 A 是它的一个 LIS.
$ 1\le m\le n\le15 $ .
考虑需要的信息。保证合法性需要对答案有贡献的序列的 LIS 信息（A 在 LIS 的信息显然包括其中），转移需要局部已处理的集合的信息。
LIS 数组满足单调性，可以将之压为二进制状态。
$ f_{S, S_0} $ 表示考虑了集合 $ S $ ，LIS 信息为 $ S_0 $ 的合法方案数。又注意到恒有 $ S_0\subset S $ ，所以用一个三进制描述这个状态即可。复杂度 $ O(n^23^n) $ .
要注意使用了标准化技术后转移拓扑序和下标的顺序是不一致的。要用个队列保存转移。
转移时精致一点。。打错了好多。。
#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
char c = getchar(); T p = 1, n = 0;
while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 20, maxm = 1.5e7;
int a[maxn], A[maxn], pow3[maxn], log3[maxm];
bool flag[maxn];
long long dp[maxm] = {0};
queue<int> q[maxn];
int main()
{
freopen("arg.in", "r", stdin);
freopen("arg.out", "w", stdout);
int n, m; read(n, m);
for(int i = 0; i < m; ++i) read(a[i]), --a[i], flag[a[i]] = 1;
pow3[0] = 1; for(int i = 1; i <= n; ++i) pow3[i] = pow3[i - 1] * 3;
for(int i = 1; i < pow3[n]; ++i) log3[i] = log3[i / 3] + 1;
int N = pow3[n];
dp[0] = 1; q[0].push(0);
long long ans = 0;
for(int i = 0; i < n; ++i)
{
while(!q[i].empty())
{
int S = q[i].front(); q[i].pop();
bool f = false;
for(int j = 0; j < n; ++j) if((S / pow3[j]) % 3 == 0)
{
f = true;
int T = S + 2 * pow3[j];
for(int k = j + 1; k < n; ++k) if((T / pow3[k]) % 3 == 2)
{
T -= 1 * pow3[k];
break;
}
int cnt = 0, ac = 0;
for(int k = 0; k < n; ++k)
{
if((T / pow3[k]) % 3 == 2) ++cnt;
if((S / pow3[k]) % 3 != 0 && k == a[ac]) ++ac;
}
if(!flag[j])
{
if(cnt <= m)
{
if(!dp[T]) q[i + 1].push(T);
dp[T] += dp[S];
}
}
else
{
if(cnt > m || a[ac] != j) continue;
if(!dp[T])q[i + 1].push(T);
dp[T] += dp[S];
}
}
}
}
while(!q[n].empty()) ans += dp[q[n].front()], q[n].pop();
printf("%lld\n", ans);
return 0;
}给定一个正 n 边形及其三角剖分, 共 2n − 3 条边 (n 条多边形的边和 n − 3 条对角线), 每条边
的长度为 1.
共 q 次询问, 每次询问给定两个点, 求它们的最短距离.
强烈抗议出原题。当时还跟 mhx 讨论了一个下午。思路实在太妙就记了下来。
平面图、网格图上很多特殊性质可以利用。分治是其中要考虑的。
一棵树上 A 和 B 轮流给结点对应染红色蓝色。A 要使红蓝联通块差大， B 使小。问最后整棵树的联通块差。
记 $ S_A/S_B/E_A/E_B $ 为各颜色点数和同色边数，则联通块数有 $ S_A $
……把福利赛打成退役赛吗……
无向图，判断五元环。$ |V|\le200 $ .
一直在往 dfs 树的返祖边考虑……但其实不能这么做。
枚举一个点和一条边后，剩下就是要看这个点和这条边的两个端点是否各存在一个公共邻点。这个可以用 bitset 加速判定。据说不用也可以过。复杂度是 $ \mathcal O({n^4\over 64}) $ .
实现的时候要注意两个端点都要有一条连出去的点且不能是对方。
其实这个问题我在之前辗转反侧的夜晚考虑过数次。但今天刚好忘了得出来的结论是返祖边不能做或者至少不好做。而判断三元环、四元环这些经典问题都是直接用 bitset 。我似乎对经典题毫无察觉。学到了学到了。
考虑一下六元环怎么做？三元环计数怎么做？
给出一个集合，可重复抽三个数。已知最后各个数的组成方案数，求复原原集合或不可能。$ |U|\le6 $ .
注意这是一个集合异或卷积的三次方…… FWT 一下看看原幂级数合不合法存不存在就可以了……
细节很多。比方说域的特征不能为 $ 2 $ ，最后所有数的和要为 $ n $ ，不能出现负数，行末不能有空格，立方根可能不是整数。
想到这个思路应该很简单的啊……应该说意识还不够……不熟练？一直往 DP 方向想，可是要是写出状压式子不久完了吗…………菜爆。
求所有点对的最小瓶颈路径。$ |V|\le10^5 $ .
套路 MST. 然后我建出这棵树后就开始取最大边来边分了……T爆。
实际上由一个技巧，就是注意到连接两个连通块时我们并不关心是哪两个点具体连边。那么在并查集上直接维护子树 tag 即可。不带路径压缩比较好写，但是每次加边多带一个 $ \log $ . 总的时间是 $ \mathcal O(n\log n) $ ，全部瓶颈在于排序。
一行 $ N $ 个白色的球，每次等概率随机一个区间 $ [L,R] $ 将这些染黑。问期望多少次染黑所有球。
@CLJ 的题。计数问题选讲的课件里有。
可知题目所求为 $ \mathbb{E}[\max_{i=1}^nX_i] $ ，其中 $ X_i $ 表示这个位置被染黑的时间，由期望的线性性和 maximum-minimums identity 有
$$ \mathbb E[\max_{i=1}^n X_i]=\sum_{S\sub[n]}(-1)^{|S|-1} \mathbb{E}[\min_{i\in S}X_i] $$
问题变为怎么求 $ \mathbb E[\min_{i\in S} X_i] $ ，这表示第一次染到 $ S $ 这个集合的期望时间，其等于 $ {{n+1\choose2}\over A} $ ，其中 $ A $ 为覆盖 $ S $ 中至少一个点的区间个数。
考虑递推算这个东西。 $ f_{i,s,b} $ 表示考虑前 $ i $ 个白球，黑球（未覆盖）区间数为 $ s $ 且黑球的奇偶性为 $ b $ （容斥用）的的时间，则有
$$ f_{i,s,b}=\sum_{j}f_{j,s-{i-j\choose2},b\oplus1} $$
那么 $ \mathbb{E}[\max_{i=1}^n X_i]={n+1\choose2}\sum_{i}{f_{i,t,1}-f_{i,t,0}\over{n+1\choose2}-t-{n-i+1\choose2}} $ .
原题要高精度小数……懒得写了……
#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
char c = getchar(); T p = 1, n = 0;
while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
#define G(n) (((n) * (n + 1)) >> 1)
long long f[55][2555][2];
int main()
{
int t; read(t);
while(t--)
{
int n; read(n);
memset(f, 0, sizeof f);
f[0][0][0] = 1;
for(int i = 1; i <= n; ++i) for(int j = 0; j < i; ++j) for(int s = G(i - j - 1); s <= G(i); ++s)
f[i][s][0] += f[j][s - G(i - j - 1)][1], f[i][s][1] += f[j][s - G(i - j - 1)][0];
long double ans = 0, tot = G(n);
for(int i = 1; i <= n; ++i) for(int s = 0; s <= G(i); ++s) if(f[i][s][1] - f[i][s][0] != 0)
ans += tot * (f[i][s][1] - f[i][s][0]) / (tot - s - G(n - i));
printf("%.15Lf\n", ans);
}
return 0;
}给一个串 $ s (|s|\le1000) $，找出任意一个回文串 $ S(|S|\le10000) $ ，使得 $ s $ 是 $ S $ 的子序列。
直接输出 $ s+rev(s) $.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e3 + 10;
char s[maxn];
int main()
{
scanf("%s", &s);
int len = strlen(s);
for(int i = 0; i < len; ++i) putchar(s[i]);
for(int i = len - 1; ~i; --i) putchar(s[i]);
return 0;
}$ f(n) $ 为非零的数位之积，
求 $g(i)=k,i\in[l,r] $ 的个数。
范围 $ Q \le 2\times10^5,1\le l\le r \le10^6,1\le k\le9 $.
打 $ f,g,h(l,k):=\sum_{i\le l} [g(i)=k] $ 的表.
注意数位积与数位和不一样。比赛时我以为 $ g $ 对 $ f $ 满足结合律，实际上是分配律（把数拆成数位之间连接的是加法）。数位和的性质过于良好，等价于在 $ \mod 9 $ 意义下的值，以至于我想当然了。被卡了很久。
要多长点心眼，遇到这种题要把“理所当然”的结论再验证一遍。不过也暴露出我找反例的能力有点弱，应该找最可能出现反例的地方想的。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
using namespace std;
template<class T> void read(T& x)
{
char c = getchar(); T p = 1, n = 0;
while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 1e6 + 10;
int g[maxn], cnt[maxn][10], prod[maxn];
int main()
{
memset(cnt, 0, sizeof cnt);memset(g, 0, sizeof g);
for(int i = 1; i < 10; ++i)
{
memcpy(cnt[i], cnt[i - 1], sizeof cnt[i]);
g[i] = prod[i] = i;
cnt[i][g[i]] ++;
}
for(int i = 10; i < maxn; ++i)
{
memcpy(cnt[i], cnt[i - 1], sizeof cnt[i]);
g[i] = g[prod[i] = prod[i / 10] * (i % 10 == 0 ? 1 : i % 10)];
cnt[i][g[i]]++;
}
int q; read(q);
while(q--)
{
int l, r, k; read(l, r, k);
printf("%d\n", cnt[r][k] - cnt[l - 1][k]);
}
return 0;
}找出 $ P $ 的一个排列，定义
， $ g(i):=\min\{j:f(i,j)=i\} $.
给定 $ N\le10^6,A,B $ ，使得对所有 $ i\in[1,n],~g(i)=A\text{ or } B $.
容易看出这是将一个排列分解为长度为 $ A $ 或 $ B $ 的置换。
解同余方程或者暴力枚出这俩的系数，然后循环移位一下即是合法构造。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
char c = getchar(); T p = 1, n = 0;
while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
int main()
{
int n, a, b; read(n, a, b);
int ti = -1;
for(int i = 0; i <= n / a; ++i)
{
if((n - i * a) % b == 0)
{
ti = i;
break;
}
}
if(ti == -1) {puts("-1"); return 0;}
int tj = (n - ti * a) / b;
for(int i = 0; i < ti; ++i) for(int j = 1; j <= a; ++j)
printf("%d ", i * a + (j) % a + 1);
for(int i = 0; i < tj; ++i) for(int j = 1; j <= b; ++j)
printf("%d ", ti * a + i * b + (j) % b + 1);
return 0;
}初始给一个点 $ 1 $ ，权值为 $ 0 $ 。有两种操作，
询问 $ \le 4\times 10 ^5 $, 权值 $ \le 10^{18} $.
建一棵按题意形态的原树，一棵新树。原数维护倍增表，找出第一个大于当结点权值的祖先，返回作为其新树的父亲。在新树上同样维护倍增表，询问时二分即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
char c = getchar(); T p = 1, n = 0;
while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 4e5 + 100;
long long ww[maxn];
namespace T1
{
long long w[maxn][20]; int fa[maxn][20];
int check(int u, long long v)
{
for(int i = 19; ~i; --i) if(w[u][i] < v) u = fa[u][i];
if(ww[u] >= v) return u; else return fa[u][0];
}
void add(int u, int f)
{
fa[u][0] = f, w[u][0] = ww[u];
for(int i = 1; i < 20; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1], w[u][i] = max(w[fa[u][i - 1]][i - 1], w[u][i - 1]);
}
}
namespace T2
{
int fa[maxn][20], dep[maxn];
long long w[maxn][20];
inline void add(int u, int f)
{
fa[u][0] = f, w[u][0] = ww[u];
dep[u] = dep[f] + 1;
for(int i = 1; i < 20; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1], w[u][i] = w[u][i - 1] + w[fa[u][i - 1]][i - 1];
}
int check(int u, long long x)
{
int du = dep[u];
for(int i = 19; ~i; --i) if(w[u][i] <= x) x -= w[u][i], u = fa[u][i];
return du - dep[u];
}
}
//long long
int main()
{
T2::dep[1] = 1;
int q; read(q);
long long last = 0, cnt = 1;
while(q--)
{
long long t, p, q; read(t, p, q); p ^= last, q ^= last;
if(t == 1)
{
ww[++cnt] = q;
int ti = T1::check(p, ww[cnt]);
T1::add(cnt, p);
T2::add(cnt, ti);
}
else
{
printf("%d\n", last = T2::check(p, q));
}
}
return 0;
}给出 $ n \le 10^9, k\le 5000 $ ，求 $ \sum {n \choose i} i ^k $.
我们注意到和这个形式相像的式子即为二项式展开 $ (1+x)^n=\sum {n \choose i} x^i $。
这启发我们一定可以从这个式子变形得到原式，我们考虑求导补次，即 $ x[(1+x)^n]' = \sum {n \choose i} ix^{i} $。
发现如此操作 $ k $ 次后得到的式子令 $ x=1 $ 即为我们需要的答案。
我们有 $ x {\mathrm{d}\over\mathrm{d}x} (x^a(1+x)^b) = ax^a(1+x)^b+bx^{a+1}(1+x)^{b-1} $ ，写出递推方程，$ f_{k,a,b} = af_{k-1,a,b}+bf_{k-1,a+1,b-1} $ ，记忆化搜索一遍可得答案，注意判断 $ a,b $ 为 $0 $ 的情况。
这个虽然看起来时是三维的，但注意到后两维和为定值，这降了一维。
继续沿用求导的思路，但我们不补次，于是得到 $ [(1+x)^n]^{(k)} = n^{\underline k}(1+x)^{n-k}=\sum{n \choose i} i^{\underline k}x^{i-k} $.
一个自然而然的想法是使用第二类把幂表示成下降幂，即 $ \sum \left\{ \begin{matrix} n \\ k\end{matrix} \right\} x^{\underline k} = x^n $.
从而 $ \sum_i {n \choose i} i^k = \sum_i{n \choose i}\sum_j \left\{\begin{matrix}k \\ j\end{matrix}\right\} i^{\underline j} = \sum_j \left\{\begin{matrix}k \\ j\end{matrix}\right\} \sum_i {n \choose i}i^{\underline j} = \sum_j \left\{\begin{matrix}k \\ j\end{matrix}\right\} [n^{\underline j}(1+x)^{n-j}]_{x=1} $.
第二类可以 $ O(k^2) $ 预处理，下降幂 $ O(k) $ 预处理，$ 2 $ 的幂 $ O(\lg n) $ 直接计算。总的复杂度仍然是 $ O(k^2) $.
同样注意 $ n-j $ 小于等于 $ 0 $ 的情况。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
char c = getchar(); T p = 1, n = 0;
while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 5000 + 10, mod = 1e9 + 7;
long long power(long long a, long long b)
{
long long ret = 1;
for(; b; b >>= 1, (a *= a) %= mod) if(b & 1)
(ret *= a) %= mod;
return ret;
}
long long dp[maxn][maxn];
long long cal(int k, int a, int n)
{
if(~dp[k][a]) return dp[k][a];
if(k == 0) return dp[k][a] = power(2, n - a);
int b = n - a;
return dp[k][a] = ((a ? 1ll * (a) % mod * cal(k - 1, a, n) % mod : 0) + (b ? 1ll * (b) % mod * cal(k - 1, a + 1, n) % mod : 0)) % mod;
}
int main()
{
int n, k; read(n, k);
memset(dp, -1, sizeof dp);
printf("%d\n", cal(k, 0, n));
}#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
char c = getchar(); T p = 1, n = 0;
while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int mod = 1e9 + 7, maxn = 5000 + 5;
long long power(long long a,long long b){long long ret = 1;for(; b; b >>= 1, (a *= a) %= mod) if(b & 1) (ret *= a) %= mod; return ret;}
long long S[maxn][maxn], D[maxn];
int main()
{
int n, k; read(n, k);
S[0][0] = 1;
for(int i = 1; i <= k; ++i) for(int j = 1; j <= i; ++j)
S[i][j] = (S[i - 1][j - 1] + j * S[i - 1][j] % mod) % mod;
D[0] = n;
for(int i = 1; i <= k; ++i) D[i] = (n - i) * D[i - 1] % mod;
int ret = 0;
for(int i = 1; i <= min(n, k); ++i)
(ret += S[k][i] * D[i - 1] % mod * power(2, n - i) % mod) %= mod;
printf("%d\n", ret);
return 0;
}