结束了

DEL 至少作为一个 OIer 已经死去了。

省选退役。
第一天代码版本没有核对好,交了个一半的,丢了100.
第二天读入优化写错。windows 拍不出错 linux RE. 200 全没有.
我的竞赛生涯就是笑话。

有了这 400 分会怎样?
那么多“如果”漏了出来。如果我把那天的咖喱全都吃光是不是好一点。

抱歉。真的抱歉。
只能走到一半,就走不下去了。
我尽力了可是运气不站在我这边。当时我在逞能。现在我也是。


有几十篇存货一起放上来吧。排版大概是不会排的了。更新也不会更了。
为了方便都设为了前一天的日期。也算是纪念至少在一天前 DEL 还是一个 OIer 吧。
不过这里大概很快就被人忘记了吧。

雅礼省赛集训 2018 Sol.

雅礼省赛集训 2018 Sol.

3.23

T1

给一棵以 1 号点为根的树。每一个点有一些怪,移动速度和在 1 号点的人一样。

对每一个终点,问最多碰到多少怪。

Sol.

裸的长链剖分。

听了题解以及跟 @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;
}

T2

定义 $ f_k(n)=f_{k-1}*1(n)=\sum_{d|n} f_{k-1}(d) $ . 给 $ x,k,f_0 $ , 求 $ f_k(n) $ .

Sol.

卷积满足结合律,考虑使用快速幂计算 $ 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;
}

T3

交互题。

一棵二叉树,每条边有颜色,告诉你现在的起点深度。你可以调用 move 使用某一颜色的边,query 查询当前点深度,你要跳到深度为 的点。

100 分初始深度为 $10^5$ 要求 query 调用不超过 $51000$ 次, move 调用不超过 $ 10^6 $ 次。

Sol.

每次走 $ 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;
    }
}

3.25

即便是原题大战又怎样。。还是菜到打不出来QAQ

A

给出一个长度为 m 的序列 A, 请你求出有多少种 1..n 的排列, 满足 A 是它的一个 LIS.

$ 1\le m\le n\le15 $ .

Sol.

考虑需要的信息。保证合法性需要对答案有贡献的序列的 LIS 信息(A 在 LIS 的信息显然包括其中),转移需要局部已处理的集合的信息。

LIS 数组满足单调性,可以将之压为二进制状态。

$ f_{S, S_0} $ 表示考虑了集合 $ S $ ,LIS 信息为 $ S_0 $ 的合法方案数。又注意到恒有 $ S_

要注意使用了标准化技术后转移拓扑序和下标的顺序是不一致的。要用个队列保存转移。

转移时精致一点。。打错了好多。。

#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;
}

B

给定一个正 n 边形及其三角剖分, 共 2n − 3 条边 (n 条多边形的边和 n − 3 条对角线), 每条边
的长度为 1.
共 q 次询问, 每次询问给定两个点, 求它们的最短距离.

Sol.

强烈抗议出原题。当时还跟 mhx 讨论了一个下午。思路实在太妙就记了下来。

平面图、网格图上很多特殊性质可以利用。分治是其中要考虑的。

3.30

table

program

path

4.2

c

一棵树上 A 和 B 轮流给结点对应染红色蓝色。A 要使红蓝联通块差大, B 使小。问最后整棵树的联通块差。

Sol.

记 $ S_A/S_B/E_A/E_B $ 为各颜色点数和同色边数,则联通块数有 $ S_A $

计蒜客20180415 Sol.

计蒜客20180415 Sol.

……把福利赛打成退役赛吗……

B

无向图,判断五元环。$ |V|\le200 $ .

一直在往 dfs 树的返祖边考虑……但其实不能这么做。

枚举一个点和一条边后,剩下就是要看这个点和这条边的两个端点是否各存在一个公共邻点。这个可以用 bitset 加速判定。据说不用也可以过。复杂度是 $ \mathcal O({n^4\over 64}) $ .

实现的时候要注意两个端点要有一条连出去的点且不能是对方。

其实这个问题我在之前辗转反侧的夜晚考虑过数次。但今天刚好忘了得出来的结论是返祖边不能做或者至少不好做。而判断三元环、四元环这些经典问题都是直接用 bitset 。我似乎对经典题毫无察觉。学到了学到了。

考虑一下六元环怎么做?三元环计数怎么做?

