March

你的问题主要是读书不多而想的太多。
——杨绛先生


Table of Contents


Forewords

我去年说想搞一个代码折叠的东西或者把代码托管到别的地方,太占地方了。
咕咕咕咕咕咕咕咕咕?

等我闲下来想想办法。

3-10

T1 网格 Grid

先手玩一下样例

样例

考虑如何暴力。经过一番观察,我们令如图的几个X号称为联通的。更具体地,是蓝X使得两个红X连通。蓝叉(x,y)向x行和y列的所有X连了边。蓝叉的存在限制住了同行列的红叉。对于每一对红叉,它对应的蓝叉必须被限制住。

img

那么一个图是STABLE的当且仅当所有的X都联通并且没有任何一行一列没有X。因为这时候它才被架住了。证明.....比较复杂。。。就是列几个关于角度的式子推一推....

暴力就是给格子连边,......这样你就有了70分。然后优化是我们开n + m个点,行和列之间连边,美滋滋。

然后这道题就变成了动态维护连通性的一个题,由于没有强制在线,没必要lct,可以选择更好写的线段树分治。注意卡常......

全局的边可以先路径压缩掉,然后剩下的按秩合并。

注意叶子节点的处理.......

另外为什么我的暴力炸掉了呢QAQ?因为我都是大写X。。。(题目是小写x)

// この俺は、狂気のマッドサイエンティスト、鳳凰院凶真!世界は、この俺の手の中にある!
# include <bits/stdc++.h>
 
using namespace std;
 
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define REPG(i, h, x) for(int i = h[x]; ~i; i = edge[i].next)
 
const int N = 3e3 + 3, M = 2e5 + 3;
 
# define u tr[x]
# define ls (x << 1)
# define rs (x << 1 | 1)
# define uls tr[ls]
# define urs tr[rs]
 
# define mp make_pair
# define pii pair<int, int>
# define pb push_back
# define fir first
# define sec second
 
# define gc getchar
inline int rd() {
    char ch = gc(); int ret = 0, sgn = 1;
    while(ch < '0' || ch > '9') { if(ch == '-') sgn = -1; ch = gc(); }
    while(ch <= '9' && ch >= '0') ret = ret * 10 + ch - '0', ch = gc();
    return ret * sgn;
}
 
vector<pii > tr[M << 2];
 
int n, m, q;
char buf[N][N];
 
int vis[N][N], ans[M];
int f[M << 1], tp, T, sz[N << 1];
 
pii stk[M];
 
int tot = 0;
inline int gfs(int x) { return f[x] == x ? f[x] : f[x] = gfs(f[x]); }
void merge(int x, int y) {
    int f1 = gfs(x), f2 = gfs(y);
    if(f1 != f2) { 
        if(sz[f1] > sz[f2]) swap(f1, f2);
      
        f[f1] = f2, sz[f2] += sz[f1];
        -- tot;
    }
}
 
inline int gf(int x) { return f[x] == x ? f[x] : gf(f[x]); }
inline void lk(int x, int y) {
    int f1 = gf(x), f2 = gf(y);
    if(f1 != f2) { 
        if(sz[f1] > sz[f2]) swap(f1, f2);
        f[f1] = f2, sz[f2] += sz[f1];
      
        stk[++ tp] = mp(f2, f1); -- tot;
    }
}
 
 
void undo(int l) {
    while(tp > l) {
        int f1 = stk[tp].sec, f2 = stk[tp --].fir;
      
        sz[f2] -= sz[f1], f[f1] = f1;
        ++ tot;
    }
}
 
void dfs(int x, int l, int r) {
    int tmp1 = tp;
    for(int i = 0; i < u.size(); ++ i) lk(u[i].fir, u[i].sec);//, puts("wtf");
  
    if(l == r) { ans[l] = (tot == 1); return ; }
    int mid = l + r >> 1;
     
    int tmp2 = tp;
    dfs(ls, l, mid), undo(tmp2);
 
    dfs(rs, mid + 1, r), undo(tmp1);
}
 
void ins(int x, int l, int r, int ql, int qr, pii v) {
    if(l >= ql && r <= qr) { u.pb(v); return ; } 
  
    int mid = l + r >> 1;
    if(ql <= mid) ins(ls, l, mid, ql, qr, v);
    if(qr > mid) ins(rs, mid + 1, r, ql, qr, v);
}
 
int main() {
    CLR(ans, -1), CLR(vis, -1);
     
    n = rd(), m = rd(), q = rd();
    T = n + m; 
    tot = T;
    REP(i, 1, T) f[i] = i, sz[i] = 1;
 
    REP(i, 1, n) scanf("%s", buf[i] + 1);
    REP(i, 1, n) REP(j, 1, m) {
        if(buf[i][j] == 'x') vis[i][j] = 0;
    }

    REP(i, 1, q) {
        int x = rd(), y = rd();
        if(buf[x][y] == 'x') {
            ins(1, 0, q, vis[x][y], i - 1, mp(x, n + y));
            vis[x][y] = i;
            buf[x][y] = '.';
        }
        else vis[x][y] = i, buf[x][y] = 'x';
    }
    REP(i, 1, n) REP(j, 1, m) if(buf[i][j] == 'x') {
        if(vis[i][j] != q && vis[i][j] != 0) ins(1, 0, q, vis[i][j], q, mp(i, n + j));
        if(vis[i][j] == 0) merge(i, n + j);//, puts("noo");
    }
     
    dfs(1, 0, q);
    REP(i, 0, q) 
        if(ans[i] == 0) puts("U");
        else if(ans[i] == 1) puts("S");
 
    return 0;
}

T2 汉诺塔 Hanoi

首先一整坨到另一坨的步数结论是$2^n - 1$

然后先想想subtask怎么办。

先想想最后合并成一整坨的。

我们先猜一下能不能还是按照最大块的一个一个往上放,恩,想想是对的,因为这是最大块的,那么剩下所有比它小的就必须摞成一整坨,没有别的选择。

然后如果是从一整坨分裂出去呢?

发现其实步数和从目标状态合并成一整坨是一样的。

现在你就拿到了20分。(另外的20分暴力)

然后终点分散的怎么办呢?考虑从大到小来,因为我们每次移最大块的时候,那些比它小的块没有选择,它只能摞成一大坨,然后就变成了上面那个问题了。

现在的问题就是第一步的策略。我们来猜猜它能不能还按照原来的策略,n-1块:T -> buffer,最大块:S -> T。

然后你试了试样例发现它过不了= =。因为它最后不一定要合并起来,我们上面提到的策略的正确性基于,它最后一定要合并起来,所以左边的n-1大小的一坨和右边的最大块他们必须经过中间这个点(不然它们怎么并起来。。。),所以对于最后不合并的情况这不一定是最优的,手玩了样例我们发现我们要讨论的情况其实是要考虑,到底是谁先去buffer。也就是对于两种情况的讨论:

  1. 最大块直接过去
  2. 最大块和剩下的坨互换位置。

所以实际上我们只需要分类讨论第一步怎么走,剩下的块正常走,然后比个大小输出方案。

然后事儿还没完。

你发现要高精度。不过由于我们的加法都是2的整次幂,维护一下二进制形式比较一下就行了。

# include <bits/stdc++.h>
 
using namespace std;
 
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
 
const int N = 1e6 + 3, MOD = 998244353;
 
int s[N], t[N], n;
int a[N], b[N];
 
void dfs(int x, int to, int *c, int *fr) {
    if(!x) return ;
    if(to == fr[x]) { dfs(x - 1, to, c, fr); return; }
    dfs(x - 1, 3 - to - fr[x], c, fr);
    ++ c[x - 1];
}
 
int main() {
    scanf("%d", &n);
    init();
    while(s[n] == t[n] && n) -- n;
     
    dfs(n - 1, 3 - s[n] - t[n], a, s);
    ++ a[0];
    dfs(n - 1, 3 - s[n] - t[n], a, t);
 
    dfs(n - 1, t[n], b, s);
    ++ b[0], ++ b[n - 1];
    dfs(n - 1, s[n], b, t);
 
    REP(i, 0, n) a[i + 1] += a[i] >> 1, a[i] %= 2, b[i + 1] += b[i] >> 1, b[i] %= 2;
 
    int flg = 0, ans = 0;
    REPD(i, n, 0) if(a[i] != b[i]) {
        flg = a[i]; break;
    }
         
        if(!flg) REPD(i, n, 0) ans = (ans * 2 + a[i]) % MOD;
        else REPD(i, n, 0) ans = (ans * 2 + b[i]) % MOD;
        printf("%d\n", ans);
    return 0;
}

T3 根式演算 Rad

好毒瘤......

其实我很好奇这套题谁出的。

1
2
3
4



2333

2018-03-12

ps:昨天题是gjs出的,今天的题是hgr大爷出的(小h,小g,小r2333333)

T1 游戏

容易看出问题实际上是求一段区间内的元素是否线性相关。

然后又一个事情就是你发现元素个数超了阶数肯定就先行性管了。。所以实际上区间的长度是一个log级别的东西。。所以我们甚至单点枚举都是log方的,剩下的就是处理修改了。

^操作非常好处理。剩下的这可咋整呢,tag如何合并。

仔细观察后发现,|,&其实可以看作一个覆盖操作。影响答案的要么是1变0,要么是0变1.那么我们记两个tag分别表示每一位如果是0或1的话分别是什么结果。

具体可以看代码的pushdown。

所以实际上数据结构的tag确实就是维护元素如何变化。。。

// この俺は、狂気のマッドサイエンティスト、鳳凰院凶真!世界は、この俺の手の中にある!
struct node { 
    int t0, t1; 
    node() { t0 = 0, t1 = INF; }
} tr[N << 2];
 
# define u tr[x]
# define ls (x << 1)
# define rs (x << 1 | 1)
# define uls tr[ls]
# define urs tr[rs]
 
int n, q, a[N], bas[35];
 
void pd(int x) {
    uls.t0 = (uls.t0 & u.t1) | ((uls.t0 ^ INF) & u.t0);
    uls.t1 = (uls.t1 & u.t1) | ((uls.t1 ^ INF) & u.t0);
    urs.t0 = (urs.t0 & u.t1) | ((urs.t0 ^ INF) & u.t0);
    urs.t1 = (urs.t1 & u.t1) | ((urs.t1 ^ INF) & u.t0);
    u.t0 = 0, u.t1 = INF;
}
 
void modify(int x, int l, int r, int ql, int qr, int v, int op) {
    if(ql <= l && qr >= r) {
        if(op == 1) u.t0 &= v, u.t1 &= v;
        else if(op == 2) u.t0 |= v, u.t1 |= v;
        else if(op == 3) u.t0 ^= v, u.t1 ^= v;
        return ;
    }
    pd(x);
    int mid = l + r >> 1;
    if(ql <= mid) modify(ls, l, mid, ql, qr, v, op);
    if(qr > mid) modify(rs, mid + 1, r, ql, qr, v, op);
}
 
int query(int x, int l, int r, int p) {
    if(l == r) return (a[l] & u.t1) | ((a[l] ^ INF) & u.t0);
    pd(x);
    int mid = l + r >> 1;
    if(p <= mid) return query(ls, l, mid, p);
    else return query(rs, mid + 1, r, p);
}
 
int merge(int x) {
        REPD(i, 30, 0) if((x & (1 << i))) {
            if(bas[i]) x ^= bas[i];
            else return bas[i] = x, 1;
        }
        return 0;
}
 
int main() {
    n = rd();
    REP(i, 1, n) a[i] = rd();
    q = rd();
    while(q --) {
        int op = rd(), l = rd(), r = rd(), x;
        if(op == 0) {
            CLR(bas, 0); int flg = 0;
            if(r - l + 1 > 30) puts("Yes");
            else { 
                REP(i, l, r) {
                    int val = query(1, 1, n, i);
                    if(!merge(val)) { puts("Yes"); flg = 1; break; }
                }
                if(!flg) puts("No");
            }
        }
        else {
            x = rd();
            modify(1, 1, n, l, r, x, op);
        }
    }
 
    return 0;
}

T2 朋友

好一个阅读题。。。QAQ

我们仔细阅读一波题面,发现有感情的串其实是后缀树上被缩起来的那些边,也就是SAM上有着相同子树的部分,因为首先a要是b的子串,而且a不能有多余的出现位置,那么表示它们了。

然后再来看一个认识的关系,实际上就是到达当前状态的整个转移路径。

现在的问题就转化成了用几条从根节点开始的路径上其余点不相交的trans路径覆盖整个SAM。

由于它要求最小答案,所以我们拆点之后上下界都设为1跑网络流就行了。