C

给出一个集合,可重复抽三个数。已知最后各个数的组成方案数,求复原原集合或不可能。$ |U|\le6 $ .

注意这是一个集合异或卷积的三次方…… FWT 一下看看原幂级数合不合法存不存在就可以了……

细节很多。比方说域的特征不能为 $ 2 $ ,最后所有数的和要为 $ n $ ,不能出现负数,行末不能有空格,立方根可能不是整数。

想到这个思路应该很简单的啊……应该说意识还不够……不熟练?一直往 DP 方向想,可是要是写出状压式子不久完了吗…………菜爆。

G

求所有点对的最小瓶颈路径。$ |V|\le10^5 $ .

套路 MST. 然后我建出这棵树后就开始取最大边来边分了……T爆。

实际上由一个技巧,就是注意到连接两个连通块时我们并不关心是哪两个点具体连边。那么在并查集上直接维护子树 tag 即可。不带路径压缩比较好写,但是每次加边多带一个 $ \log $ . 总的时间是 $ \mathcal O(n\log n) $ ,全部瓶颈在于排序。

HDU 4624 期望

HDU 4624 期望

一行 $ N $ 个白色的球,每次等概率随机一个区间 $ [L,R] $ 将这些染黑。问期望多少次染黑所有球。

Sol.

@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}} $ .

原题要高精度小数……懒得写了……

Code

#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;
}

Codeforces #463 Sol.

Codeforces #463 Sol.

A

给一个串 $ s (|s|\le1000) $,找出任意一个回文串 $ S(|S|\le10000) $ ,使得 $ s $ 是 $ S $ 的子序列。

Sol.

直接输出 $ s+rev(s) $.

Code

#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;
}

B

$ f(n) $ 为非零的数位之积,

img

求 $g(i)=k,i\in[l,r] $ 的个数。

范围 $ Q \le 2\times10^5,1\le l\le r \le10^6,1\le k\le9 $.

Sol.

打 $ f,g,h(l,k):=\sum_{i\le l} [g(i)=k] $ 的表.

注意数位积与数位和不一样。比赛时我以为 $ g $ 对 $ f $ 满足结合律,实际上是分配律(把数拆成数位之间连接的是加法)。数位和的性质过于良好,等价于在 $ \mod 9 $ 意义下的值,以至于我想当然了。被卡了很久。

要多长点心眼,遇到这种题要把“理所当然”的结论再验证一遍。不过也暴露出我找反例的能力有点弱,应该找最可能出现反例的地方想的。

Code

#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;
}

C

找出 $ P $ 的一个排列,定义img , $ g(i):=\min{j:f(i,j)=i} $.

给定 $ N\le10^6,A,B $ ,使得对所有 $ i\in[1,n],~g(i)=A\text{ or } B $.

Sol.

容易看出这是将一个排列分解为长度为 $ A $ 或 $ B $ 的置换。

解同余方程或者暴力枚出这俩的系数,然后循环移位一下即是合法构造。

Code

#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;
}

D

初始给一个点 $ 1 $ ,权值为 $ 0 $ 。有两种操作,

  1. 在 $ p $ 下面接一个下一个编号的点,权值为 $ q $.
  2. 询问 $ p $ 的祖先序列中的最长不降权值且和不超过 $ q $ 的长度最长长度。

询问 $ \le 4\times 10 ^5 $, 权值 $ \le 10^{18} $.

Sol.

建一棵按题意形态的原树,一棵新树。原数维护倍增表,找出第一个大于当结点权值的祖先,返回作为其新树的父亲。在新树上同样维护倍增表,询问时二分即可。

Code

#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;
}

E

给出 $ n \le 10^9, k\le 5000 $ ,求 $ \sum {n \choose i} i ^k $.

Sol. 1

我们注意到和这个形式相像的式子即为二项式展开 $ (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 $ 的情况。

这个虽然看起来时是三维的,但注意到后两维和为定值,这降了一维。

Sol. 2

继续沿用求导的思路,但我们不补次,于是得到 $ [(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 $ 的情况。

Code 1

#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));
}

Code 2

#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;
}

2018shijiebei w88 18luck 188bet beplay manbet 12bet 95zz shenbo weide1946 ca88 88bifa aomenxinpujing betway bodog bt365 bwin tongbao vwin weinisiren zuqiutouzhu