关于带上下界的最小流,第一遍是从SS和TT跑(这时T到S有一条INF),这一步要判是否有解(限制边满流这时T到S的边的流量就是这时的流量。然后拆掉独立的供给和消费边,跑T到S的网络流,然后用之前的结果减去当前的结果。

当前的结果可能比之前的结果要大,这就代表着这个残留网络内部还有更多的空间可以给我们调整。

最后题解说得挺好的

题解

// この俺は、狂気のマッドサイエンティスト、鳳凰院凶真!世界は、この俺の手の中にある!
# define u tr[x]
# define o tr[y]
# define v u.trans[c]
# define vn tr[v]
 
struct node { int trans[S_ + 1], p, l; } tr[N << 1];
 
int rt, tot;
char buf[N];
 
int t[N][S_ + 1], k, m, n, ttot, id[N];
 
inline int ins(int c, int lst) {
    int x = lst, y = ++ tot; lst = y;
 
    o.l = u.l + 1;
    for(; !v && x; x = u.p) v = y;
 
    if(!x) o.p = rt;
    else if(vn.l == u.l + 1) o.p = v;
    else {
        int z = ++ tot;
        memcpy(tr[z].trans, vn.trans, sizeof(tr[z].trans));
        tr[z].p = vn.p, vn.p = o.p = z;
        tr[z].l = u.l + 1;
        for(int ori = v; v == ori && x; x = u.p) v = z;
    }
    return y;
}
 
# undef u 
# undef o 
# undef v 
# undef vn 
 
struct qwq { int v, next, f; } edge[(N * 2) * 5 << 1];
queue<int> q;
int d[N << 2], cur[N << 2], head[N << 2], cnt = -1, out[N << 2], in[N << 2], ss, tt, S, T, SS, TT;
 
inline void add(int u, int v, int f) {
//  printf("%d->%d, %d id:%d\n", u, v, f, cnt + 1);
    edge[++ cnt] = (qwq) { v, head[u], f }, head[u] = cnt;
    edge[++ cnt] = (qwq) { u, head[v], 0 }, head[v] = cnt;
}
 
inline void adde(int u, int v, int up, int dw) {
    if(up - dw) add(u, v, up - dw);
    in[v] += dw, out[u] += dw;
}
 
int bfs() {
    CLR(d, -1);
    q.push(S), d[S] = 0; 
    while(!q.empty()) {
        int x = q.front(); q.pop();
         
        REPG(i, head, x) {
            v = edge[i].v;
            if(edge[i].f && d[v] == -1) q.push(v), d[v] = d[x] + 1;
             
        }
    }
    return d[T] != -1;
}
 
int dfs(int x, int f) {
    int usd = 0, ff;
    if(x == T) return f;
 
    for(int &i = cur[x], v; ~i; i = edge[i].next) { 
        if(edge[i].f && d[(v = edge[i].v)] == d[x] + 1 && (ff = dfs(v, min(f, edge[i].f)))) 
            edge[i].f -= ff, edge[i ^ 1].f += ff, usd += ff, f -= ff; 
        if(f == 0) break;
    }
 
    if(!usd) d[x] = -1; // !!!
    return usd;
}
 
int dinic() {
    int ret = 0;
 
    while(bfs()) {
        memcpy(cur, head, sizeof(head)); 
        ret += dfs(S, INF); 
    }
    return ret;
}
 
int spe[N << 2];
void solve() {
    CLR(head, -1), CLR(spe, -1);
    ss = 0, tt = tot << 1 | 1; 
    SS = tt + 1, TT = SS + 1;
 
    REP(i, 1, k) if(tr[1].trans[i]) add(ss, tr[1].trans[i], 1);
    REP(x, 2, tot) {
        REP(c, 1, k) if(tr[x].trans[c]) add(tot + x, tr[x].trans[c], 1);//, puts("wtf");
        adde(x, tot + x, 1, 1);
        add(tot + x, tt, 1);
    }
 
    REP(x, 2, tt - 1) {
        if(in[x]) spe[x] = cnt + 1, add(SS, x, in[x]);
        if(out[x]) spe[x] = cnt + 1, add(x, TT, out[x]);
    }
    int rev = cnt + 1;
    int tmpp = rev;
    add(tt, ss, INF);
    S = SS, T = TT;
    int ans1 = dinic();
     
    ans1 = edge[tmpp ^ 1].f;//min(, 
    REP(i, 2, tt - 1) { 
//      printf("%d %d %d\n", i, spe[i], edge[spe[i]].f);  
        if(edge[spe[i]].f) puts("0"), exit(0); 
    }
     
//  cout<<ans1<<endl;
    edge[rev].f = edge[rev ^ 1].f = 0;
    S = tt, T = ss;
    int ans2 = dinic();
 
    if(ans2 > ans1) puts("ERR");
    else printf("%d\n", ans1 - ans2);
}
 
void pre() {
    q.push(1);
    while(!q.empty()) {
        int x = q.front(); q.pop();
        REP(i, 1, k) if(t[x][i]) {
            q.push(t[x][i]), id[t[x][i]] = ins(i, id[x]);
        }
    }
}
 
int main() {
//  freopen("1.in", "r", stdin);
     
    k = rd(), m = rd(), ttot = 1;
    rt = ++ tot, id[rt] = tot;
 
    REP(i, 1, m) {
        int x = 1; n = rd();
        REP(j, 1, n) {
            int c = rd();
            if(!t[x][c]) t[x][c] = ++ ttot;
            x = t[x][c];
        } 
    }
     
    pre();
//  REP(i, 1, tot) REP(c, 1, k) printf("[%d,%d]:%d\n", i, c, tr[i].trans[c]);
    solve();
 
    return 0;
}

T3 多项式

。。。。

先放个题解存着。。。

多项式1

多项式2

上下界网络流复习

= =.....

无源汇

没有什么可说的....就是建边有两种方式。一种是看差,一种是直接记in[x],out[x]。

有源汇可行流

INF边的反向流量即为答案

对于看差的建边方式的正确性理解,可以看成是差分。

有源汇最大流

先满足下界求出可行流,然后删除INF边加上s到t自由流的部分。

不过其实我们并不用删边23333333333,不删边的话最后INF的反向边就直接是答案了。

因为我们的答案实际上是一开始的反向边流量再加上自由流。而不删边的自由流肯定把一开始的反向边流量直接加上去了。

有源汇最小流

先满足下界求出可行流,然后删除INF边减去t到s自由流的部分。

这两个能这么做是因为S和T一定已经流满了,边都走不了,他们就不会被增广到。

上下界费用流

下界的费用最后再手算。所以费用设成0,剩下的都一样了。

3-13

T1 信仰圣光

题目脸上就摆着几个大字,“分治NTT”,然后当时不会。。。

瓶颈在于合并两个环的复杂度。。。。

所以这道题就列出来生成函数的式子然后直接分治NTT,或者合并果子也行。。。不过好像合并果子没有分治NTT快,一开始我写的合并果子。。。。最后几个点T掉了。。我压了压NTT的常数还是有一个点T,分治直接过了。。。

需要。。。练习一波。。生成函数。。。

.....想想我真是一个傻逼。。

合并果子:

# include <bits/stdc++.h>
  
using namespace std;
  
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPG(i, h, x) for(int i = h[x], v; ~i; i = edge[i].next)
  
# define gc getchar
inline int rd() {
    char ch = gc(); int ret = 0;
    while(ch < '0' || ch > '9') ch = gc();
    while(ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0', ch = gc();
    return ret;
}
  
typedef long long LL;
const int N = 152501 + 2, M = N << 1, FR = 524288 + 3, MOD = 998244353; 
   
int a[FR], b[FR];
int len, n; 
int f[FR], g[FR], rot[FR][2], rev[FR];
  
int fac[N], invfac[N], invlen;
inline int pow_(int x, int k) {
    int ret = 1;
    while(k) {
        if(k & 1) ret = 1ll * ret * x % MOD;
        x = 1ll * x * x % MOD;
        k >>= 1;
    }
    return ret;
}
inline int binom(int x, int y) { return 1ll * fac[x] * invfac[y] % MOD * invfac[x - y] % MOD; }
int inv(int x) { return pow_(x, MOD - 2); }
void pre() {
    fac[0] = 1;
    REP(i, 1, N - 1) fac[i] = 1ll * fac[i - 1] * i % MOD;
    invfac[N - 1] = inv(fac[N - 1]);
    REPD(i, N - 2, 0) invfac[i] = 1ll * invfac[i + 1] * (i + 1) % MOD; 
}
  
void init() {
    int inv3 = inv(3);
        for(int i = 2; i < FR; i <<= 1) {
                rot[i][0] = pow_(3, (MOD - 1) / i);
                rot[i][1] = pow_(inv3, (MOD - 1) / i);
        }
}
  
void FFT(int *F, int len, int op) {
    REP(i, 0, len - 1) if(i < rev[i]) swap(F[i], F[rev[i]]);
    for(int i = 2; i <= len; i <<= 1) { // length
        int wn = rot[i][op];
        for(int j = 0; j < len; j += i) { // start pos
            int w = 1;
            for(int k = 0; k < i / 2; ++ k, w = 1ll * w * wn % MOD) { 
                int u = F[j + k], t = 1ll * F[j + k + i / 2] * w % MOD;
                F[j + k] = (u + t) % MOD; 
                F[j + k + i / 2] = (u - t + MOD) % MOD;
  
            }
        }
    }
    if(op) REP(i, 0, len - 1) F[i] = 1ll * F[i] * invlen % MOD;
}
  
int tot, pool[N], hh[N], k;
vector<int> co[N];
void convolution(int *A, int *B, int x, int y) {
    REP(j, 0, pool[x]) A[j] = co[x][j]; // 注意可以按照需要改成0
    REP(i, pool[x] + 1, len - 1) A[i] = 0;
    REP(j, 0, pool[y]) B[j] = co[y][j];
    REP(i, pool[y] + 1, len - 1) B[i] = 0;
   
    FFT(A, len, 0); FFT(B, len, 0);
    REP(i, 0, len - 1) A[i] = 1ll * A[i] * B[i] % MOD;
    FFT(A, len, 1);
}
   
inline void rader(int l) {
    for (len = 1; len <= l; len <<= 1);
    REP(i, 1, len) rev[i] = (i & 1) ? ((rev[i >> 1] >> 1) ^ (len >> 1)) : (rev[i >> 1] >> 1);
    invlen = inv(len);
}
  
struct gg { bool operator()(int a, int b) { return pool[a] > pool[b]; } };
priority_queue<int, vector<int>, gg> q;
int vis[N], tim;
  
void clear() {
    ++ tim; 
    REP(i, 1, tot) co[i].clear();
    tot = 0;
}
int main() {
//  freopen("1.in", "r", stdin);
    ++ tim;
    pre(), init();
    int t = rd();
    while(t --) { 
        n = rd(), k = rd();
        REP(i, 1, n) hh[i] = rd();
        REP(i, 1, n) if(vis[i] != tim) {
            int sz = 0, x;
            for(x = i; vis[x] != tim; x = hh[x]) 
                vis[x] = tim, ++ sz;
            pool[++ tot] = sz;
            co[tot].resize(pool[tot] + 1);
            if(x == i) REP(j, 1, sz) co[tot][j] = binom(sz, j);
            else {
                co[tot][1] = 1;
                REP(j, 2, sz) co[tot][j] = binom(sz - 1, j - 1);
            }
        } 
        if(tot > k) { puts("0"); clear(); continue; } 
        REP(i, 1, tot) q.push(i);
        while(q.size() > 1) {
            int x = q.top(); q.pop();
            int y = q.top(); q.pop();
            pool[++ tot] = pool[x] + pool[y]; co[tot].resize(pool[tot] + 1);
            rader(pool[tot]);
            a[0] = b[0] = 0;
            convolution(f, g, x, y);
            REP(i, 1, pool[tot]) co[tot][i] = f[i];
            q.push(tot);
        }
//      cout<<q.size()<<endl;
        int x = q.top();
        q.pop();
        int ans = (1ll * co[x][k] * inv(binom(n, k)) % MOD + MOD) % MOD;
        printf("%d\n", ans);
        clear();
    }   
    return 0;
}

分治NTT:

# include <bits/stdc++.h>
 
using namespace std;
 
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPG(i, h, x) for(int i = h[x], v; ~i; i = edge[i].next)
 
# define gc getchar
inline int rd() {
    char ch = gc(); int ret = 0;
    while(ch < '0' || ch > '9') ch = gc();
    while(ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0', ch = gc();
    return ret;
}
 
typedef long long LL;
const int N = 152501 + 2, M = N << 1, FR = 524288 + 3, MOD = 998244353; 
  
int a[FR], b[FR];
int len, n; 
int f[FR], g[FR], rot[FR][2], rev[FR];
 
int fac[N], invfac[N], invlen;
inline int pow_(int x, int k) {
    int ret = 1;
    while(k) {
        if(k & 1) ret = 1ll * ret * x % MOD;
        x = 1ll * x * x % MOD;
        k >>= 1;
    }
    return ret;
}
inline int binom(int x, int y) { return 1ll * fac[x] * invfac[y] % MOD * invfac[x - y] % MOD; }
int inv(int x) { return pow_(x, MOD - 2); }
void pre() {
    fac[0] = 1;
    REP(i, 1, N - 1) fac[i] = 1ll * fac[i - 1] * i % MOD;
    invfac[N - 1] = inv(fac[N - 1]);
    REPD(i, N - 2, 0) invfac[i] = 1ll * invfac[i + 1] * (i + 1) % MOD; 
}
 
void init() {
    int inv3 = inv(3);
        for(int i = 2; i < FR; i <<= 1) {
                rot[i][0] = pow_(3, (MOD - 1) / i);
                rot[i][1] = pow_(inv3, (MOD - 1) / i);
        }
}
 
void FFT(int *F, int len, int op) {
    REP(i, 0, len - 1) if(i < rev[i]) swap(F[i], F[rev[i]]);
    for(int i = 2; i <= len; i <<= 1) { // length
        int wn = rot[i][op];
        for(int j = 0; j < len; j += i) { // start pos
            int w = 1;
            for(int k = 0; k < i / 2; ++ k, w = 1ll * w * wn % MOD) { 
                int u = F[j + k], t = 1ll * F[j + k + i / 2] * w % MOD;
                F[j + k] = (u + t) % MOD; 
                F[j + k + i / 2] = (u - t + MOD) % MOD;
            }
        }
    }
    if(op) REP(i, 0, len - 1) F[i] = 1ll * F[i] * invlen % MOD;
}
 
vector<int> co[N * 4];
int tot, pool[N * 4], hh[N], k;
void convolution(int *A, int *B, int x, int y) {
    REP(j, 0, pool[x]) A[j] = co[x][j]; // 注意可以按照需要改成0
    REP(i, pool[x] + 1, len - 1) A[i] = 0;
    REP(j, 0, pool[y]) B[j] = co[y][j];
    REP(i, pool[y] + 1, len - 1) B[i] = 0;
  
    FFT(A, len, 0); FFT(B, len, 0);
    REP(i, 0, len - 1) A[i] = 1ll * A[i] * B[i] % MOD;
    FFT(A, len, 1);
}
  
inline void rader(int l) {
    for (len = 1; len <= l; len <<= 1);
    REP(i, 1, len) rev[i] = (i & 1) ? ((rev[i >> 1] >> 1) ^ (len >> 1)) : (rev[i >> 1] >> 1);
    invlen = inv(len);
}
 
bool cmp(int x, int y) { return pool[x] < pool[y]; }
int wk[N];
int vis[N], tim;
 
int solve(int l, int r) {
    if(l == r) return wk[l];
    int mid = l + r >> 1;
    int x = solve(l, mid), y = solve(mid + 1, r);
    co[++ tot].resize(pool[x] + pool[y] + 1);
    pool[tot] = pool[x] + pool[y];
    rader(pool[tot]);
    convolution(f, g, x, y);
    REP(i, 1, pool[tot]) co[tot][i] = f[i];
    return tot;
}
 
void clear() {
    ++ tim; 
    REP(i, 1, tot) co[i].clear();
    tot = 0;
}
int main() {
//  freopen("1.in", "r", stdin);
    ++ tim;
    pre(), init();
    int t = rd();
    while(t --) { 
        n = rd(), k = rd();
        REP(i, 1, n) hh[i] = rd();
        REP(i, 1, n) if(vis[i] != tim) {
            int sz = 0, x;
            for(x = i; vis[x] != tim; x = hh[x]) 
                vis[x] = tim, ++ sz;
            pool[++ tot] = sz;
            co[tot].resize(pool[tot] + 1);
            if(x == i) REP(j, 1, sz) co[tot][j] = binom(sz, j);
            else {
                co[tot][1] = 1;
                REP(j, 2, sz) co[tot][j] = binom(sz - 1, j - 1);
            }
        } 
        if(tot > k) { puts("0"); clear(); continue; } 
         
        REP(i, 1, tot) wk[i] = i;
        sort(wk + 1, wk + tot + 1, cmp);
        int x = solve(1, tot);
//      cout<<q.size()<<endl;
        int ans = (1ll * co[x][k] * inv(binom(n, k)) % MOD + MOD) % MOD;
        printf("%d\n", ans);
        clear();
    }   
    return 0;
}

T2 装饰地板

。。满分做法怎么这么高级啊。

虽然我最后还是不懂它最后到底怎么做的

sro RogerDTZ

特征方程的学习

内容和这道题的解法没有特别特别大的关系。。。。。
好像找错资料了。。。学了一堆没有任何关系的内容23333333
这么说的话化零多项式还坑着。。。

以下说的是关于常系数线性齐次递推式的通项怎么求。

Reference

现在我们有了一个常系数线性齐次递推式,并且知道了它的前几项,怎么求通项呢。

考虑构造一个数列使得这个数列是若干个满足这个递推式的等比数列的线性组合(它们之间线性无关)。那么构造出来的这个数列也是满足这个递推式的。

一个令人非常头疼的事情是这个玩意儿它可能有好几阶。。。而且前几项的值也不太好确定。。那我们先把这个问题解决掉(也是我们选择等比数列的原因),假设我们知道这些等比数列都是什么,那么既然是线性组合,先将等比数列的值带进去,待定系数法求出对应系数,那么这个时候你惊奇地发现这个数列的通项居然被你求出来了,一切都这么美好。。。

你转头一想:不对啊,我从哪里知道哪些数列是符合要求的。

这时候特征方程就上场啦,它主要是依赖于我们选择了等比数列这样一个优秀的数列。

既然要满足递推式,那我们就直接不管系数,设公比为q,先把等比数列需要的项的值代进去,这时候,我们发现唯一存在的项就是第n项,两遍同除以它,这样这个k阶递推式就变成了一个k次方程啦!

每一个q的解都是一个合法公比。

当然。。。。。有的时候会出现重根。。。。。。

不过大部分情况下效果还是不错的。

T3 灵大会议

考场写挂打出GG。每个点维护$\sum dep_i \times val_i$和$\sum val_i$

dfs序不知道比树剖好写到哪里去了。。。

我树剖卡常死都过不去。。。。

// この俺は、狂気のマッドサイエンティスト、鳳凰院凶真!世界は、この俺の手の中にある!
# pragma GCC optimize(2)
# include <bits/stdc++.h>
   
using namespace std;
   
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define REPG(i, h, x) for(int i = h[x], v; ~i; i = edge[i].next)
   
typedef long long LL;
   
# define gc getchar
inline LL rd() {
    char ch = gc(); LL ret = 0, sgn = 1;
    while(ch < '0' || ch > '9') { if(ch == '-') sgn = -1; ch = gc(); }
    while(ch <= '9' && ch >= '0') ret = ret * 10 + ch - '0', ch = gc();
    return ret * sgn;
}
   
const int N = 152501 + 3, S = 18 + 1;
const LL INF = (1ll << 60);
   
struct node { 
    LL l;
    LL sum, x;
    node() { x = l = sum = 0; } 
} tr[N << 2];
   
struct qwq { LL v, next, c; } edge[N << 1];
LL head[N], cnt, n, val[N], dfn[N], id[N];
LL dis[N], dep[N];
inline void add(int u, int v, int c) { edge[++ cnt] = (qwq) { v, head[u], c }, head[u] = cnt; }
   
# define u tr[x]
# define ls (x << 1)
# define rs (x << 1 | 1)
# define uls tr[ls]
# define urs tr[rs]
   
inline void upd(int x) { u.sum = uls.sum + urs.sum, u.x = uls.x + urs.x; }
void build(int x, int l, int r) {
    if(l == r) {
        u.l = dis[id[l]], u.x = val[id[l]];
        u.sum = u.l * u.x;
        return ;
    }
    LL mid = l + r >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    upd(x);
}
   
void modify(int x, int l, int r, int p, LL v) {
    if(l == r) { u.x = v; u.sum = u.l * u.x; return ; }
    int mid = l + r >> 1;
    if(p <= mid) modify(ls, l, mid, p, v);
    else modify(rs, mid + 1, r, p, v);
    upd(x);
}
   
# define fir first
# define sec second
# define mp make_pair
# define pii pair<LL, LL>
void merge(pii &x, pii y) { x.fir += y.fir, x.sec += y.sec; }
pii qry(int x, int l, int r, int ql, int qr) {
    if(ql <= l && qr >= r) return mp(u.sum, u.x);
    int mid = l + r >> 1;
    pii ret = mp(0, 0);
    if(ql <= mid) merge(ret, qry(ls, l, mid, ql, qr));
    if(qr > mid) merge(ret, qry(rs, mid + 1, r, ql, qr));    
    return ret;
}
LL tp[N], son[N], sz[N], tim, fa[N], anc[S][N], pw[S], fc[N];
   
void dfs0(int x) {
    sz[x] = 1;
    REPG(i, head, x) if((v = edge[i].v) != fa[x]){
        dep[v] = dep[x] + 1, dis[v] = edge[i].c + dis[x], fa[v] = x;
        fc[v] = edge[i].c;
        dfs0(v), sz[x] += sz[v];
        if(son[x] == -1 || sz[son[x]] < sz[v]) son[x] = v;
    }
}
   
void dfs1(int x, int top) {
    tp[x] = top, id[dfn[x] = ++ tim] = x;
    if(~son[x]) dfs1(son[x], top);
    REPG(i, head, x) if((v = edge[i].v) != fa[x] && v != son[x]) dfs1(v, v);
}
   
inline int lca(int x, int y) {
    for(; tp[x] != tp[y]; x = fa[tp[x]]) 
        if(dep[tp[x]] < dep[tp[y]]) swap(x, y);
    return dep[x] < dep[y] ? x : y;
}   
   
inline void pre() {
    REP(i, 1, n) anc[0][i] = fa[i];
    REP(i, 1, S - 1) REP(j, 1, n) anc[i][j] = anc[i - 1][anc[i - 1][j]];
}
   
int getpos(int pos, int x, int y, int z) { 
    if(pos == 1) return x;
    LL d = dep[x] + dep[y] - 2 * dep[z] + 1;
    if(pos == d) return y; 
    if(dep[x] - dep[z] + 1 >= pos) {
        -- pos; int kk = 0;
        for(; pos; pos >>= 1, ++ kk) if(pos & 1) x = anc[kk][x];
        return x;
    }
    else { 
        pos = d - pos; int kk = 0;
        for(; pos; pos >>= 1, ++ kk) if(pos & 1) y = anc[kk][y];
        return y;
    }
}
   
pii query(int x, int y) { 
//  printf("%d %d--\n", x, y);
    pii ret = mp(0, 0);
    if(dep[x] < dep[y]) swap(x, y);
    for(; tp[x] != tp[y]; x = fa[tp[x]]) {
        // pii tmp;
//      printf("%d %d pii\n", tp[x], tp[y]);
        merge(ret, qry(1, 1, n, dfn[tp[x]], dfn[x]));
        if(dep[tp[x]] < dep[tp[y]]) swap(x, y);
    }
    merge(ret, qry(1, 1, n, dfn[y], dfn[x])); 
    return ret;
} 
   
LL judge(int x, int y, int z, int pos) {
//  printf("%d %d %d %d", pos, x, y, dep[x] - dep[z] + 1);
    pos = getpos(pos, x, y, z);
    LL ret = 0;
    if(lca(x, pos) != pos) swap(x, y); 
    pii tmp = query(x, pos);
    ret += tmp.fir, ret -= tmp.sec * dis[pos];
    tmp = query(z, y);
    ret += tmp.fir, ret -= tmp.sec * dis[z];
    ret += (dis[pos] - dis[z]) * tmp.sec;
//  printf("%d pt2\n", ret);
    tmp = query(pos, z);
    ret -= tmp.fir, ret += dis[pos] * tmp.sec;
    ret -= (dis[pos] - dis[z]) * val[z];
    return ret;
}
   
LL calc(int x, int y, int z) {
    LL l = 1, r = dep[x] + dep[y] - 2 * dep[z] + 1, hh;
    if(dfn[x] > dfn[y]) swap(x, y);
    LL sum = query(x, z).sec + query(z, y).sec - val[z];
    while(l <= r) {
        LL mid = l + r >> 1; 
        LL pos = getpos(mid, x, y, z);
//      printf("pos:%d, %d\n", mid, getpos(mid, x, y, z));
        LL lll = lca(x, pos);
        LL tmp = query(x, lll).sec + query(lll, pos).sec - val[lll];
        if(tmp * 2 >= sum) r = mid - 1, hh = mid;
        else l = mid + 1;
    }
//  REP(l, 0, d - 1) ans = min(judge(x, y, z, l), ans), prLLf("%d ", judge(x, y, z, l)); puts("");
    return judge(x, y, z, hh);
}
void solve() {
    CLR(son, -1);
    dep[1] = 1, dfs0(1), dfs1(1, 1);
    build(1, 1, n);
    pre();
    LL q = rd();
    while(q --) {
        LL op = rd(), x = rd(), y = rd();
        if(op - 1) modify(1, 1, n, dfn[x], y), val[x] = y;
        else printf("%lld\n", calc(x, y, lca(x, y)));
    }
       
}
   
   
int main() {
//  freopen("1.in", "r", stdin);
       
    CLR(head, -1);
    n = rd(); 
    REP(i, 1, n) val[i] = rd();
    REP(i, 1, n - 1) {
        LL a = rd(), b = rd(), c = rd(); 
        add(a, b, c), add(b, a, c);
    }
    solve();
    return 0;
}

3-14

T1 数列

GD的大佬们好喜欢出数学题啊。。。

标算。。。。我数学太菜了T T

数列1

数列2

T2 基因

如果无修那就是个sb题。。。

树上SA搞搞然后主席树,也可以SAM之后主席树,反正怎么搞都可以。。。。。

可惜它有。

有怎么办。我在考场上想这个问题的时候还在想。。平衡树内应该不太会套东西了qaq应该是思路出了问题就没管了。。。

结果。。。。。

它标算真的是平衡树套平衡树。。。。

后缀平衡树是一个重量平衡树,所以里面可以套一些支持快速合并的数据结构,例如线段树或者红黑树。

std是sbt套pbds的红黑树,也可以替罪羊套treap。

非常。。日狗。。。

然后如果你套线段树的话。

52171381654

就问你有没有感受到出题人的恶意。。。(大雾)

可是宝宝不想写这种,平衡树套平衡树。

分块啊2333.

我们沿用SA的做法,二分+倍增哈希找lcp,新串到一定程度就重构主席树,否则一边主席树一边暴力。

做完了。。

# include <bits/stdc++.h>
  
using namespace std;
  
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define REPG(i, h, x) for(int i = h[x]; ~i; i = edge[i].next)
  
# define gc getchar
inline int rd() {
    char ch = gc(); int ret = 0, sgn = 1;
    while(ch < '0' || ch > '9') { if(ch == '-') sgn = -1; ch = gc(); }
    while(ch <= '9' && ch >= '0') ret = ret * 10 + ch - '0', ch = gc();
    return sgn * ret;
}
  
const int N = 8e4 + 3, S = 17, INF = 1e9, BLOCK = 2500;
const int B1 = 233, B2 = 10005, MOD1 = 998244353, MOD2 = 1e9 + 7;
  
inline int ty(char x) {
    if(x == 'A') return 1;
    if(x == 'T') return 2;
    if(x == 'C') return 3;
    if(x == 'G') return 4;
}
  
struct node {
    int ls, rs, sum;
    node() { ls = rs = sum = 0; }
} tr[N * 100];
int rt[N], a[N], head[N], cnt, anc[S + 1][N], g[S + 1][N], tot, stk[N], tp;
int ht[N], sa[N], rk[N], dep[N], h1[S + 1][N], h2[S + 1][N], n, m;
bool valid[N];
int pw1[S + 1], pw2[S + 1], pw[S + 1], lg[N], curlen;
struct qwq { int v, next, c; } edge[N];
inline void add(int u, int v, int c) { edge[++ cnt] = (qwq) { v, head[u], c }, head[u] = cnt; }
  
# define u tr[x]
# define o tr[y]
# define uls tr[u.ls]
# define urs tr[u.rs]
# define ols tr[o.ls]
# define ors tr[o.rs]
int qry(int x, int y, int l, int r, int ql, int qr) {
//  cout<<l<<"??"<<r<<":"<<u.sum - o.sum<<endl;
    if(qr >= r && ql <= l) return u.sum - o.sum;
    int mid = l + r >> 1;
    int ret = 0;
    if(ql <= mid) ret += qry(u.ls, o.ls, l, mid, ql, qr);
    if(qr > mid) ret += qry(u.rs, o.rs, mid + 1, r, ql, qr);
    return ret;
}
inline void upd(int x) { u.sum = uls.sum + urs.sum; }
void build(int &x, int y, int l, int r, int p) {
    x = ++ tot; u = o;
    if(l == r) { ++ u.sum; return ; }
    int mid = l + r >> 1;
    if(p <= mid) build(u.ls, o.ls, l, mid, p);
    else build(u.rs, o.rs, mid + 1, r, p);
    upd(x);
} 
# undef u 
# undef o 
  
void dfs(int x, int f) {
    REPG(i, head, x) {
        int v = edge[i].v, c = edge[i].c;
        anc[0][v] = x, h1[0][v] = c, h2[0][v] = c, dep[v] = dep[x] + 1;
        dfs(v, x);
    }
}
  
bool cmp(int x, int y) {
    int dx = dep[x], dy = dep[y];
    REPD(i, S, 0) if(dx >= pw[i] && dy >= pw[i] && anc[i][y] && h1[i][x] == h1[i][y] && h2[i][x] == h2[i][y]) 
        dx -= pw[i], dy -= pw[i], x = anc[i][x], y = anc[i][y];
      
//  cout << x << "?"<<y<<"??"<<(char)h1[0][x]<<" "<<(char)h1[0][y] << endl;
    if(!dx && !dy) return x < y;
    if(!dx || !dy) return dx < dy;
    return h1[0][x] < h1[0][y];
}
  
int lcp(int x, int y) {
    int ret = 0, dx = dep[x], dy = dep[y];
    REPD(i, S, 0) if(dx >= pw[i] && dy >= pw[i] && anc[i][y] && h1[i][x] == h1[i][y] && h2[i][x] == h2[i][y]) 
        dx -= pw[i], dy -= pw[i], ret |= pw[i], x = anc[i][x], y = anc[i][y];
    return ret;
}
  
void bd() { 
    REP(i, 2, n) sa[i - 1] = i;
    curlen = n - 1;
    sort(sa + 1, sa + curlen + 1, cmp);
//  REP(i, 1, n) REP(j, 1, n) cout<<cmp(i, j)<<" "<<i<<","<<j<<endl;
    REP(i, 1, curlen) rk[sa[i]] = i;
    REP(i, 1, curlen - 1) ht[i] = lcp(sa[i], sa[i + 1]), g[0][i] = ht[i];
  
    REP(i, 1, S) REP(j, 1, n) if(j + pw[i] - 1 <= n) {   
        g[i][j] = min(g[i - 1][j + pw[i - 1]], g[i - 1][j]);
    }
      
    REP(i, 1, n) rt[i] = 0;
    REP(i, 1, tot) tr[i] = node();
    tot = 0;
    rt[0] = 0;
    REP(i, 1, curlen) build(rt[i], rt[i - 1], 0, INF, a[sa[i]]);
    REP(i, 1, n) valid[i] = 1;
    tp = 0;
}
  
int getmn(int x, int y) {
    if(x > y) swap(x, y);
    if(x == y) return dep[x];
//  ++ x;
    -- y;
    int l = y - x + 1;
    int k = lg[l];
    return min(g[k][x], g[k][y - pw[k] + 1]);
} 
  
void init() {
    pw1[0] = B1, pw2[0] = B2, pw[0] = 1;
    lg[1] = 0;
    REP(i, 2, N - 3) lg[i] = lg[i >> 1] + 1;
    REP(i, 1, S) {
        pw1[i] = 1ll * pw1[i - 1] * pw1[i - 1] % MOD1;
        pw2[i] = 1ll * pw2[i - 1] * pw2[i - 1] % MOD2;
        pw[i] = pw[i - 1] << 1;
    } 
    REP(i, 1, S) REP(j, 1, n) if(dep[j] >= pw[i]) {
        anc[i][j] = anc[i - 1][anc[i - 1][j]];
        h1[i][j] = (h1[i - 1][j] * pw1[i - 1] % MOD1 + 1ll * h1[i - 1][anc[i - 1][j]]) % MOD1;
        h2[i][j] = (h2[i - 1][j] * pw2[i - 1] % MOD2 + 1ll * h2[i - 1][anc[i - 1][j]]) % MOD2;
    }
    bd();
}
  
char buf[N];
  
void solve() {
    int msk = 1;
    while(m --) {
        int op = rd();
        if(op) {
            int f = rd(), v = rd(); scanf("%s", buf + 1);
            f ^= msk;
            anc[0][++ n] = f, dep[n] = dep[f] + 1, a[n] = v;
            h1[0][n] = h2[0][n] = ty(buf[1]);
            stk[++ tp] = n;
            REP(i, 1, S) if(dep[n] >= pw[i]) {
                anc[i][n] = anc[i - 1][anc[i - 1][n]];
                h1[i][n] = (h1[i - 1][n] * pw1[i - 1] % MOD1 + 1ll * h1[i - 1][anc[i - 1][n]]) % MOD1;
                h2[i][n] = (h2[i - 1][n] * pw2[i - 1] % MOD2 + 1ll * h2[i - 1][anc[i - 1][n]]) % MOD2;
            }
            if(tp == BLOCK) bd();
        }
        else {  
            int L, R, l, r, pos;
            int x = rd(), ql = rd(), qr = rd();
            x ^= msk;
            if(dep[x] < ql) { puts("0"); continue; } // ???????????????????????????????
//          cout<<ql<<"??"<<dep[x]<<endl;
            if(valid[x]) {
                pos = rk[x];
                L = pos, R = pos;
                   
                int l = 1, r = rk[x];
                while (l < r) {
                    int mid = l + r >> 1;
                    if (getmn(mid, rk[x]) >= ql) r = mid;
                    else l = mid + 1;
                }
            L = l;
                l = rk[x], r = curlen;
                while (l < r) {
                    int mid = l + r + 1 >> 1;
                    if (getmn(mid, rk[x]) >= ql) l = mid;
                    else r = mid - 1;
                }
                R = l;
            }
            else {
                int l = 1, r = curlen, pos = curlen + 1;
        while(l < r) {
            int mid = l + r >> 1;
            if(cmp(sa[mid], x)) l = mid + 1;
            else r = mid;
        }
        pos = l;
                int lcpL = pos > 1 ? lcp(sa[pos - 1], x) : -1;
                int lcpR = pos <= curlen ? lcp(sa[pos], x) : -1;
                   
                L = pos, R = pos - 1;
                if (lcpL >= ql) {
                    l = 1, r = pos - 1;
                    while (l < r) {
                        int mid = l + r >> 1;
                        if (min(lcpL, getmn(mid, pos - 1)) >= ql) r = mid;
                        else l = mid + 1;
                    }
                    L = l;
                }
                   
                if (lcpR >= ql) {
                    l = pos, r = curlen;
                    while (l < r) {
                        int mid = l + r + 1 >> 1;
                        if (min(lcpR, getmn(pos, mid)) >= ql) l = mid;
                        else r = mid - 1;
                    }
                    R = l;
                }
            }           
            int ans = 0;
//          printf("[%d, %d]\n", L, R);
            REP(i, 1, tp) if(a[stk[i]] <= qr && lcp(stk[i], x) >= ql) ++ ans;
            if(R >= L) ans += qry(rt[R], rt[L - 1], 0, INF, 0, qr);
            if(!ql && a[1] <= qr) ++ ans;
            printf("%d\n", ans);
            if(ans) msk = ans;
  
        }
    }
}
  
  
int main() {
//  freopen("1.in", "r", stdin);
//  freopen("mine.out", "w", stdout);
    CLR(head, -1);
    n = rd(), m = rd();
    REP(i, 1, n) a[i] = rd();
    REP(i, 1, n - 1) {
        int x = rd(), y = rd(); scanf("%s", buf + 1);
        add(x, y, ty(buf[1]));
    }
  
//  dep[1] = 1;
    dfs(1, 0);
  
    init();
//  REP(i, 1, curlen) cout<<sa[i]<<" "<<endl;
    solve();
    return 0;
}

分块

T3 学习

发现一个节点个数为x的团最大匹配为$\lfloor \frac{x}{2} \rfloor $

那么把图建出来求最大匹配就好了。。。

可惜边数太多qaq

有一种非常巧妙的构造。。。不在这里说了。题解有。

一般图最大匹配

主要看建图技巧。

带花树是坠吼的。

给一个彩色的 学习链接

相关题目坑着。。。

但我们今天不说这个。


苏凯树,苏凯大爷的一般图匹配方法.jpg

正确性依赖于出题人知不知道苏凯树。

(23333333333333333333333333333333333333333)

“是这样的,当时我们有一个题,10个点的一般图匹配。但我10个点用什么带花树嘛。。。”

具体方法其实就是。。。类似带花树不缩奇环直接xjb配一下(

int aug(int x) {
    vis[x] = tim;
    REPG(i, head, x) {
        int v = edge[i].v;
        if(!opn[v]) return opn[v] = x, opn[x] = v, 1;
        if(vis[opn[v]] != tim) {
            int tmp = opn[v];
            opn[tmp] = 0, opn[v] = x, opn[x] = v;
            if(aug(tmp)) return 1;
            opn[tmp] = v, opn[v] = tmp, opn[x] = 0;
        }
    }
    return 0;
}

凯


这个题的代码:

# include <bits/stdc++.h>
 
using namespace std;
 
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define REPG(i, h, x) for(int i = h[x]; ~i; i = edge[i].next)
 
const int N = 12000 + 3;
 
struct qwq { int v, next; } edge[N << 2];
int head[N], cnt;
inline void add(int u, int v) { edge[++ cnt] = (qwq) { v, head[u] }, head[u] = cnt; }
inline void add_edge(int u, int v) { add(u, v), add(v, u); }
 
int opn[N], vis[N], tim, n, m, tot;
#define Rep(i, n) for (int i = 1; i <= n; i ++)
int aug(int x) {
    vis[x] = tim;
    REPG(i, head, x) {
        int v = edge[i].v;
        if(!opn[v]) return opn[v] = x, opn[x] = v, 1;
        if(vis[opn[v]] != tim) {
            int tmp = opn[v];
            opn[tmp] = 0, opn[v] = x, opn[x] = v;
            if(aug(tmp)) return 1;
            opn[tmp] = v, opn[v] = tmp, opn[x] = 0;
        }
    }
    return 0;
}
 
 
int main() {
    while(~scanf("%d%d", &n, &m) && (n || m)) {
        CLR(opn, 0), cnt = 0, CLR(head, -1), tim = 0, CLR(vis, 0);
        tot = n;
        REP(tt, 1, m) {
            int c; scanf("%d", &c);
            int k = c + (c & 1);
            REP(i, 1, k - 1) add(tot + i, tot + i + 1), add(tot + i + 1, tot + i);
            add(tot + 1, tot + k), add(tot + k, tot + 1);
            REP(i, 1, c) {
                int x; scanf("%d", &x); 
                add(x, tot + i), add(tot + i, x);
                if(i + 1 <= k) add(x, tot + i + 1), add(tot + i + 1, x);
                else add(x, tot + 1), add(tot + 1, x);
            } 
            tot += k;
        }
        int ans = 0;
        REP(i, 1, tot) if(!opn[i]) {
            ++ tim; ans += aug(i);
        }
        printf("%d\n", ans - (tot - n) / 2);
    }
    return 0;
}

3-16

T1 Mythological V

2-sat。。。。

限制主要有树本身的限制:一个点不能分身,子树的包含关系,和选点的限制:不能多选,不能不选,不能同时选,直接在树上建点就好了。

// only for temporary testing, original code was created by bjbsz201705
# include <bits/stdc++.h>
   
#define REP(i, n) for (int i = 1; i <= n; i ++)
#define REP0(i, n) for (int i = 0; i <= n; i ++)
#define REPG0(i, x) for (int i = head[x]; i; i = edge[i].next)
#define v0 edge[i].to
#define REPG(i, x) for (int i = h1[x]; i; i = e1[i].next)
#define v e1[i].to
   
using namespace std;
  
const int N = 125010;
const int M = 40000100;
  
struct qwq{ int to, next;} edge[N], e1[M];
int head[N], cnt, n, m, q;
void add(int a, int b) { edge[++ cnt] = (qwq){b, head[a]}, head[a] = cnt;}
int h1[N], c1;
void add1(int a, int b) {  e1[++ c1] = (qwq){b, h1[a]}, h1[a] = c1;}
int id[255][255], idcnt, fa[N];
  
void dfs(int x, int f) {
    fa[x] = f;
    if (f){
        REP(i, m) {
            add1(id[x][i], id[f][i]);
            add1(id[f][i] ^ 1, id[x][i] ^ 1);
            //printf("_%d %d\n", x, f);
        }
    }
    REPG0(i, x) if (v0 != f) REPG0(j, x) if (v0 != edge[j].to && edge[j].to != f) {
        REP(k, m) add1(id[v0][k], id[edge[j].to][k] ^ 1);
        //printf("_%d %d\n", v0, edge[j].to);
        }
    REPG0(i, x) if (v0 != f) dfs(v0, x);
}
 bool instk[N];
int stk[N], tp, dfn[N], low[N], bel[N], belnum, tim;
  
void tarjan(int x) {
    //printf("%d\n", x);
    stk[++ tp] = x, low[x] = dfn[x] = ++ tim, instk[x] = 1;
    REPG(i, x){
    //  printf("%d : %d\n", x, v);
        if (!dfn[v]){ tarjan(v); low[x] = min(low[x], low[v]);}
        else if (instk[v]) low[x] = min(low[x], dfn[v]);
    }
    if (low[x] == dfn[x]) {
        belnum ++;
        do bel[stk[tp]] = belnum, instk[stk[tp]] = 0;
        while(stk[tp --] != x);
    }
}
  
int getid(int x, int f, int a) {
    REPG0(i, x) if (v0 != f && bel[id[v0][a]] < bel[id[v0][a] ^ 1])
        return getid(v0, x, a);
    return x;
}
  
int main() {
    scanf("%d%d%d", &n, &m, &q);
    REP(i, n - 1) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y); add(y, x);
    }
    REP(i, n) REP(j, m) id[i][j] = idcnt, idcnt += 2;
    dfs(1, 0);
    REP(i, q) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        REPG0(j, c) if (edge[j].to != fa[c]){
            add1(id[edge[j].to][a], id[edge[j].to][b] ^ 1);
            add1(id[edge[j].to][b], id[edge[j].to][a] ^ 1);
        }
        add1(id[c][a] ^ 1, id[c][b]);
        add1(id[c][b] ^ 1, id[c][a]);
    }
    REP(i, n) add1(id[1][i] ^ 1, id[1][i]);
    REP0(i, idcnt - 1) if (!dfn[i]) tarjan(i);
    REP(i, m) printf("%d ", getid(1, 0, i));
    //printf("%d %d %d\n", i, bel[id[i][3]], bel[id[i][3] ^ 1]);
      
    return 0;
}

T2 Mythological IV

只会插值的暴力做法。。。

部分分插值就好了。。。

具体插值的相关学习内容在笔记本上qaq

3-18

T1 Lcm

等我写完了回来。。坑着。

T2 求和

没什么可说的。。。直接反演。。。。。

然后学习了一下杜教筛。。。

那个phi的技巧其实是。。。因为直接用gcd反演你发现就是这个狮子233333

另外关于为什么sigma phi(n的因数)=n,考虑对化简$\frac{x}{n}$后的分母分类,最简分数$\frac{a}{b}$在上面出现的话,当且仅当$b|n$且$(a,b)=1$。 那么以b为分母的分数共$\varphi(b)$个。

杜教筛

ヾ(✿゚▽゚)ノ

好困啊。。。果然不应该过了好几天之后再写题解。。变懒了。。。

反正重点是理解为什么复杂度之展开一层以及如何利用卷积构造一个更好求前缀和的函数。

# include <bits/stdc++.h>
 
using namespace std;
 
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define REPG(i, h, x) for(int i = h[x]; ~i; i = edge[i].next)
 
typedef long long LL;
const int N = 1e6 + 3;
 
# define gc getchar
inline LL rd() {
    char ch = gc(); LL ret = 0, sgn = 1;
    while(ch < '0' || ch > '9') { if(ch == '-') sgn = -1; ch = gc(); }
    while(ch <= '9' && ch >= '0') ret = ret * 10 + ch - '0', ch = gc();
    return sgn * ret;
}
 
LL MOD, n, vis[N], phi[N], p[N], tot, inv6, ans, inv2;
bool isnotp[N];
 
inline LL pow_(LL x, LL k) {
    LL ret = 1;
    for(; k; k >>= 1, x = 1ll * x * x % MOD)
        if(k & 1) ret = 1ll * ret * x % MOD;
    return ret;
}
 
inline void inc(LL &x, LL y) { x = (x + y) % MOD; }
inline void dec(LL &x, LL y) { x = ((x - y) % MOD + MOD) % MOD; }
inline LL getsum(LL r) { return 1ll * r * (r + 1) % MOD * 1ll * (r * 2 + 1) % MOD * inv6 % MOD; }
 
void init() {
    isnotp[1] = phi[1] = 1;
    REP(i, 2, N - 1) {
        if(!isnotp[i]) p[++ tot] = i, phi[i] = i - 1;
        REP(j, 1, tot) {
            if(p[j] * i >= N) break;
            isnotp[p[j] * i] = 1;
            if(i % p[j] == 0) {
                phi[i * p[j]] = 1ll * phi[i] * p[j] % MOD;
                break;
            }
            else phi[i * p[j]] = 1ll * phi[p[j]] * phi[i] % MOD;
//          cout<<p[j]<<"*"<<i<<"???"<<endl; system("pause");
        } 
    }
    REP(i, 1, N - 1) inc(phi[i], phi[i - 1]);
//  REP(i, 1, 20) cout<<phi[i]<<" "; puts("");
}
 
LL getphi(LL r) {
    if(r < N) return phi[r];
    if(~vis[n / r]) return vis[n / r];
    LL ret = (1ll * r * (r + 1) % MOD) * inv2 % MOD;
    for(int i = 2; i <= r; ++ i) {
        int j = r / (r / i);
        dec(ret, 1ll * (j - i + 1) * getphi(r / i) % MOD);
        i = j;
    }
    return vis[n / r] = ret;
}
 
int main() {
    CLR(vis, -1);
    n = rd(), MOD = rd();
    init();
    inv6 = pow_(6, MOD - 2);
    inv2 = pow_(2, MOD - 2);
    for(LL i = 1; i <= n; ++ i) {
        LL j = n / (n / i);
        inc(ans, 1ll * getphi(n / i) * ((getsum(j) - getsum(i - 1)) % MOD) % MOD);
        ans = (ans + MOD) % MOD;
        i = j;
    }
    printf("%lld\n", ans);
    return 0;
}

T3 字符串

比较打开思路。。。

复杂度优化瓶颈在于l和r的限制,无法快速访问。

但ac自动机大小小得可怜。

这道题的题解实际上考到了一个点就是说。

线段树本身就是一个分治的过程,如果我们把它的过程限制成有序的,那么实际上,比如这道题,我们可以考虑每个点维护从自动机上i号点走完了当前区间的串后到达了自动机上哪个点,并且记录路径贡献。

但这只是没有修改的情况。

有修改的情况,怎么一个log处理出来呢?我们的瓶颈在于线段树的区间不是一个整区间,那么我们把它补成2的整次幂,然后倍增预处理,打上一个tag,到的时候再下放就好了。

注意这时候的modify要特判与mid不交的情况。。。(3h惨案)

最后非常感谢lwj大爷在调试上的帮助T T

# include <bits/stdc++.h>
 
using namespace std;
 
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
 
const int N = 1e5 + 3, S = 18;
 
# define DIG(x) (x - 'a' + 1) 
# define gc getchar
inline int rd() {
    char ch = gc(); int ret = 0, sgn = 1;
    while(ch < '0' || ch > '9') { if(ch == '-') sgn = -1; ch = gc(); }
    while(ch <= '9' && ch >= '0') ret = ret * 10 + ch - '0', ch = gc();
    return sgn * ret;
}
 
# define pii pair<int, int>                           
# define mp make_pair                 
# define fir first
# define sec second
 
int n, q, curlen, curpw;
char buf[(1 << S)];
 
namespace ACAM {
    # define RT 0
    const int M = 26;
    int tr[53][27], actot, tag[53], fail[53];
       
    inline void init() { CLR(tr, 0), CLR(tag, 0), actot = 0; }
    void insert(char *str) {
        int cur = 0, l = strlen(str + 1);
        REP(i, 1, l) {
            if(!tr[cur][DIG(str[i])]) tr[cur][DIG(str[i])] = ++ actot;
            cur = tr[cur][DIG(str[i])];
        }
        ++ tag[cur];
   
    }
    int que[53], h, t;
    void buildfail() {
        h = t = 0;
        REP(i, 1, 26) 
            if(tr[RT][i]) fail[tr[RT][i]] = RT, que[++ t] = tr[RT][i];
            else tr[RT][i] = RT;
        while(h < t) {
            int u = que[++ h];
            REP(i, 1, 26) {
                int &v = tr[u][i];
                if(!v) { v = tr[fail[u]][i]; continue; }
                fail[que[++ t] = v] = tr[fail[u]][i], tag[v] += tag[fail[v]];
            }
        }
    }   
}
 
struct info {
    int f[53], g[53];
    inline void init(int c) { REP(i, 0, ACAM::actot) f[i] = ACAM::tr[i][c], g[i] = ACAM::tag[ACAM::tr[i][c]]; }
} ;
 
info g[S + 1][N];
int tp;
 
void upd(info &a, info b, info c);
void mult(int l, int r, int lenth) {
    using namespace ACAM;
    REP(i, l, r) g[0][i].init(DIG(buf[i]));
    REP(i, 1, S) REP(j, l, r) upd(g[i][j], g[i - 1][j], g[i - 1][(j - l + (1 << i - 1)) % lenth + l]);
}
 
# define u tr[x]
# define ls (x << 1)
# define rs (x << 1 | 1)
# define uls tr[ls]
# define urs tr[rs]
 
struct node {
    info x;
    int pw, tg, len, be;
    inline void init(int c) { x.init(c); }
} tr[(1 << S) + 2];
 
void upd(info &a, info b, info c) { REP(i, 0, ACAM::actot) a.f[i] = c.f[b.f[i]], a.g[i] = c.g[b.f[i]] + b.g[i]; }
 
pii merge(pii b, info c) { return mp(c.f[b.fir], b.sec + c.g[b.fir]); }
# define CPY(i, a) memcpy(i, a, sizeof(a))
void cover(int x, int be, int tg, int len) {
    if(!tg && !len) return ;
    u.x = g[u.pw][be + tg];
    ::u.be=be;
    u.tg = tg, u.len = len;
}
 
void pd(int x, int l, int r) {
    if(!u.tg && !u.len) return ;
    int mid = l + r >> 1;
    cover(ls, u.be, u.tg, u.len);
    cover(rs, u.be, (u.tg + mid - l + 1) % u.len, u.len);
     
//  printf("%d %d %d %d\n", l, r, mid, getpos(u.tg - 1, mid - l + 1 + 1, u.len));
    u.tg = 0, u.len = 0;
}
 
void modify(int x, int l, int r, int ql, int qr, int be, int tg, int lenth) { // tg.fir : position
    if(ql <= l && qr >= r) { cover(x, be,tg, lenth); return ; }
    pd(x, l, r);
    int mid = l + r >> 1;
    if(ql <= mid) modify(ls, l, mid, ql, qr, be, tg, lenth);
    if(qr > mid) {
        int up = (tg + mid - max(l, ql) + 1) % lenth;
        if(ql >= mid + 1) up = tg;
        modify(rs, mid + 1, r, ql, qr, be, up, lenth);
    }
    upd(u.x, uls.x, urs.x);
}
 
pii query(int x, int l, int r, int ql, int qr, pii cur) {
    if(ql <= l && qr >= r) return merge(cur, u.x);
    pd(x, l, r);
    int mid = l + r >> 1;
    if(ql <= mid) cur = query(ls, l, mid, ql, qr, cur);
    if(qr > mid) cur = query(rs, mid + 1, r, ql, qr, cur);
    return cur;
}
 
void build(int x, int l, int r, int pw) {
    u.pw = pw;
    if(l == r) { u.init(DIG(buf[l])); return ; }
    int mid = l + r >> 1;
    build(ls, l, mid, pw - 1);
    build(rs, mid + 1, r, pw - 1);
    upd(u.x, uls.x, urs.x);
}
 
# undef u 
# undef ls 
# undef rs 
# undef uls 
# undef urs 
 
# define QAQ puts("*")
void solve() {
    using namespace ACAM;
    init();
    REP(i, 1, n) {
        scanf("%s", buf + 1);
        insert(buf);
    }
    buildfail();
    scanf("%s", buf + 1);
    int tt = strlen(buf + 1);
    for(curlen = 1, curpw = 0; curlen < tt; curlen <<= 1, ++ curpw);
    build(1, 1, curlen, curpw);
    REP(qq, 1, q) {
        int op = rd();
        if(op - 1 == 0) {
            int l = rd(), r = rd();
            scanf("%s", buf + tp);
            int tmp = strlen(buf + tp);
            if(r - l + 1 < tmp) tmp = r - l + 1;
            mult(tp, tp + tmp - 1, tmp);
            modify(1, 1, curlen, l, r, tp, 0, tmp);
            tp += tmp;
        }
        else {  
            int l = rd(), r = rd();
            printf("%d\n", query(1, 1, curlen, l, r, mp(0, 0)).sec);
        }
    }
}
 
int main() {
//  freopen("1.in", "r", stdin);
//  freopen("mine.out", "w", stdout);
    n = rd(), q = rd();
    solve();
    return 0;
}

3-20

喜欢今天的题(*๓´╰╯`๓)。。

T1 模型

边双很好办。

求出带权重心(叶子节点为权值)

点双的问题在于重心(根)拿走了就会GG。

那么我们先将所有子树之间连起来,之后再按照边双一样做就行了。

# include <bits/stdc++.h>
   
using namespace std;
   
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define REPG(i, h, x) for(int i = h[x], v; ~i; i = edge[i].next)
   
typedef long long LL;
# define gc getchar
inline int rd() {
    char ch = gc(); int ret = 0, sgn = 1;
    while(ch < '0' || ch > '9') { if(ch == '-') sgn = -1; ch = gc(); }
    while(ch <= '9' && ch >= '0') ret = ret * 10 + ch - '0', ch = gc();
    return sgn * ret;
}
const int N = 5e5 + 3, MOD = 1e9 + 7;
   
struct qwq { int v, next; } edge[N << 1];
int head[N], cnt, n;
inline void add(int u, int v) { edge[++ cnt] = (qwq) { v, head[u] }, head[u] = cnt; }
   
# define pb push_back
# define mp make_pair
# define pii pair<int, int>
# define fir first
# define sec second
# define pob pop_back
# define bk back
   
vector<pii > ans;
vector<int> lv[N];
priority_queue<pii > q;
   
bool ok[N];
   
int deg = 0, sz[N], mx[N], rt;
   
void dfs0(int x, int f) {
    int tmp = 0;
    REPG(i, head, x) if((v = edge[i].v) != f) {
        dfs0(v, x); sz[x] += sz[v];
        ++ tmp; mx[x] = max(mx[x], sz[v]);
    }
    if(sz[x] == 0) sz[x] = 1, ok[x] = 1; // ??
    else if(x == 1 && tmp == 1) ++ sz[x], ok[x] = 1;
}
   
void dfs1(int x, int f) {
    if(ok[x]) lv[deg].pb(x);
    REPG(i, head, x) if((v = edge[i].v) != f) dfs1(v, x);
}
   
bool cmp(const vector<int> &x, const vector<int> &y) { return x.size() > y.size(); }
   
int main() {
    int t = rd();
    while(t --) {
        n = rd(); 
        cnt = 0;
        ans.clear();
        CLR(sz, 0), CLR(mx, 0), CLR(ok, 0), CLR(head, -1);
//        REP(i, 1, n) sz[i] = 0, mx[i] = 0, ok[i] = 0, head[i] = -1;
        REP(i, 1, deg) lv[i].clear();
        REP(i, 1, n - 1) {
            int a = rd(), b = rd();
            add(a, b), add(b, a);
        }
        deg = 0;
        dfs0(1, 0);
        rt = 1; int tmpp = sz[1];
        REP(i, 1, n) {
            if(tmpp > max(mx[i], sz[1] - sz[i])) rt = i, tmpp = max(sz[1] - sz[i], mx[i]);
//            else if(tmpp > sz[1] - sz[i]) rt = i, tmpp = sz[1] - sz[i];
        }
        REPG(i, head, rt) {
            ++ deg;
            v = edge[i].v;
            dfs1(v, rt);
        }
        sort(lv + 1, lv + deg + 1, cmp);
   
        int lst = lv[1].bk();
        q.push(mp(lv[1].size(), 1));
        REP(i, 2, deg) if(!lv[i].empty()) { // !!!!!!!!!!!!!
            if(q.empty()) ans.pb(mp(lv[i].bk(), lst));
            else {
                int j = q.top().sec; q.pop();
                ans.pb(mp(lv[i].bk(), lv[j].bk()));
                lv[j].pob();
                if(!lv[j].empty()) q.push(mp(lv[j].size(), j));
            }
            lv[i].pob();
            if(!lv[i].empty()) q.push(mp(lv[i].size(), i));
   
        }
   
        while (!q.empty()) {
            int i = q.top().sec; q.pop();
            if(q.empty()) { ans.pb(mp(lv[i][0], lst)); break; }
            int j = q.top().sec; q.pop();
            ans.pb(mp(lv[j].bk(), lv[i].bk()));
            lv[j].pob(), lv[i].pob();
            if(!lv[i].empty()) q.push(mp(lv[i].size(), i));
            if(!lv[j].empty()) q.push(mp(lv[j].size(), j));
        }
   
        printf("%d\n", ans.size());
        for(auto x : ans) printf("%d %d\n", x.fir, x.sec);
    }
    return 0;
}

T2 Mythological VI

个人来说感觉很有意思的一个题

非常trick

思路实际上是类似把min转化成sigma的一个技巧,考虑当前大于等于v的贡献方案数或者说概率有多少。

之后。

  1. 补集转化。
  2. 等于号的转化。
  3. 期望的线性性的变形运用。

想想怎么求小于等于v的概率。

那么这就意味着大于$\frac{v}{2}$的数只能和小于$\frac{v}{2}$的点匹配,方案数是$(v-n)^{n-\frac{v}{2}}$

剩下的地方是一个完全图,方案数是$1\times 3\times 5\times ...\times \frac{v}{2}$

# include <bits/stdc++.h>
  
using namespace std;
  
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
  
typedef long long LL;
const int N = 1e6 + 3, MOD = 1e9 + 7;
# define gc getchar
inline int rd() {
    char ch = gc(); int ret = 0, sgn = 1;
    while(ch < '0' || ch > '9') { if(ch == '-') sgn = -1; ch = gc(); }
    while(ch <= '9' && ch >= '0') ret = ret * 10 + ch - '0', ch = gc();
    return sgn * ret;
}
  
int pow_(int x, int k) {
    int ret = 1;
    for(; k; k >>= 1, x = 1ll * x * x % MOD)
        if(k & 1) ret = 1ll * ret * x % MOD;
    return ret;
}
  
inline void inc(int &x, int c) { x = (x + c) % MOD; }
inline int inv(int x) { return pow_(x, MOD - 2); }
 
int n, f[N], ans, invn; 
 
int calc(int v) {
    int lft = v / 2, rt = n - lft;
    return 1ll * pow_(v - n, rt) * f[lft - rt] % MOD * invn % MOD;
}
 
int main() {
    n = rd();
    f[0] = 1;
    for(int i = 2; i <= n; i += 2) f[i] = 1ll * f[i - 2] * (i - 1) % MOD;
    invn = pow_(f[n], MOD - 2);
    ans = n;
    REP(i, n, n * 2 - 2) inc(ans, 1 - calc(i));
    printf("%d\n", (ans + MOD) % MOD);  
    return 0;
}

T3 Mythological VII

看题解吧。。。。

令sum为a数组的前缀和,我们就转化成了任意时刻$sum_l\ge sum_r$

考虑如果存在$i$使得$min(sum[i-x])>=sum[y]$且$sum[i]>sum[x]$那么显然可以贪心地走到$(i,y)$,$y$亦然。

当不能走的时候,如果依然存在$sum i <sum[y]$,那么显然是"No"(因为sum[y]不能更小了),$y$亦然。

接下来就只能尽量往两边贪心走了,如果当前前缀的最大值小于后缀的最小值就输出"No",否则就考虑前缀max和后缀max的关系,来决定是向左走还是向右走。

我稍微。。口胡理解一下

如果能够放宽限制,那么放宽限制。
如果放宽不了,判断l前是否存在一个不符合要求的点,如果存在那么无解,
因为考虑它不可能平安到达一个nl使得这时存在一个点的限制同时被放小, 因为前面的端点已经不能再变大了,它只会越来越小,而后面的端点不能再变大了。
之后,实际上只用考虑最值点。因为别的已经被我们在之前判掉了,定义r的下一个点nr为suffix_max的点
现在nr肯定是可达的,考虑去不去nr呢?
用左边最紧的限制去比较右边最松的限制,意思就是,“能不走就不走,要GG了才走”,最大化一个端点的贡献。

分析的困难点在于它的转移是离散的,我们在贪的过程中需要保证它的过程点是合法而正确的。

# include <bits/stdc++.h>
 
using namespace std;
 
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define REPG(i, h, x) for(int i = h[x]; ~i; i = edge[i].next)
# define QAQ puts("*")
# define STOP system("pause")
 
typedef long long LL;
const int N = 1e5 + 3, S = 18;
const LL INF = 1e16; 
 
# define gc getchar
inline LL rd() {
    char ch = gc(); LL ret = 0, sgn = 1;
    while(ch < '0' || ch > '9') { if(ch == '-') sgn = -1; ch = gc(); }
    while(ch <= '9' && ch >= '0') ret = ret * 10 + ch - '0', ch = gc();
    return sgn * ret;
}
 
LL pmx[N], pmn[N], smx[N], smn[N];
LL lr[N], rr[N];
int stk[N], tp, n, k, lg[N], pw[S + 1];
LL s[N], g[2][S + 1][N];
 
void init() {
     
    REP(i, 1, n) g[0][0][i] = s[i], g[1][0][i] = s[i];
    REP(i, 1, S) REP(j, 1, n) if(j + pw[i] - 1 <= n) {
        g[0][i][j] = min(g[0][i - 1][j], g[0][i - 1][j + pw[i - 1]]);
        g[1][i][j] = max(g[1][i - 1][j], g[1][i - 1][j + pw[i - 1]]);
    }
     
    tp = 0;
    CLR(lr, 0), CLR(rr, 0);
    REP(i, 1, n) { // 左边第一个比它大的位置
        while(tp && s[i] > s[stk[tp]]) -- tp;
        lr[i] = stk[tp], stk[++ tp] = i;
    }
    tp = 0;
    REPD(i, n, 1) { // 右边第一个比它小的位置
        while(tp && s[i] < s[stk[tp]]) -- tp;
        rr[i] = stk[tp], stk[++ tp] = i;
    } 
    pmx[1] = pmn[1] = 1, smx[n] = smn[n] = n;
 
    REP(i, 2, n) {
        pmx[i] = s[pmx[i - 1]] >= s[i] ? pmx[i - 1] : i;
        pmn[i] = s[pmn[i - 1]] <= s[i] ? pmn[i - 1] : i;
    }
 
    REPD(i, n - 1, 1) {
        smx[i] = s[smx[i + 1]] >= s[i] ? smx[i + 1] : i;
        smn[i] = s[smn[i + 1]] <= s[i] ? smn[i + 1] : i;
    }
}
 
inline LL qmn(int l, int r) {
    if(!l) return -INF;
    int len = r - l + 1;
    len = lg[len];
    return min(g[0][len][l], g[0][len][r - pw[len] + 1]);
}
 
inline LL qmx(int l, int r) {
    if(!r) return INF;
    int len = r - l + 1;
    len = lg[len];
    return max(g[1][len][l], g[1][len][r - pw[len] + 1]);
}
  
bool solve() {                      
    int l = k, r = k;
    while(l > 1 || r > n) {
        int x = lr[l], y = rr[r];
        if(l > 1 && qmn(x, l) >= s[r]) l = x;
        else if(r < n && qmx(r, y) <= s[l]) r = y;
        else if(l == 1) return s[l] >= s[smx[r + 1]];
        else if(r == n) return s[r] <= s[pmn[l - 1]];
        else {
            x = pmn[l - 1], y = smx[r + 1];
            if(s[x] < s[r] || s[y] > s[l]) return 0;
            x = pmx[l - 1];
            if(s[x] >= s[y]) l = x;
            else r = y;
        }
    } 
    return 1;
}
 
int main() {
    pw[0] = 1;
    REP(i, 1, S) pw[i] = pw[i - 1] << 1;
    REP(i, 2, N - 2) lg[i] = lg[i >> 1] + 1;
    int t = rd();
    while(t --) {
        n = rd(), k = rd();
        REP(i, 1, n) s[i] = rd(), s[i] += s[i - 1];
        init();
        printf("%s\n", solve() ? "Yes" : "No");
    }
    return 0;
}

3-21

T1 nonintersect

算几。

0180301092810_4858

0180301092816_4946

好像是个TC题。


态题


学了一下如何线段判交

struct cord {
    DB x, y;
    cord(DB _x = 0.0, DB _y = 0.0) : x(_x), y(_y) {}
} a[N];
vector<pii > wk;
 
inline cord getori(cord x, cord y) { return cord(y.x - x.x, y.y - x.y); }
 
# define SQR(x) ((x) * (x))
inline DB getdis(cord x, cord y) {
    cord gg = getori(x, y);
    return sqrt(SQR(gg.x) + SQR(gg.y));
}
 
inline DB cross(cord x, cord y, cord z) {
    cord aa = getori(x, y), bb = getori(x, z);
    return bb.x * aa.y - bb.y * aa.x;
}
 
bool inters(cord a, cord b, cord c, cord d) {
    if(!(min(a.x, b.x)<=max(c.x,d.x) && min(c.y,d.y)<=max(a.y,b.y) && min(c.x,d.x)<=max(a.x,b.x) 
        && min(a.y,b.y)<=max(c.y,d.y))) return false;
    DB u = cross(a, b, c);
    DB v = cross(a, b, d);
    DB w = cross(c, d, a);
    DB z = cross(c, d, b);
    return (u * v <= EPS && w * z <= EPS);
}
 
bool inter(pii s1, pii s2) {
    return inters(a[s1.fir], a[s1.sec], a[s2.fir], a[s2.sec]);
}

Reference

T2 新访问计划

很喜欢的一道题。

虽然。。。。。我并不知道出题人是怎么想到这个做法的qaq。妙妙。
有点神。。。

暴力的话肯定是,首先有一个sum的代价,之后问题就变成了有些链的权值是c有些事edge,问最小代价,随便dp就好了。

暴力的瓶颈在于它需要一个k。
在稍微分析了一下题目之后发现k关于c是单调的不升的,而这就容易使我们掉入一个陷阱,那就是认为c对于代价最小的方案选择有影响。
仔细观察我们发现在k相同的情况下,c与路径方案是无关的,因为无论如何,它一定会让收益最大化,即让边权尽量大。

那么对于一个k,我们只需要找到任意一种方案转移就好。由于k关于c单调不升,那么二分一下就好了。注意到总代价关于c的函数可能会出现平台,而k的取值变化并不是连续的,这个时候需要注意一下。

# include <bits/stdc++.h>
 
using namespace std;
 
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define REPG(i, h, x) for(int i = h[x], v; ~i; i = edge[i].next)
 
const int N = 2e4 + 3, INF = 0x3f3f3f3f;
 
typedef long long LL;
# define gc getchar
inline int rd() {
    char ch = gc(); int ret = 0, sgn = 1;
    while(ch < '0' || ch > '9') { if(ch == '-') sgn = -1; ch = gc(); }
    while(ch <= '9' && ch >= '0') ret = ret * 10 + ch - '0', ch = gc();
    return sgn * ret;
}
 
struct qwq { int v, next, c; } edge[N << 1];
int head[N], cnt;
inline void add(int u, int v, int c) { edge[++ cnt] = (qwq) { v, head[u], c }, head[u] = cnt; }
 
# define pii pair<int, int>
# define fir first
# define sec second
# define mp make_pair
 
int n, k, c, tc, sum;
 
pii f[N][2];
 
inline void rlx(pii &x, pii y) {
    if(x.fir == y.fir) x.sec = min(x.sec, y.sec);
    else if(x.fir > y.fir) x = y;
//  printf("%d %d, %d %d\n", x.fir, y.fir, 12, 12);
}
 
void dfs(int x, int fa) {
     
    int deg = 0;
    REPG(i, head, x) if((v = edge[i].v) != fa) dfs(v, x);
    f[x][0] = mp(0, 0), f[x][1] = mp(tc, 1);
    pii g[2];
    REPG(i, head, x) if((v = edge[i].v) != fa) {
        ++ deg;
        g[0] = f[v][0], g[1] = f[v][1];
        pii buf[2] = { mp(INF, 0), mp(INF, 0) };
 
        rlx(buf[0], mp(g[1].fir + f[x][1].fir - tc, g[1].sec - 1 + f[x][1].sec));
        rlx(buf[0], mp(g[0].fir + f[x][0].fir + edge[i].c, g[0].sec + f[x][0].sec));
        rlx(buf[0], mp(g[0].fir + f[x][0].fir + tc, g[0].sec + f[x][0].sec + 1));
//      printf("%d,%d: %d %d %d\n", x, v, f[x][0].fir, f[v][0].fir, f[v][1].fir);
     
        rlx(buf[1], mp(g[0].fir + edge[i].c + f[x][1].fir, g[0].sec + f[x][1].sec));
        rlx(buf[1], mp(g[0].fir + tc + f[x][0].fir, g[0].sec + f[x][0].sec + 1));
        rlx(buf[1], mp(g[1].fir + f[x][0].fir, g[1].sec + f[x][0].sec));
 
        f[x][0] = buf[0], f[x][1] = buf[1];
    }
     
}
 
void clear() {
    sum = 0; 
    REP(i, 0, n) head[i] = -1, cnt = 0;
}
 
void solve() {
    tc = c;
    dfs(0, -1);
    rlx(f[0][0], f[0][1]);
 
    if(f[0][0].sec <= k) { printf("%d\n", f[0][0].fir + sum); return ; }
    int l = 0, r = 1e9;
    while(l < r) {
        int mid = l + r >> 1;
        tc = mid;
        dfs(0, -1);
        rlx(f[0][0], f[0][1]);
 
        if(f[0][0].sec > k) l = mid + 1;
        else r = mid; 
    }
    tc = l; 
    dfs(0, -1);
    rlx(f[0][0], f[0][1]);
    printf("%d\n", f[0][0].fir + sum - f[0][0].sec * (l - c) - (l - c) * (k - f[0][0].sec));
 
 
}
 
int main() {
//  freopen("1.in", "r", stdin);
    while(~scanf("%d%d%d", &n, &k, &c)) {
        clear(); 
        REP(i, 1, n - 1) {
            int a = rd(), b = rd(), c = rd();
            add(a, b, c), add(b, a, c);
            sum += c;
        }
        solve();
    }
 
    return 0;
}                                                                              

3-23

T2 Draw

考虑在混合图欧拉回路的网络流做法基础上思考,这个时候我们会用到一个常用的技巧就是考虑每次合并两个点。对于存在一条S-T流就会减少两个度数代价,那么直接建边费用流最大化价值即可。

现在的问题是,奇数点有的时候可能被作为一个路径的开始,它对T有一个贡献,对S没有,那么我们单建一条费用为0的边即可。

注意多个联通块,且注意度数分配完毕与1取max。

# include <bits/stdc++.h>
  
using namespace std;
  
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define REPG(i, h, x) for(int i = h[x], v; ~i; i = edge[i].next)
  
const int N = 1e4 + 3, M = 1e5 + 3, INF = 1e9;
  
# define gc getchar
int rd() {
    int x = 0, f = 1; char ch = gc();
    while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = gc(); }
    while(ch <= '9' && ch >= '0'){ x = x * 10 + ch - '0'; ch = gc(); }
    return x * f;
}
  
# define pii pair<int, int>
# define pb push_back
# define fir first
# define sec second
# define mp make_pair
  
vector<pii > vec[N];
vector<int> bel[N];
  
int fa[N], n, m, head[N], cnt, S, T;
struct qwq { int v, next, f, c; } edge[M << 1];
inline void add(int u, int v, int f, int c) {
    edge[++ cnt] = (qwq) { v, head[u], f, c }, head[u] = cnt;
    edge[++ cnt] = (qwq) { u, head[v], 0, -c }, head[v] = cnt;
}
 
inline int gf(int x) { return fa[x] == x ? x : fa[x] = gf(fa[x]); }
int dis[N], fl[N], tim, id[N], deg[N];
bool vis[N];
queue<int> q;
 
bool spfa() {
    REP(i, 1, T) dis[i] = -1e9, vis[i] = false; 
    q.push(S);
    dis[S] = 0, vis[S] = true;
    while(!q.empty()) {
        int x = q.front(); q.pop();
        REPG(i, head, x) {
            if (edge[i].f && dis[(v = edge[i].v)] < dis[x] + edge[i].c){
                dis[v] = dis[x] + edge[i].c;
                if (!vis[v]) q.push(v), vis[v] = true;
            }
        }
        vis[x] = false;
    }
    return dis[T] != -1e9;
}
int vt[N], cur[N];
 
int dfs(int x, int fl, int &sum) {
    if(x == T || !fl) return sum -= fl * dis[T], fl;
    vt[x] = tim;
   
    int ret = 0, tmp;
    for(int i = head[x], v; ~i; i = edge[i].next) {
        if(vt[(v = edge[i].v)] != tim && dis[v] == dis[x] + edge[i].c && (tmp = dfs(v, min(fl, edge[i].f), sum)))
            ret += tmp, fl -= tmp, edge[i ^ 1].f += tmp, edge[i].f -= tmp;
        if(!fl) break;
    }
    return ret;
}
int cf(int tmp) {
    int sum = tmp;
    while(spfa()){ 
//      memcpy(cur, head, sizeof(cur));
        do ++ tim; while(dfs(S, INF, sum));
    }
    return sum;
}
  
int ans = 0;
int solve(vector<int> &ve) {
    int tot = ve.size();
    S = 0, T = tot + 1;
    CLR(head, -1), cnt = -1;
    bool sig = 0;
//  REP(i, 1, n) cout<<id[i]<<"??"<<endl;
    for(int x : ve) {
        for(pii e : vec[x]) {
            sig = 1;
            if(e.sec) add(id[e.fir], id[x], 1, 0);
        }
  
    }
    if(!sig) return 0;
    int tmp = 0;
    for(int x : ve) {
        if(deg[x] > 0) {
            tmp += deg[x];
            add(id[x], T, deg[x] >> 1, 1);
            if(deg[x] & 1) add(id[x], T, 1, 0);
        }
        else if(deg[x] < 0) {
            tmp += -deg[x];
            add(S, id[x], (-deg[x]) >> 1, 1);
            if((-deg[x]) & 1) add(S, id[x], 1, 0);
        }
    }   
    tmp /= 2;
    return max(cf(tmp), 1);
} 
  
int main() {
    n = rd(), m = rd(); 
    REP(i, 1, n) fa[i] = i;
    REP(i, 1, m) {
        int a = rd(), b = rd(), tp = rd();
        deg[a] ++, deg[b] --; // out - in
        vec[a].pb(mp(b, tp));
        int f1 = gf(a), f2 = gf(b);
        if(f1 != f2) fa[f2] = f1;
    }
  
    REP(i, 1, n) bel[gf(i)].pb(i), id[i] = bel[gf(i)].size();
    REP(i, 1, n) if(gf(i) == i) ans += solve(bel[i]);
    printf("%d\n", ans);
    return 0;
}

zkw费用流

其实就是把EK的单路增广变成dinic的dfs。

注意dfs的时候可能有环所以要注意判vis。

这种网络流更加适用于偏重流量而不是边权的图,反之EK可能效率反而会更高。

T3 King

Heaplax是找规律之神啊。。。。。。。。。。。。。。

3-28

T2 城市

重要的条件理解成了没有重边。。。。不然我考试的时候其实是往标算那边想的,结果读错题了,非常不爽。

# include <bits/stdc++.h>
 
using namespace std;
 
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPG(i, h, x) for(int i = h[x], v; ~i; i = edge[i].next)
 
const int N = 1e5 + 3;
 
int n, m, d[2][N];
int q[N], h, t;
 
struct qwq { int v, next; } edge[(N + N) << 1];
int head[N], cnt, ans[N];
inline void add(int u, int v) { edge[++ cnt] = (qwq) { v, head[u] }, head[u] = cnt; }
 
# define gc getchar
inline int rd() {
    char ch = gc(); int ret = 0;
    while(ch < '0' || ch > '9') ch = gc();
    while(ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0', ch = gc();
    return ret;
}
 
# define pb push_back
# define pii pair<int, int>
# define fir first
# define sec second
# define mp make_pair
 
struct info { 
    int x, y, id; 
    info(int _x, int _y, int _z) : x(_x), y(_y), id(_z) {}
} ;
vector<info> vec;
vector<int> G;
 
int tid[N], id[N], tim;
 
# define dc d[op]
void bfs(int s, int op) {
    h = t = 0; q[++ t] = s;
    dc[id[s]] = 0;
    while(h < t) {
        int x = q[++ h];
        REPG(i, head, x) if(tid[(v = edge[i].v)] == tim) {
            if(dc[id[v]] != -1) continue;
            dc[id[v]] = dc[id[x]] + 1;
            q[++ t] = v;
        }
    }
}
# undef dc
 
void divide(vector<int> g, vector<info> que) {
    if(que.empty()) return ;
    if(g.size() == 3) return ;
    int tmp = 0; ++ tim;
    for(int x : g) tid[x] = tim, id[x] = ++ tmp;
    REP(i, 1, tmp) d[0][i] = d[1][i] = -1;
     
    int mn = 0x7fffffff, ta, tb;
    for(int x : g) {
        REPG(i, head, x) if(tid[(v = edge[i].v)] == tim) {
            int a = id[x], b = id[v];
            if(a > b) swap(a, b);
            int d = max(b - a, tmp - b + a);
            if(d < mn) mn = d, ta = x, tb = v; 
        }
    }
//  puts("(");
    bfs(ta, 0), bfs(tb, 1);
//  puts(")");
    ta = id[ta], tb = id[tb];
    for(info e : que) {
        int x = id[e.x], y = id[e.y], i = e.id;
        if(tid[e.x] == tim && tid[e.y] == tim) 
            ans[i] = min(ans[i], d[0][x] + d[0][y]), ans[i] = min(ans[i], d[1][x] + d[1][y]);
    }
 
    vector<int> p1, p2;
    vector<info> q1, q2;
    for(int x : g) {
        if(id[x] <= ta || id[x] >= tb) p1.pb(x);
        if(id[x] >= ta && id[x] <= tb) p2.pb(x);
    }
 
    for(info e : que) {
        int x = e.x, y = e.y, i = e.id;
        if((id[x] <= ta || id[x] >= tb) && (id[y] <= ta || id[y] >= tb)) q1.pb(e);
        if((id[x] >= ta && id[x] <= tb) && (id[y] >= ta && id[y] <= tb)) q2.pb(e);
    }
 
    divide(p1, q1), divide(p2, q2);
 
} 
 
int main() {
    CLR(head, -1);
    n = rd();
    REP(i, 1, n - 1) add(i, i + 1), add(i + 1, i);
    add(n, 1), add(1, n);
    REP(i, 1, n - 3) {
        int a = rd(), b = rd();
        add(a + 1, b + 1), add(b + 1, a + 1);
    }
    m = rd();
    REP(i, 1, m) {
            int a = rd(), b = rd(); ++ a, ++ b;
            if(a > b) swap(a, b);
            vec.pb(info(a, b, i));
            ans[i] = min(b - a, n - b + a);
//          cout<<ans[i]<<endl;
        }
        REP(i, 1, n) G.pb(i);
        divide(G, vec);
        REP(i, 1, m) printf("%d\n", ans[i]);
    return 0;
}

T3 序列

判断区间内的元素是否单调不增。

这个题实际上用到了原来线段树的一个技巧,实际上线段树就是一个有序的分治,我们在必要的时候,merge其实只用看边界的地方如何合并。

这道题我们只要记录它最小的拐点有没有被淹没就好了。

# include <bits/stdc++.h>
 
using namespace std;
 
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define REPG(i, h, x) for(int i = h[x], v; ~i; i = edge[i].next)
 
const int N = 1e5 + 3, INF = 2e9;
 
# define gc getchar
inline int rd() {
    char ch = gc(); int ret = 0;
    while(ch < '0' || ch > '9') ch = gc();
    while(ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0', ch = gc();
    return ret;
}
 
struct node {
    int lx, rx, tg0, tg1, pt;
    node() { tg0 = pt = INF, lx = rx = tg1 = 0; }
} tr[N << 2];
  
int n, m, a[N];
  
inline void upd(node &u, node uls, node urs) { 
    u.lx = uls.lx, u.rx = urs.rx;
    u.pt = min(uls.pt, urs.pt);
    if(uls.rx < urs.lx) u.pt = min(u.pt, uls.rx);
}
# define u tr[x]
# define ls x << 1
# define rs x << 1 | 1
# define uls tr[ls]
# define urs tr[rs]
  
inline void cover(int x, int t0, int t1) {
    u.lx = min(t0, u.lx) + t1, u.rx = min(t0, u.rx) + t1;
    if(u.pt >= t0) u.pt = INF;
    else u.pt += t1;
    u.tg0 = min(u.tg0, t0 - u.tg1), u.tg1 += t1;
}
 
inline void pd(int x) {
    cover(ls, u.tg0, u.tg1);
    cover(rs, u.tg0, u.tg1);
    u.tg0 = INF, u.tg1 = 0;
}
void build(int x, int l, int r) {
    if(l == r) { u.lx = u.rx = a[l]; return ; }
    int mid = l + r >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    upd(u, uls, urs);
}
  
void modify(int x, int l, int r, int ql, int qr, int t0, int t1) {
    if(ql <= l && qr >= r) { cover(x, t0, t1); return ; }
    pd(x);
    int mid = l + r >> 1;
    if(ql <= mid) modify(ls, l, mid, ql, qr, t0, t1);
    if(qr > mid) modify(rs, mid + 1, r, ql, qr, t0, t1);
    upd(u, uls, urs);
}
  
node qry(int x, int l, int r, int ql, int qr) {
//  cout<<x<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;
    if(ql <= l && qr >= r) return u;
    pd(x);
    int mid = l + r >> 1;
    node ret;
    if(qr <= mid) ret = qry(ls, l, mid, ql, qr);
    else if(ql > mid) ret = qry(rs, mid + 1, r, ql, qr);
    else {
        ret = qry(ls, l, mid, ql, qr);
        upd(ret, ret, qry(rs, mid + 1, r, ql, qr));
    }
    return ret;  
}
 
int main() {
//  freopen("1.in", "r", stdin);
//  freopen("out.out", "w", stdout);
    n = rd(), m = rd();
    REP(i, 1, n) a[i] = rd();
    build(1, 1, n);
    while(m --) {
        int op = rd(), l = rd(), r = rd();
        if(op != 3) {
            int x = rd();
            if(op == 1) modify(1, 1, n, l, r, INF, x);
            else if(op == 2) modify(1, 1, n, l, r, x, 0);
        }
        else printf("%d\n", qry(1, 1, n, l, r).pt < INF ? r - l + 1 : 1);
    }
    return 0;
}

3-26

T1

这个题主要是要发现一些性质。

首先一个性质就是说对于一个k级串它一定可以找到一个子串使得这个子串前后存在同一个k-1级串的border。

那么暴力dp就出来了,考虑枚举它的后缀然后转移就好了。

找一个子串。。子串。。子串。。。前缀。。。。。

我横竖睡不着,仔细看了半夜,才从字缝里看出字来,满篇都写着三个字母——“SAM”

为什么要用后缀自动机呢,因为后缀自动机上的节点,每个节点代表的是更有意义的一些子串。例如对于一个接受态节点,它的parent链上的存在的节点是更具有代表性的节点,他们不仅出现了至少两次,他们还是那些具有辨识意义的子串。意思就是和某个后缀的lcp,是可能取到的最大的那个。

那么感觉上就差不多了。

考虑从浅层到深层递推,首先当前点的答案至少是它到根这条链上的最大值,我们把提供这个最大值的节点记作pre。

那么我们要做的事情实际上就是看有没有可能更大,那就是看这个k-1级串(pre)是否在这里出现了两次。

SAM自带fail树,我们在pre的线段树里查询合法区间内是否出现两次即可。

如何维护每个点的线段树?可持久化线段树合并一下。

# include <bits/stdc++.h>
 
using namespace std;
 
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPG(i, h, x) for(int i = h[x], v; ~i; i = edge[i].next)
# define CPY(i, a) memcpy(i, a, sizeof(a))
 
const int N = 2e5 + 3, S = 25; // [0, 26)
 
int pos[N], id[N << 1], n;
char buf[N];
 
namespace Sam {
    # define u sa[x]
    # define v u.trans[c]
    # define vn sa[v]
    # define o sa[y]
     
    struct node { 
        int trans[S + 1], p, l;
    } sa[N << 1];
     
    int lst, tot, rt;
    int ins(int c, int pp) {
        int x = lst, y = ++ tot; lst = y;
        o.l = u.l + 1, id[y] = pp;
        for(; !v && x; x = u.p) v = y;
        if(!x) o.p = rt;
        else if(vn.l == u.l + 1) o.p = v;
        else {
            int z = ++ tot; sa[z].l = u.l + 1;
            CPY(sa[z].trans, vn.trans);
            id[z] = id[v];
            sa[z].p = vn.p, vn.p = o.p = z;
            for(int ori = v; v == ori && x; x = u.p) v = z;
        }
        return y;
 
    }
 
    int c[N], q[N << 1];
 
    inline void init() { rt = ++ tot; lst = rt;}
    void build(char *ch, int len) {
        init();
        REP(i, 1, len) {
            pos[i] = ins(ch[i] - 'a', i);
        }
        REP(x, 1, tot) ++ c[u.l];
        REP(i, 1, len) c[i] += c[i - 1];
        REPD(x, tot, 1) q[c[u.l] --] = x;
    }
    # undef u 
    # undef o
    # undef vn
    # undef v
}
namespace SegT {
    # define u tr[x]
    # define o tr[y]
    # define uls tr[u.ls]
    # define urs tr[u.rs]
     
    const int NR = 1e7 + 3;
    int tot, rt[N << 1];
    struct node {
        int ls, rs, sum;
    } tr[NR];
 
    inline void upd(int x) { u.sum = uls.sum + urs.sum; }
    int mergeleaf(int x, int y) { int z = ++ tot; tr[z].sum = u.sum + o.sum; return z; }
    int merge(int x, int y, int l, int r) {
        if(!x || !y) return x + y;
        if(l == r) return mergeleaf(x, y);
        int nx = ++ tot, mid = l + r >> 1;
        tr[nx].ls = merge(u.ls, o.ls, l, mid);
        tr[nx].rs = merge(u.rs, o.rs, mid + 1, r);
        upd(nx);
        return nx;
    }
 
    int qry(int x, int l, int r, int ql, int qr) {
        if(ql <= l && qr >= r) return u.sum;
        int mid = l + r >> 1, ret = 0;
        if(ql <= mid) ret += qry(u.ls, l, mid, ql, qr);
        if(qr > mid) ret += qry(u.rs, mid + 1, r, ql, qr);
        return ret;
    } 
 
    void ins(int &x, int l, int r, int p) {
        if(!x) x = ++ tot;
        if(l == r) { ++ u.sum; return ; }
        int mid = l + r >> 1;
        if(p <= mid) ins(u.ls, l, mid, p);
        else ins(u.rs, mid + 1, r, p);
        upd(x);
    }
 
    void init() {
        REP(i, 1, n) ins(rt[pos[i]], 1, n, i);
        REPD(i, Sam::tot, 1) {
            int x = Sam::q[i];
            if(Sam::sa[x].p) rt[Sam::sa[x].p] = merge(rt[Sam::sa[x].p], rt[x], 1, n);
        }
    }
    int bst[N << 1], ans[N << 1];
    void solve() {
        int ret = 1;
        bst[0] = 0, bst[1] = 1, ans[0] = ans[1] = 1;
        REP(i, 2, Sam::tot) {
            int x = Sam::q[i];
            if(Sam::sa[x].p == 1) bst[x] = x, ans[x] = 1;
            else {  
                int y = bst[Sam::sa[x].p], tmp = ans[y];
                if(qry(rt[y], 1, n, id[x] - Sam::sa[x].l + Sam::sa[y].l, id[x] - 1)) bst[x] = x, ans[x] = tmp + 1;
                else bst[x] = y, ans[x] = tmp;
            }
            ret = max(ans[x], ret);
        }
        printf("%d\n", ret);
    }
}
 
int main() {
    scanf("%s", buf + 1);
    n = strlen(buf + 1);
    Sam::build(buf, n); 
    SegT::init(); // puts("???");
    SegT::solve();
    return 0;
}

T2 Flow

首先对于一个边,它只有在有用的时候才会被割,也就是存在一条路径经过它的时候。

考虑一个路径什么时候才会割两次,那肯定是前面割了一条路后面割了一条路。

那么让这种情况不成立只需要在这种边上加一条INF的反向边。

# include <bits/stdc++.h>
 
using namespace std;
 
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define REPG(i, h, x) for(int i = h[x], v; ~i; i = edge[i].next)
# define CPY(i, a) memcpy(i, a, sizeof(a))
 
typedef long long LL;
const int N = 2e3 + 3;
const LL INF = (1ll << 60);
 
# define gc getchar
inline int rd() {
    char ch = gc(); int ret = 0, sgn = 1;
    while(ch < '0' || ch > '9') { if(ch == '-') sgn = -1; ch = gc(); }
    while(ch <= '9' && ch >= '0') ret = ret * 10 + ch - '0', ch = gc();
    return sgn * ret;
}
 
int head[N], cur[N];
int q[N], d[N], cnt = 1, h, t, n, m, S, T;
struct qwq { int v, next; LL f; } edge[N << 2];
inline void add(int u, int v, LL c) { 
    edge[++ cnt] = (qwq) { v, head[u], c }, head[u] = cnt;
    edge[++ cnt] = (qwq) { u, head[v], 0 }, head[v] = cnt; 
}
 
bool bfs() {
    REP(i, 0, T) d[i] = -1;
    h = t = 0;
    d[q[++ t] = S] = 0;
    while(h < t) {
        int x = q[++ h];
        REPG(i, head, x) { 
            if(d[(v = edge[i].v)] == -1 && edge[i].f) 
                d[v] = d[x] + 1, q[++ t] = v;
        }   
    } 
    return ~d[T];
}   
 
LL dfs(int x, LL fl) {
    LL usd = 0, f;
    if(x == T) return fl; 
    for(int &i = cur[x], v; ~i; i = edge[i].next) {
        if(edge[i].f && d[(v = edge[i].v)] == d[x] + 1 && (f = dfs(v, min(fl, 1ll * edge[i].f))))
            edge[i].f -= f, edge[i ^ 1].f += f, fl -= f, usd += f;
        if(!fl) return usd;
    }
    if(!usd) d[x] = -1;
    return usd;
}
 
LL dinic() {
    LL ret = 0;
    while(bfs()) {
        CPY(cur, head);
        LL tmp = dfs(S, INF);
        if(tmp >= INF) return INF;
        else ret += tmp;
    }
    return ret;
}
 
int vis[N], tim, ok[N];
# define pii pair<int, int>
# define fir first
# define sec second
# define pb push_back
# define mp make_pair
 
vector<pii > vec0[N], vec1[N];
 
int main() {
    int ca = rd();
    while(ca --) {
        CLR(head, -1), cnt = 1;
        n = rd(), m = rd();
        tim = 0;
        REP(i, 1, n) vis[i] = ok[i] = 0;
        S = 1, T = n;
        REP(i, 1, m) {
            int a = rd(), b = rd(), c = rd();
            vec0[b].pb(mp(a, c));
            vec1[a].pb(mp(b, c));
            add(a, b, c);
        }
        ++ tim, h = t = 0;
        q[++ t] = T, vis[T] = tim, ok[T] = 1;
        while(h < t) {
            int x = q[++ h];
            for(pii e : vec0[x]) if(vis[e.fir] != tim) {
                ok[e.fir] = 1;
                vis[e.fir] = tim;
                q[++ t] = e.fir;
            }
        }
 
        ++ tim, h = t = 0;
        q[++ t] = S, vis[S] = tim;
        while(h < t) {
            int x = q[++ h];
            for(pii e : vec1[x]) if(ok[e.fir]) {
                add(e.fir, x, INF);
                if(vis[e.fir] != tim) vis[e.fir] = tim, q[++ t] = e.fir;
            }
        }
         
        LL ans = dinic();
        printf("%lld\n", ans < INF ? ans : -1);
 
        REP(i, 1, n) vec0[i].clear(), vec1[i].clear();      
 
    }
    return 0;
}

3-28

T1 Coin

问题等价于从数轴上从左到右跳,每次跳的距离不能比上一次大,问方案数。

那么先贪心能走大步走大步,那么这些关键点,所有方案一定会经过这些关键点,问题转化为这个。

首先对于每一个单位步数为T的答案很好算,因为是倍数关系,所以可以用快速幂求,只要加上一步跨过来的就好了。

剩下贪心走,然后矩阵乘合并算步数就行了。

# include <bits/stdc++.h>
 
using namespace std;
 
# define RG register
# define REP(i, a, b) for(RG int i = a; i <= b; ++ i)
# define REPD(i, a, b) for(RG int i = a; i >= b; -- i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPG(i, h, x) for(RG int i = h[x], v; ~i; i = edge[i].next)
# define CPY(i, a) memset(i, a, sizeof(a))
 
typedef long long LL;
const int N = 50 + 3, MOD = 998244353;
 
# define gc getchar
inline int rd() {
    char ch = gc(); int ret = 0;
    while(ch < '0' || ch > '9') ch = gc();
    while(ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0', ch = gc();
    return ret;
}
inline LL rdl() {
    char ch = gc(); LL ret = 0;
    while(ch < '0' || ch > '9') ch = gc();
    while(ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0', ch = gc();
    return ret;
}
 
int n; 
inline void inc(LL &x, LL b) { x = (x + b) % MOD; }
struct Mat {
    LL a[N][N];
    inline LL* operator [](int i) { return a[i]; }
        inline const LL* operator [](int i) const { return a[i]; }
        Mat() { CLR(a, 0); }
        void init() { REP(i, 0, n) a[i][i] = 1; }
} ans, a[N];
 
LL v[N], m;
 
Mat operator *(const Mat &x, const Mat &y) {
    Mat ret = Mat();
    REP(i, 1, n) REP(k, 1, n) REP(j, 1, n) inc(ret[i][j], 1ll * x[i][k] * y[k][j] % MOD);
    return ret;
} 
 
Mat pow_(Mat x, LL k) {
    Mat ret; ret.init();
    for(; k ; k >>= 1, x = x * x) 
        if(k & 1) ret = ret * x;
    return ret;
}
 
int main() {
    n = rd(), m = rdl();
    REP(i, 1, n) v[i] = rdl();
    sort(v + 1, v + n + 1);
     
    a[1][1][1] = 1;
    REP(i, 2, n) {
        a[i] = pow_(a[i - 1], v[i] / v[i - 1]);
        REP(j, 1, i) inc(a[i][i][j], 1);
    }
    ans.init();
 
    REPD(i, n, 1) {
        ans = ans * pow_(a[i], m / v[i]);
        m %= v[i];
    }
 
    LL ret = 0;
    REP(i, 1, n) inc(ret, ans[i][1]);
    printf("%lld\n", ret);
    return 0;
}

T2 同构

这个题非常巧妙。。。题解说得很好了。

主要还是要注意一下,想到dfs序和括号序这个。

3-29

T1 钢琴

优化可以利用一个性质就是fail其实变动得非常少,所以可以利用可持久化的思想来搞。

# include <bits/stdc++.h>
 
using namespace std;
 
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define CPY(i, a) memcpy(i, a, sizeof(a))
 
const int N = 100 + 3, M = 1e6 + 3, MOD = 1e9 + 7;
 
# define gc getchar
inline int rd() {
    char ch = gc(); int ret = 0, sgn = 1;
    while(ch < '0' || ch > '9') { if(ch == '-') sgn = -1; ch = gc(); }
    while(ch <= '9' && ch >= '0') ret = ret * 10 + ch - '0', ch = gc();
    return sgn * ret;
}
 
int f[M], n, m, s[M], nxt[M][N], g[M], ans[M];
 
inline void inc(int &x, int y) { x = (x + y >= MOD ? x + y - MOD : x + y); }
inline void dec(int &x, int y) { x = (y >= x ? x - y + MOD : x - y); }
 
int main() {
    n = rd(), m = rd();
    REP(i, 1, m) s[i] = rd();
    int j = 0; f[1] = 0;
    REP(i, 2, m) {
        while(j && s[j + 1] != s[i]) j = f[j];
        if(s[j + 1] == s[i]) ++ j;
        f[i] = j; /* cout<<f[j]<<endl; */
    }
    REP(i, 1, m) {
        CPY(nxt[i], nxt[f[i]]);
        nxt[i][s[f[i] + 1]] = f[i] + 1;
        inc(ans[i], 1ll * n * (ans[i - 1] + 1) % MOD), dec(ans[i], g[i - 1]), inc(ans[i], ans[nxt[i - 1][s[i]]]);
        inc(g[i], g[f[i]]), dec(g[i], ans[nxt[f[i]][s[f[i] + 1]]]), inc(g[i], ans[f[i] + 1]);
//      cout<<g[i - 1]<<"???"<<endl;
    }
    REP(i, 1, m) printf("%d\n", ans[i]);
    return 0;
}

3-30

T1 Bird

呃,树高log所以可以直接暴力模拟。记一下当前点子树内离当前点最近的是哪个。

# include <bits/stdc++.h>
 
using namespace std;
 
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define REPG(i, h, x) for(int i = h[x]; ~i; i = edge[i].next)
# define STOP system("pause")
# define CPY(i, a) memset(i, a, sizeof(a))
 
const int N = 3e5 + 3, INF = 0x3f3f3f3f;
 
# define gc getchar
inline int rd() {
    char ch = gc(); int ret = 0, sgn = 1;
    while(ch < '0' || ch > '9') { if(ch == '-') sgn = -1; ch = gc(); }
    while(ch <= '9' && ch >= '0') ret = ret * 10 + ch - '0', ch = gc();
    return ret * sgn;
}
 
int n, m, cap[N], p[N];
 
int tg[N], ans = 0;
struct info {
    int d, id;
    info(int _d = INF, int _id = 0) : d(_d), id(_id) {}
} tr[N];
 
info operator +(info a, int w) { return info(a.d + w, a.id); }
inline int operator <(info a, info b) { return a.d < b.d; }
 
# define ls (x << 1)
# define rs (x << 1 | 1)
# define u tr[x]
 
void upd(int x) {
    if(cap[x] > 0) u = info(0, x); 
    else u = info(INF, 0);
    if(ls <= n) u = min(u, tr[ls] + (tg[ls] >= 0 ? 1 : -1) );
    if(rs <= n) u = min(u, tr[rs] + (tg[rs] >= 0 ? 1 : -1) );
}
 
int main() {
    scanf("%d%d", &n, &m);
    REP(i, 1, n) scanf("%d", &cap[i]);
    REP(i, 1, m) scanf("%d", &p[i]);
 
    REPD(i, n, 1) upd(i);
 
    REP(i, 1, m) {
        int x = p[i];
        info tmp; int fl=0;
        for(int i = x; i ; i >>= 1) {
            if(tr[i].id) tmp = min(tmp, tr[i] + fl);
            fl += (tg[i] <= 0 ? 1 : -1);
        }
          
           
        int y = tmp.id; -- cap[y];
        for(; x != y; ) {
            if(x > y) -- tg[x], upd(x), x >>= 1;
            else ++ tg[y], upd(y), y >>= 1;
        }
        for(; x; x >>= 1) upd(x);
 
        ans += tmp.d;
        printf("%d ",ans);
    }
 
    return 0;
}

T2 Pow

它最后肯定是有若干个链,我们要做的就是找一个m吧这些链连起来,同时链首一定等于某个链尾 * 2 - m。而且实际上我们只需要找最小的判一下成不成立即可。

但事情还没有完,其实也要判次小的。因为它可能就是最后的那个。

注意0环的情况。

# include <bits/stdc++.h>
 
using namespace std;
 
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define REPG(i, h, x) for(int i = h[x]; ~i; i = edge[i].next)
# define CPY(i, a) memcpy(i, a, sizeof(a))
 
typedef long long LL;
const int N = 2e5 + 3;
const LL INF = 1e18 + 7;
 
# define gc getchar
inline LL rdl() {
    char ch = gc(); LL ret = 0, sgn = 1;
    while(ch < '0' || ch > '9') { if(ch == '-') sgn = -1; ch = gc(); } 
    while(ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0', ch = gc();
    return sgn * ret;
}
 
inline int rd() {
    char ch = gc(); int ret = 0, sgn = 1;
    while(ch < '0' || ch > '9') { if(ch == '-') sgn = -1; ch = gc(); } 
    while(ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0', ch = gc();
    return sgn * ret;
}
 
 
# define pii pair<LL, int>
# define fir first
# define sec second
# define mp make_pair
# define pb push_back
 
LL l[N], r[N];
int cntl, cntr, mx = 0;
set <pii > st;
 
int n;
LL a[N]; 
bool in[N], out[N];
 
LL chk(LL m) {
    if(m <= mx) return INF;
    int tmp = 0;
    for(int i = 1, j = 1; i <= cntl; ++ i) {
        if(l[i] * 2 - r[j] == m) ++ j, ++ tmp;
    }
    return tmp == cntr ? m : INF;
}
 
int main() {
    n = rd();
    REP(i, 1, n) a[i] = rdl(), st.insert(mp(a[i], i)), mx = max(a[i], 1ll * mx);
 
    if(!mx) puts("1"), exit(0);
 
    REP(i, 1, n) {
        auto it = st.lower_bound(mp(a[i] << 1, 0));
        if(it != st.end() && (*it).fir == (a[i] << 1)) { 
            in[(*it).sec] = 1, out[i] = 1;
            st.erase(it);
        }
    }
 
    int num0 = 0, num1 = 0;
    REP(i, 1, n) {
        num0 += (a[i] == 0);
        if(!in[i]) {
            if(a[i] != 1 || num1) r[++ cntr] = a[i];
            if(a[i] == 1) ++ num1;
        }
        if(!out[i]) l[++ cntl] = a[i];
    }
 
    sort(l + 1, l + cntl + 1), sort(r + 1, r + cntr + 1);
    if(num0) l[++ cntl] = r[++ cntr] = 0;
    if(!cntr) printf("%lld\n", mx + 1), exit(0);
 
    LL ans = INF;
    ans = min(chk(l[1] * 2 - r[1]), chk(l[2] * 2 - r[1]));
    printf("%lld\n", ans);
 
    return 0;
}

T3

30Pts:

# include <bits/stdc++.h>
 
using namespace std;
 
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define CPY(i, a) memcpy(i, a, sizeof(a))
 
typedef long long LL;
const int N = 2000 + 3;
 
# define gc getchar
inline int rd() {
    char ch = gc(); int ret = 0, sgn = 1;
    while(ch < '0' || ch > '9') { if(ch == '-') sgn = -1; ch = gc(); }
    while(ch <= '9' && ch >= '0') ret = ret * 10 + ch - '0', ch = gc();
    return sgn * ret;
}
 
# define gc getchar
inline LL rdl() {
    char ch = gc(); LL ret = 0, sgn = 1;
    while(ch < '0' || ch > '9') { if(ch == '-') sgn = -1; ch = gc(); }
    while(ch <= '9' && ch >= '0') ret = ret * 10 + ch - '0', ch = gc();
    return sgn * ret;
}
 
LL inv, MOD, k, n;
LL xx, yy;
LL f[N][N], fac[N];
 
inline void inc(LL &x, LL y) { x = (x + y >= MOD ? x + y - MOD : x + y); }
 
LL pow_(LL x, LL k) {
    LL ret = 1;
    for(; k; k >>= 1, x = x * x % MOD)
        if(k & 1) ret = ret * x % MOD;
    return ret; 
}
 
inline void exgcd(LL a, LL b) {  
    static LL temp;
        if (b == 0) xx = 1, yy = 0;  
        else exgcd(b, a % b), temp = xx, xx = yy, yy = temp - a / b * yy;   
}  
 
int main() {
    MOD = rdl(), k = rdl(), n = rdl();
    REP(i, 1, k - 1) MOD *= MOD; 
    fac[0] = 1;
    REP(i, 1, n) fac[i] = i * fac[i - 1] % MOD;
    if(k == 1) {
        inv = pow_(fac[n], MOD - 2);
    }
    else if(k == 2) {
        exgcd(fac[n], MOD);
        inv = xx;
    }
    if(!fac[n] || fac[n] == 1) inv = 1;
//  cout<<<<endl;
    f[0][0] = 1;
    REP(i, 1, n) REP(j, 1, i) {
        inc(f[i][j], f[i - 1][j] * (i - 1) % MOD);
        inc(f[i][j], f[i - 1][j - 1] % MOD);
    }
    LL ans = 0;
    REP(i, 1, n) {
        inc(ans, i * f[n][i] % MOD * inv % MOD);
    }
 
    printf("%lld\n", ((((2 * n) % MOD) - ans) % MOD + MOD) % MOD);
    return 0;
}

怎么过得这么快。完蛋了,一年更比一年菜。

最后感谢LWJ大爷捐赠的numerous的(WAZ大爷的)饭票以及WY小姐姐安利的好吃的鱼店另外xfz天下第一可爱!

Upd: 酸菜鱼真好吃!


资料袋和待填的坑

  1. 练习dp与思维题,看一看lwj大爷给的zzq大爷的CS Academy题目选讲.pptx
  2. 期望与概率的题目
  3. Cayley Hamilton定理

    minshuo给的链接

    然后其实gdez好几个大爷也有写相关内容。。。。。

    但是感觉我好想没找着啥题。。。

  4. 数据结构的代码熟练度。
  5. 杜教筛
  6. 多项式开根,求逆,exp,FWT ···
  7. 一般图匹配的建模联系

小脆可整理

Tips:

  1. 3-26提到的SAM
  2. 新访问计划里面,考虑方案其实是不变的,以及最小方差生成树里,考虑排列变化的时间节点是什么。
  3. Coin的思路,Flow考虑一个边什么时候会被割QAQ
  4. 可持久化的思想
  5. minmax转sigma
  6. 线段树的分治思路
  7. dfs序的利用技巧。一般是单点修链上求和

· EOF ·

Comments
Write a Comment