noip

FF_pigeon · 2025-07-14 16:12:28 · 题解

noip[]

DAY1:

T1:

观察题目，发现一定要有横移的操作，所以考虑最小化平移的操作，以两列为一个单位考虑，发现有一种可以只平移两次（让黑子上去的时候交错一下）的方法，而且一定是最小情况，因为只平移一次的话肯定会有黑白子撞上。偶数情况会了，奇数只要有一个特判就做完了。

T2：

读题：不会。 首先要根据题意判断出，我们只需让 S(u) ≡ C(u) mod 3

这里C(u)表示就是每个点所处集合的编号。

理解题意后先看部分分，发现有一个保证图是一个树的部分分，考虑先做树的部分。发现一个很好的性质，就是树可以从叶子节点往上给边赋值，叶子节点非常好做，直接赋成对应值就可以，网上每个父节点都用他的父亲边来调，这样只有根节点不行，（所以随机化根节点就过了）。考虑怎么调节根节点：三部图跟二部图的区别就是有无奇环，所以如果根节点在一个奇环上，那么我们可以令 m = C_{root} - S_{root} 然后让与根节点在奇环上相连的两条边的值都是模三意义下 -m 的值，剩下的边正负交替即可。

code:

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define rep(x,a,b) for(int x=(a);x<=(b);++x)
#define rop(x,a,b) for(int x=(a);x<(b);++x)
#define per(x,a,b) for(int x=(a);x>=(b);--x)
#define pb push_back
#define mp make_pair
using namespace std;

const int N = 2e5 + 10;

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}

int n, m;
int c[N], head[N], vis[N], ecnt, Begin, End;
int col[N], num[N], pre[N], cn[N], s[N], sum[N], f[N];
vector<pair<int,int> >t[N];
struct ans{
    int u, v, val;
}a[N<<1];
struct Edge{
    int to, nxt, id;
}e[N<<1];
void addedge( int u , int v , int p ){
    e[++ecnt] = (Edge){v,head[u],p};
    head[u] = ecnt;
}
void check( int x ){
    for( int i = head[x] ; i ; i = e[i].nxt ){
        int v = e[i].to;
        if( col[v] == -1 )col[v] = col[x] ^ 1, check(v);
        else {
            if( col[v] == col[x] ){
                Begin = x;
            }
        }
    }
}
void dfs( int x , int fa , int come ){
    f[x] = fa;
    if( fa )t[x].pb(mp(fa,come));
    for( int i = head[x] ; i ; i = e[i].nxt ){
        int v = e[i].to;
        if( f[v] > 0 || v == Begin )continue;
        else{
            t[x].pb(mp(v,e[i].id));
            dfs(v,x,e[i].id);
        }
    }
}
void dfs1( int x ){
    for( int i = head[x] ; i ; i = e[i].nxt ){
        int v = e[i].to;
        if( col[v] == -1 ){
            col[v] = col[x] ^ 1;
            pre[v] = x;
            cn[v] = e[i].id;
            dfs1(v);
        }
        else{
            if( v == Begin && col[v] == col[x] ){
                End = x;
                cn[Begin] = e[i].id;
                pre[Begin] = End;
            }
        }
    }
}
void dfs2( int x ){
    for( int i = head[x] ; i ; i = e[i].nxt ){
        int v = e[i].to;
        if( col[v] != -1 ) continue;
        else{
            col[v] = col[x] ^ 1;
            dfs2(v);
        }
    }
}

void output(){
    for( int i = 1 ; i <= m ; ++i ){
        a[i].val = (a[i].val %3 + 3) %3;
        if( a[i].val == 0 )a[i].val = 3;
        cout << a[i].val << "\n";
        sum[a[i].u] += a[i].val;
        sum[a[i].v] += a[i].val;
    }
}
void get_ans( int x ){
    for( int i = 0 ; i < (int)t[x].size() ; ++i ){
        int v = t[x][i].first;
        if( v == f[x] )continue;
        get_ans(v);
        int cnt = c[v] - s[v];
        a[t[x][i].second].val = cnt;
        s[x] += cnt;
        s[v] += cnt;
    }
}
void get_ans2( int x ){
    for( int i = 0 ; i < (int)t[x].size() ; ++i ){
        int v = t[x][i].first;
        if( v == f[x] )continue;
        get_ans2(v);
        int cnt = c[v] - col[x];
        a[t[x][i].second].val = cnt;
        s[v] += cnt;
        s[x] += cnt;
    }
}
void solve(){
    vis[1] = 0;
    check(1);
    if( Begin ){
        dfs(Begin,0,0);
        get_ans(Begin);
        int cnt = (c[Begin] - s[Begin]);
        memset(col,-1,sizeof(col));
        col[Begin] = 0;
        dfs1(Begin);
        for( int i = End ; i != Begin ; i = pre[i] ){
            a[cn[i]].val += cnt;
            cnt = -cnt;
        }
        for( int i = head[End] ; i ; i = e[i].nxt ){
            int v = e[i].to;
            if( v == Begin )a[e[i].id].val += (cnt<<1);
        }
        output();
    }
    else{
        for( int i = 1 ; i <= n ; ++i )
            if( num[i] >= 2 ){
                Begin = i;
            }
        memset(col,-1,sizeof(col));
        col[Begin] = 0;
        dfs2(Begin);
        dfs(Begin,0,0);
        get_ans2(Begin);
        if(( s[Begin] %3 + 3 )% 3 == 1 ){
            a[t[Begin][1].second].val++;
            a[t[Begin][2].second].val++;
        }
        output();
    }
}

int main(){
    memset(col,-1,sizeof(col));
    memset(head,-1,sizeof(head));
    n = read();m = read();
    for( int i = 1 ; i <= n ; ++i )c[i] = read();
    for( int i = 1, u, v; i <= m ; ++i ){
        u = read();v = read();
        a[i].u = u;
        a[i].v = v;
        num[u]++;num[v]++;
        addedge(u,v,i);
        addedge(v,u,i);
    }
    solve();

    return 0;
}

T3

观察.jpg

发现两条很重要的事实：1、对于每个 a[i] ，其小于 lcm(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17) 的部分无论怎么操作都不会变，所以只要讨论 a[i] \bmod lcm 的部分。第二、最后一次操作没用，所以只要管 1-16 的最大公约数做上面那个除数。(720720)。

所以就有了做法，我们dp一个 f[i][j] 表示 数字 i,在 j -> k （倒序）之中产生了多少的贡献。

所以每个数统计到最后的答案就是:

至于修改，就很简单了，每次把某个数的贡献减去，再换成新数即可。 时间复杂度 O(kV + q)

int n, k, q;
ll a[N];
ll pw[20], f[720750][18], ans, sum[N];
int main(){
    n = read();k = read();
    for( int i = 1 ; i <= n ; ++i )a[i] = llread();
    pw[0] = 1ll;
    for( int i = 1 ; i <= k ; ++i )pw[i] = (n * pw[i-1] * 1ll) % mod;
    q = read();
        for( int j = k ; j ; --j ){
    for( int i = 0 ; i < 720720 ; ++i ){
            f[i][j] = ((f[i - (i%j)][j+1] + (i * pw[k-j]) % mod ) % mod + ((n - 1) * f[i][j+1])%mod + f[i][j] )%mod;
        }
    } 
    for( int i = 1 ; i <= n ; ++i ){
        sum[i] = (sum[i] + f[a[i] % 720720][1]) % mod;
        ll tmp = (a[i]/720720ll)*720720ll;
        tmp = (((tmp * pw[k-1]) % mod) * k ) % mod;
        sum[i] = ( sum[i] + tmp ) % mod; 
        ans = ( ans + sum[i] ) % mod;
    }
    cout << ans << "\n";
    while( q-- ){
        int x, y;
        x = read();y = read();
        ans -= sum[x];
        sum[x] = 0;
        sum[x] = (sum[x] + f[y % 720720][1]) % mod;
        ll tmp = (y/720720ll)*720720ll;
        tmp = (((tmp * pw[k-1]) % mod) * k ) % mod;
        sum[x] = (sum[x] + tmp) % mod;
        ans = ((sum[x] + ans) % mod + mod ) % mod;
        cout << ans << "\n";
    }
    return 0;
}

DAY2

T1

真的不知道考试的时候是怎么死的。 老师已经在题目里亲切的将 vt+\frac{1}{2}at^2 = s 给我了。发现二分t之后就直接变成一个判定性问题了，根据前面几个部分分的提示，我们可以很轻松的dp出上面这个公式左面计算出来的 s 的最大理论值是否比右面大。然后就做完了。不卡精度，状态一维，推荐使用限制次数的二分（40次就够了）时间复杂度 O(nlogV)。 code：(砍头版)

int T;
int n, k; 
ld A, V;
ld s; 
ld sum[N]; 
ld a[N], v[N], f[N], ans;

bool check( ld t ){
    ld tt = t*t;
    f[0] = V * t + A * tt;
    sum[0] = 0;
    for( int i = 1 ; i <= n ; ++i )sum[i] = sum[i-1] + v[i]*t;
    for( int i = 1 ; i <= n ; ++i )
        f[i] = max(f[i-1] + v[i] * t , 
                 f[max(i-k,0)] + max(v[i] * t,a[i] * tt) + (sum[i-1] - sum[max(i-k,0)]));
    if( f[n] >= s )return true;
    else return false;
}

void erfen(){
    int cnt = 100;
    ld l = 0 , r = s/sum[n] + (ld)100;
    while( cnt-- ){
        memset(f,0,sizeof(f));
        ld mid = (l + r) / 2;
        if( check(mid) ){
            ans = mid;
            r = mid+eps;
        }
        else l = mid;
    }
}
int main(){
    T = read();
    while( T-- ){
        n = read();k = read();s = llread();V = read();
        A = read();
        A /= 2;
        for( int i = 1 , b; i <= n ; ++i ){
            b = read();
            v[i] = (ld)b;
            sum[i] = sum[i-1] + v[i];
        }
        for( int i = 1, b ; i <= n ; ++i ){
            b = read();
            a[i] = (ld)b/2;
        } 
        erfen();
        pri%.10lf\n",(double)ans);
    }
    return 0;
}

T2：

并非需要Boruvka。

第一档：送温暖

第二档，去重之后还是送温暖。

但是这提示我们，可以优先去重。然后我们仔细观察，成功的被popcount启发，发现边权的值域只有 [0,logV] ，所以开 logV 个队列，用于存储每个点能连边权为多少的边。那么这条性质有那么用呢？考虑最小生成树的三种经典算法，图是个完全图，不能用kruskal，连通块之间边权因为是popcount（字典树是没法维护的），所以不能用Boruvka。综上，要使用Prim，而其每次寻找最小边权的操作与我们上面观察到的性质不谋而合。

所以开始考虑Prim卡在哪里：定义 T 为已经加入最小生成树的点集，S为还没加入最小生成树的点集。所以每次从 S 取点的操作，就可以从我们开的边权队列里从小边权的开始找，假设我们找到的点为 i ，那么就会出现一个问题：我们在将 i 加入 T 后，需要将所有在 S 中的 j 与 i 之间的边加入到上面的边权队列中。这样复杂度就会爆炸。所以，我们考虑一种 a ,也就是点的权值几乎把 2^k 铺满且接近完全图时的常用优化方式，就是每次只考虑那些跟 i 只相差一个二进制位的点，我们可以一次找到，而且边权就是 1 。至于相差位数更多的点，则可以通过这些只差一个二进制位的慢慢转移过去，这样就有效减少了进队的点数和边数。时间复杂度 O(n+Vlog^{2}V)

注意：这道题有popocount，所以可以进行这种优化。

int n, a;
int cnt[N], q[25][N], h[25], t[25], d[N], p;
ll ans, tot;
int main(){
    n = read();
    for( int i = 0 ; i <= N ; ++i )cnt[i] = 0, d[i] = 22;
    for( int i = 1 ; i <= n ; ++i )
        cnt[a = read()]++;
    d[a] = ans = 0;
    for( int i = 0 ; i <= 21 ; ++i ){
        h[i] = 1;t[i] = 0;
    }
    q[p=0][++t[0]] = a;
    while( tot < n ){
        int x;
        for( ; ; ++p ){
            while( h[p] <= t[p] ){
                x = q[p][h[p]++];
                if( p == d[x] )goto O;
            }
        }
        O: if( cnt[x] > 0 ){
            ans += d[x];
            tot += cnt[x];
            d[x] = 0;
            p = 1;
        }
        for( int i = 0 ; i < 19 ; ++i ){
            if( d[x^(1<<i)] > d[x] + 1){
                d[x^(1<<i)] = d[x] + 1;
                q[d[x]+1][++t[d[x]+1]] = x ^ (1<<i);
            }
        }
    }
    cout << ans << "\n";

    return 0;
}

T3:

考场上直接想的 O(n^2) 的做法，但是因为 lca 忘了没写出来。

而且 O(n^2) 的做法可以用 n次dfs来解决。。唐诗。。。

首先我们有欧拉函数的公式：

然后我们就可以将这个式子，

化简成一个使答案更为集中的形式，

这样统计答案就会清晰一些。

左边的连乘非常好做，直接dfs出每个子树的大小，那么经过其到其父亲这条边的路径数就是 sz[v] * (n - sz[v])

至于右半部分，我们要统计经过每种有某个质因子的路径的条数，这很不好做。所以正难则反，考虑用全部路径数减去不经过的路径数。问题就等价转化为了统计将含有某个质因子的边全部砍断之后剩下的每个连通块的大小。

我们称含有特定质因子的边是“关键边”，与关键边相连且深度较大的点叫做“关键点”。考虑每个关键点所代表的连通块大小 = 该关键点的子树大小减去所有在其字数内的关键点的子树大小。这里使用虚数思想：（但是不用建出来），将关键点假想为一棵树统计，得出答案。具体见代码。

code:

ll q_pow( ll a , ll b ){
    ll res = 1, base = a;
    while(b){
        if( b&1 ){
            res *= base;
            res %= mod;
        }
        base *= base;
        base %= mod;
        b >>= 1;
    }
    return res;
}
int n;
int head[N], ecnt, fa[N], dfn[N], dfnn, End[N], col[N], cnt, s[N];
int isprime[V+5], prime[V+5], low[V+5], top;
ll ans = 1, sz[N], dep[N];
vector<int> p[V+5];
struct edge{
    int u, v, w;
}g[N<<1];
struct Edge{
    int to, nxt, w;
}e[N<<1];
void addedge( int u , int v , int w ){
    e[++ecnt] = (Edge){v,head[u],w};
    head[u] = ecnt;
}
void dfs( int x , int fa ){
    dfn[x] = ++dfnn;
    dep[x] = dep[fa] + 1;
    sz[x] = 1;
    for( int i = head[x] ; i ; i = e[i].nxt ){
        int v = e[i].to;
        if( v == fa )continue ;
        dfs(v,x);
        sz[x] += sz[v];
        ans = ans * q_pow(e[i].w,sz[v] * (n-sz[v])) % mod;
    }
    End[x] = dfnn;
    return ;
}
bool cmp( int a , int b ){return dfn[a] < dfn[b];}
bool in_stack( int a , int b ){return dfn[a] <= dfn[b] && End[b] <= End[a];}
int main(){
    n = read();
    for( int i = 1, u, v, w ; i < n ; ++i ){
        u = read();v = read();w = read();
        g[i] = (edge){u,v,w};
        addedge(u,v,w);
        addedge(v,u,w);
        fa[v] = u;
    }
    dfs(1,0);
    for( int i = 2 ; i <= V ; ++i ){
        if( !isprime[i] )prime[++cnt] = i, low[i] = i;
        for( int j = 1 ; i * prime[j] <= V && j <= cnt ; ++j ){
            isprime[i*prime[j]] = 1;
            low[i * prime[j]] = prime[j];
            if( i % prime[j] == 0 )break;
        }
    }
    for( int i = 1 ; i < n ; ++i ){
        int d = g[i].w;
        if( dep[g[i].u] > dep[g[i].v] )swap(g[i].u,g[i].v);
        while( d != 1 ){
            int x = low[d];
            p[x].pb(g[i].v);
            while( d % x == 0 )d /= x;
        }
    }
    for( int i = 2 ; i <= V ; i++ ){
        if( p[i].empty() )continue;
        sort(p[i].begin(),p[i].end(),cmp);
        s[top = 1] = 1;
        col[top] = n;
        ll tot = 1ll * (n - 1) * n /2;
        for( int j = 0 ; j < p[i].size() ; ++j ){
            int v = p[i][j];
            int u = 0;
            while( !in_stack(s[top],v) )tot -= 1ll * col[top] * (col[top]-1) /2,top--;
            col[top] -= sz[v];
            s[++top] = v;
            col[top] = sz[v];
        }
        while(top)tot -= 1ll * col[top] * (col[top] - 1) / 2, top--;
        ans = 1ll * ans * (q_pow(1 + mod - q_pow(i,mod-2) % mod,tot)) % mod;
    }
    cout << ans << "\n";
    return 0;
}

T4：

题意很好理解，定义 A = \Sigma a[i], B = \Sigma{b[i]}, 也很好想到我们 k 的取值就是 A/x 上取整。然后打的顺序就是从 b[i] - a[i] 大的靶子从大往小大。先按照上文优先级排序再定义 p[i] = \Sigma_{j=1}^{i} b[j] + \Sigma_{j=i+1}^{n}a[j] 所以求出一个 f(x) 就是二分一下 kx 在 p 序列中有几个比其小的就可以了。

但是这样是 O(nVlogn) 的，肯定无法通过。观察到有上取整操作，考虑数论分块。

假设现在我们已知 k 那么我们就有 x ∈ [\frac{A}{k},\frac{A}{k-1}) 考虑这些 x 会产生的贡献。就是：

其实里面的 x 也要求和的，但是懒得写了。

然后这个形式就很好维护了，x 的取值范围受到 k,A,B,p_{i-1},p_i 控制，最后算出一个区间长度， 再乘上个数即可。

这时，我们有两种不同的做法：

一种是用 O(logn) 的时间复杂度处理出一个 x

另一种是用 O(n) 的时间复杂度处理出一整个区间的中的答案之和。

这两种复杂度都不能直接通过，所以考虑平衡复杂度：假设我们将 x∈[0,T) 中的 x 用第一种方法去做， 剩下的用第二种去做， 那么就会有复杂度为 O(Tlogn + \frac{n^2V}{T}) 使用均值不等式，可以得出 T = n \sqrt{Vlogn} 。

但是这个 log 看着呆呆的（其实是常数太大了) 我们想把他优化掉。发现二分操作根本用不到，因为我们二分的范围是 x ∈ [0，T)， 这个范围直接计数排序就可以了，然后跟 p[i] 合起来扫描一遍就做完了。

最终复杂度 O(T + \frac{n^2V}{T}), 当且仅当 T = n\sqrt{V} 时等号成立，最优复杂度为O(2n\sqrt{V})。 结束。 code：

int n;
struct target{
    int a, b;
}t[N]; 
ll A, B, ans, D;
ll p[N], suma[N];
int cnt[30000010];
bool cmp( target c , target d ){
    return c.b - c.a > d.b - d.a;
}
int main(){
    n = read();
    for( int i = 1 ; i <= n ; ++i ){
        t[i].a = read();A += t[i].a;
        t[i].b = read();B += t[i].b;
    }
    sort(t+1,t+n+1,cmp);
    p[0] = A;
    for( int i = 1 ; i <= n ; ++i )p[i] = p[i-1] - t[i].a + t[i].b;
    D = min(T,B);
    for( int i = 1 ; i <= D ; ++i )cnt[(A+i-1)/i*i-A]++;
    for( int i = 1 ; i <= n ; ++i ){
        if( p[i-1] > A + T )break;
        for( int j = p[i-1]-A+1 ; j <= p[i]-A && j <= T ; ++j )ans += 1ll * i * cnt[j];
    }
    for( ll l = D + 1, r ; l <= B ; l = r + 1 ){
        ll lc = l, rc = B;
        ll k = (A+l-1)/l;
        while( lc <= rc ){
            ll mid = (lc + rc) >> 1;
            if( k == (A+mid-1)/mid ){
                lc = mid+1;
                r = mid;
            }
            else rc = mid-1;
        }
        ll l0 = max(l,(A+k-1)/k), r0 = min(r,B/k);
        if( l0 <= r0 ){
            for( int i = 1 ; i <= n ; ++i ){
                if( p[i]/k >= l0 )ans += 1ll * i * (min(p[i]/k,r0) - l0 + 1);
                if(p[i-1]/k >= l0)ans -= 1ll * i *(min(p[i-1]/k,r0) - l0 + 1);
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

DAY3:

T1：

没发现比较暴力的做法，发现如果一方要跟另一方的牌一一战胜，那么每个k 时刻都不能有被打败的那一方的牌数大于另一个人，所以自然就想到了卡特兰数， 类比他，将胜方的牌在数轴上的位置设置为 1 负方的牌在数轴上的位置设置为 -1, 那么整个数轴都不能有正值。操作为查询区间最小值，区间加/减，鉴定为线段树。

DAY4:

T1:

90分的温暖。

对于满分的做法，我们只要从考虑值域上有哪些值可以与公共牌凑成顺子，将想法转变为从使用最少（最后）的公共牌，来判断值域上哪些区间可以，最后注意并集操作即可。

T2:

不会map导致的。

其实很好想，字典序最大，直接贪心，考虑从大往小的火球有哪些能被合成为更大的火球，，发现只有奇数的火球能被合成出来，我们只需要搜索从大到小的偶数火球能够配对的奇数火球是否存在或者能否被合成，就完成了。

督促我去学map。

T3：

没看懂题解，但是有一步转化值得记录，如果我们只考虑相对于某个数的大小关系，而不考虑数值，那么我们可以令大于目标数的数字全部为1 , 小于目标数字的为 -1 ，目标数字为 0 。就可以通过求和统计区间内大于或小于目标数字的数字个数。

DAY5:

T1：

送温暖，又双叒叕的用差分处理区间求和。

code:

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define rep(x,a,b) for(int x=(a);x<=(b);++x)
#define rop(x,a,b) for(int x=(a);x<(b);++x)
#define per(x,a,b) for(int x=(a);x>=(b);--x)
using namespace std;

const int N = 2e5 + 10;

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll llread(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}

int n, m, k;
int h[N], l[N], r[N]; 
int d[N], s[N];
int ans;
int main(){
    n = read();m = read();k = read();
    for( int i = 1 ; i <= n ; ++i ){
        h[i] = read();
        ans = max(h[i],ans);
    }
    for( int i = 1 ; i <= m ; ++i ){
        l[i] = read();
        r[i] = read();
        d[l[i]]++;
        d[r[i]+1]--;
    }
    for( int i = 1 ; i <= n ; ++i ){
        s[i] = s[i-1] + d[i];
        h[i] += min(s[i],k);
        ans = max(ans,h[i]);
    }
    cout << ans << "\n";
    return 0;
}

T2：

还是很好想的，总是会能够出现在 mod n 意义下相同的数字，就会进去循环。但是模数不能直接模，会爆炸。

code:

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define rep(x,a,b) for(int x=(a);x<=(b);++x)
#define rop(x,a,b) for(int x=(a);x<(b);++x)
#define per(x,a,b) for(int x=(a);x>=(b);--x)
using namespace std;

const int N = 1e6 + 10;

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll llread(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}

ll n, L, P;
ll c[N], ans;
ll p[N], vis[N], cir, Begin;
int main(){
//  freopen("kwii3.in","r",stdin);
    n = llread();L = llread();p[0] = llread();P = llread();
    for( int i = 0 ; i < n ; ++i )c[i] = llread();
    for( int i = 0 ; i <= n ; ++i ){
        if( vis[p[i] % n] != 0  ){
            cir = i - vis[p[i] % n];
            Begin = vis[p[i] % n];
            break;
        }
        vis[p[i] % n] = i;
        p[i+1] = (p[i] + c[p[i] % n]);
    }
    ll sum = ((p[cir + Begin] - p[Begin] + P) % P );
    if( L > Begin )ans = (((((L - Begin)/cir)%P) * sum ) % P + ((p[(L - Begin) % cir + Begin] + P )%P)) % P;
    else {
        cout << p[L] << "\n";
        return 0;
    }
    cout << ans << '\n';
    return 0;
}

/*
5 100 6 100007
1 2 3 4 5 

*/

T3:

首先拆分贡献，对和式进行化简，发现 E 可以由每行总和和每列的总和产生。所以我们考虑求解 A 矩阵每行和每列的和，并用他们推出 A 矩阵。

发现行列和前面的系数有很强的等差性。考虑使用裂项相消，就会有：

其中 C 是每行的和，每列的和同理。至于 C_1 、 C_n ，可以用 E_{1,1} E_{1,m} E_{n,1} ，还有矩阵总和一定列出方程求解出公式。

然后考虑怎么从行和和列和得到原矩阵，我们有一种赋值的操作，就是将 A[i][j] 赋成 min(C[i],R[i]) ，然后再让两个后者都减去前者，就能够产生一组合法的解。

code

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define rep(x,a,b) for(int x=(a);x<=(b);++x)
#define rop(x,a,b) for(int x=(a);x<(b);++x)
#define per(x,a,b) for(int x=(a);x>=(b);--x)
#define pb push_back
using namespace std;

const int N = 3005;

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
ll llread(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}

int T, n, m;
ll E[N][N], A[N][N];
ll C[N<<1], R[N<<1];
int main(){
    T = read();
    memset(E,0,sizeof(E));
    while(T--){
        n = read();m = read();
        for( int i = 1 ; i <= n ; ++i )
            for( int j = 1 ; j <= m ; ++j )
                E[i][j] = llread();
        for( int i = 2 ; i < n ; ++i )C[i] = ( E[i+1][1] + E[i-1][1] - E[i][1] * 2 ) >> 1;
        for( int j = 2 ; j < m ; ++j )R[j] = ( E[1][j-1] + E[1][j+1] - E[1][j] * 2 ) >> 1;
        if( m == 1 && n == 1 ){cout << E[1][1] << "\n";continue;}
        if( m == 1 ){
            C[1] = E[n][1];
            for( int i = 2 ; i < n ; ++i )C[1] -= (n - i) * C[i];
            C[1] /= (n-1);
            C[n] = E[1][1];
            for( int i = 2 ; i < n ; ++i )C[n] -= (n - i) * C[n - i + 1];
            C[N] /= (n-1);
            for( int i = 1 ; i <= n ; ++i )cout << C[i] << "\n";
            continue;
        }
        if( n == 1 ){
            R[1] = E[1][m];
            for( int i = 2 ; i < m ; ++i )R[1] -= (m - i) * R[i];
            R[1] /= (m-1);
            R[m] = E[1][1];
            for( int i = 2 ; i < m ; ++i )R[m] -= (i - 1) * R[i];
            R[m] /= (m-1);
            for( int i = 1 ; i <= m ; ++i )cout << R[i] << " ";
            cout << "\n";
            continue;
        }
        ll X = E[1][1], Y = E[1][m], Z = E[n][1];
        for( int i = 2 ; i < n ; ++i )X -= (i - 1) * C[i], Y -= (i - 1) * C[i], Z -= (n - i) * C[i];
        for( int j = 2 ; j < m ; ++j )X -= (j - 1) * R[j], Y -= (m - j) * R[j], Z -= (j - 1) * R[j];
        ll W = 0;
        for( int i = 2 ; i < n ; ++i )W -= C[i];
        for( int i = 2 ; i < m ; ++i )W += R[i];
        W=W*(n-1)*(m-1);W-=(m-1)*Z-(n+m-2)*X-(n-1)*Y;W/=n-1,W/=2*n+2*m-4;

        C[n]=W,C[1]=(Z-X)/(n-1)+C[n],R[1]=(Y-(n-1)*C[n])/(m-1),R[m]=(X-(n-1)*C[n])/(m-1);
        for( int i = 1 ; i <= n ; ++i ){
            for( int j = 1 ; j <= m ; ++j ){
                A[i][j] = min(C[i],R[j]);C[i] -= A[i][j], R[j] -= A[i][j];
                cout << A[i][j] << " ";
            }
            cout << "\n";
        } 
    }
    return 0;
}

Day14:

T1

发现是区间减一操作，并且不带修改，所以我们可以先进行差分操作。然后区间[l,r]减一操作就是在差分数组上c_l - 1 和 c_{r+1} + 1, 那么我们就会想到，如果我能够把整个差分数组变为0 即为最后的答案。

对于最大化和最小化贡献，根据二次函数的凹凸性，我们直接贪心即可，寻找最远（近）的前正后负的点对即可。

code:写不出来里

T2:

首先转化一下提议，我们的操作序列肯定是形如 xy…y 的基本操作拼接而成，然后这个操作的以及就是会把序列的长度翻 y 的个数倍。

也就是我们要求出，\Pi a_i 大于等于某个值，并且最小化

其中 k 是 a_i 的个数，观察贡献的形式，发现第一题对其有启发作用。有推论：a_i 中的数字是会是两个相邻整数（二次函数的凹凸性）。所以我们先枚举 k, 然后二分 \Sigma a_i, 这样就能确定 a_i 的大小和个数。

注：在与 n 比大小时，使用除法而不是乘法来避免精度问题。

code:

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define rep(x,a,b) for(int x=(a);x<=(b);++x)
#define rop(x,a,b) for(int x=(a);x<(b);++x)
#define per(x,a,b) for(int x=(a);x>=(b);--x)
using namespace std;

const int N = 1e5 + 10;

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll llread(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}

const ll INF = 0x3f3f3f3f3f3f3f3fll;
ll n, ans = INF;
ll x, y;
int main(){
    n = llread();x = llread();y = llread();
    n++;
    int t = 1;
    while( (1ll << t) <= n * 2 ){
        ll L = t, R = n;
        while( L < R ){
            ll mid = (L + R) >> 1, pb = n - 1, val = mid / t, lg = mid % t;
            for( int i = 1 ; i <= lg ; ++i ){
                pb /= val + 2;if( pb == 0 )break;
            }
            for( int i = 1 ; i <= t - lg ; ++i ){
                pb /= val + 1;if( pb == 0 )break;
            }
            if( pb == 0 )R= mid; else L = mid + 1;
        }
        if( L <= ans / y )ans = min(ans, L * y + x * (ll)t);
        ++t;
    }
    cout << ans << "\n";
    return 0;
}

Day 15：

T1：

发现一个数字只能放在比 X_i 小的那些位置上，所以从小到大每个数字能放的位置都是确定的，直接做就行。

这个时候我认为给出的序列只能是升序，所以死了。首先，给出的序列不能全降序（或者方案数为1），那么对于一个先升后降的序列，我们发现，从第一个开始下降的元素起，候命所有的元素都要在排列的最后面，因为如果不是，我们可以将降序的第一个元素替换为第二个元素，保证序列元素数不变的情况下，成功的减小了字典序。

所以我们只用考虑前面那些升序的即可。

一定要对拍口牙一定要对拍口牙一定要对拍口牙

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 3e5 + 10;
const int mod = 998244353;

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int n, m;
int x[N], vis[N];
int main(){
    n = read();m = read();
    for( int i = 1 ; i <= m ; ++i ){
        x[i] = read();vis[x[i]] = 1;
    }
    if( !vis[1] ){
        cout << 0 << "\n";
        return 0;
    }
    int pos = 0;
    for( int i = 1 ; i <= m ; ++i )
        if( x[i+1] < x[i] ){
            pos = i;
            x[i+1] = n+1;
            break;
        }
    int len = 1;
    ll ans = 1;
    for( int i = 0 ; i <= pos ; ++i ){
        for( int j = x[i] + 1 ; j < x[i+1] ; ++j ){
            if( vis[j] )continue;
            if( i != pos )ans *= (len - 1);
            else ans *= len;
            ++len;
            ans %= mod;
        }
        ++len;
    }
    cout << ans << "\n";
    return 0;
}

T2：

构造题：我们思考一条线段什么时候覆盖的块数最多，发现如果除了两端点之外如果经过了整点，那么一定不优，而且，斜率越大的越不优，第一个条件要求横纵坐标差互质，第二个要求尽可能小。

自然而然就会想到以 (0,0) 和 (n,n-1) 两个点为基准往两侧保持互质的延伸。这样做发现最上面和最右面一行和一列都是覆盖不满的，那么就用斜率分别为 n 和 \frac{1}{n} 的两条线铺满，这样算出来线段数正好为 n + 1。

code:

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T, n;
int main(){
    T = read();
    while( T-- ){
        n = read();
        if( n == 1 ){
            cout << 1 << "\n";
            cout << 0 << " " << 0 << " " << 1 << " " << 1 << "\n";
            continue;
        }
        else if( n == 2 ){
            cout << 2 << "\n";
            cout << 2 << " " << 0 << " " << 0 << " " << 1 << "\n";
            cout << 2 << " " << 2 << " " << 0 << " " << 1 << "\n";
            continue;
        }
        else{
            cout << n + 1<< "\n";
            for( int i = 0 ; i < n ; i += 2 ){
                int y = n - i - 1;
                if( y > 0 ){
                    cout << i << " " << 0 << " " << n << ' ' << y << "\n";
                }
            }
            for( int x = n - 2 ; x > 0 ; x -= 2 ){
                int y = n - x - 1;
                if( y < n ){
                    cout << x << " " << n << " " << 0 << " " << y << "\n";
                }
            }
            cout << 0 <<" " << n << " " << n << " " << n-1 << "\n";
            cout << n << " " << 0 << " " << n - 1 << " " << n << "\n"; 
        }
    }
    return 0;
}

T3：

其实挺无脑的，就是用向量的叉乘去维护三角形面积，拆分贡献计算即可。最后的单调性维护非常好做。注意三点共线情况。

这里顺便给出向量叉乘的公式：

代码就不写了。

T4：

首先我们发现这道题跟0/1的大小关系无关。所以我们设 0 为 -1， 1 为 1， 这样前/后缀 1 的个数不小于 0 的个数就是前/后缀不小于零。

鉴于前后缀的变化量只会是 1 ，所以我们考虑贪心， 每次一遇到前缀为 -1 的点时便把这个 0 删除。这样对于前缀是最长的。而对于后缀，上面的操作删除的是前缀中最后能删除的 0 ， 所以对于后缀来说也是最优的。这样求出来的串一定是最长的。

这样是 O(n) 计算，我们考虑直接算出要删除多少个零来统计答案。记 a_i 为的前缀和，b_i为后缀和。那么第一遍扫描时删除的个数就是 max(-a_i)，但是这个时候 b 数组已经发生了改变， 设为 b^{'} ,我们发现可以用 b_i 和 a_i 表示出 b_{i} ^{'}，我们每次在 i 之后的位置删除一个 0 ，就会让 b_i +1，于是， b_{i} ^{'} 就是：

那么我们最后删除的总数 tot 就会等于：

经过酣畅淋漓的推式子，删除的总数就是最小的前后缀之和。而答案是 n - tot, 就是这个序列中的最大子段和长度

sgm 维护即可， 复杂度 O(n + mlogn)。

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 6e5 + 10;
const int inf = -1e8;

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int n, m;
char s[N];
int v[N], pre[N];
int node = 1;
struct Tag{
    int sum, lsum, rsum;
    int ans;
    Tag operator +(const Tag &x)const{
        Tag res;
        res.sum = sum + x.sum;
        res.lsum = max(lsum,sum + x.lsum);
        res.rsum = max(x.rsum,x.sum + rsum);
        res.ans = max(ans, max(x.ans, rsum + x.lsum));
        return res;
    }
};
struct tree_node{
    int ls, rs, val;
    Tag tag;
};
struct sgm_tree{
    tree_node t[N<<1];
    void T( tree_node &d, int x  ){
        d.val = x;
        d.tag.ans = d.tag.sum = d.tag.lsum = d.tag.rsum = x;
    }
    void pushup( int x ){t[x].tag = t[t[x].ls].tag + t[t[x].rs].tag;}
    void build( int x , int l , int r ){
        if( l == r ){
            T(t[x],v[l]);
            return ;
        }
        T(t[x],inf);
        int mid = (l + r) >> 1;
        t[x].ls = ++node;
        build(t[x].ls,l,mid);
        t[x].rs = ++node;
        build(t[x].rs,mid+1,r);
        pushup(x);
    }
    void update( int x , int l , int r , int to ){
        if( l == r ){
            if( t[x].val == 1 )
                T(t[x],-1);
            else T(t[x],1);
            return ;
        }
        int mid = (l + r) >> 1;
        if( to <= mid )update(t[x].ls,l,mid,to);
        else update(t[x].rs,mid+1,r,to);
        pushup(x);
    }
    Tag query( int x , int l , int r , int lc , int rc ){
        if( lc <= l && r <= rc )return t[x].tag;
        int mid = (l + r) >> 1;
        Tag L, R;
        int flagl = 0, flagr = 0;
        if( lc <= mid )L = query(t[x].ls,l,mid,lc,rc), flagl = 1;
        if( rc > mid )R = query(t[x].rs,mid+1,r,lc,rc), flagr = 1;
        if( flagl == 0 )return R;
        else if( flagr == 0 )return L;
        else return L + R;
    }
}SGM;
int main(){
    n = read();m = read();
    cin >> (s+1);
    for( int i = 1 ; i <= n ; ++i )v[i] = (s[i] == '0' ? -1 : 1);
    for( int i = 1 ; i <= n ; ++i )pre[i] = pre[i-1] + s[i] - '0';
    SGM.build(1,1,n);
    int op, l, r, x;
    while( m-- ){
        op = read();
        if( op == 1 ){
            l = read();r = read();
            Tag tmp = SGM.query(1,1,n,l,r);
            int cnt1 = tmp.ans;
            if( cnt1 < 0 )cout << 0 << "\n";
            else{
                int cnt2 = tmp.sum;
                cnt2 = (cnt2 + r - l + 1)/2;
                cout << cnt2 * 2 - cnt1 << "\n";
            } 
        }
        else{
            x = read();
            SGM.update(1,1,n,x); 
        }
    }
    return 0;
}

Day 17：

T1:

发现边的数据范围比较小，所以直接暴力。

考虑到点对的度数之和只会有 0 ~ 2n-1种取值，所以开 2n 个队列来维护，每次从最大的队列往最小的队列扫描，有可行的直接连边，并维护答案，再将这条边的端点有关点全部 +1 并且丢到队列中即可。

code:

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define rep(x,a,b) for(int x=(a);x<=(b);++x)
#define rop(x,a,b) for(int x=(a);x<(b);++x)
#define per(x,a,b) for(int x=(a);x>=(b);--x)
#define pii pair<int,int>
using namespace std;

const int N = 505;

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll llread(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}

int n, m;
int e[N][N];
int d[N];
queue<pii> q[N*2]; 
void clean( int x ){
    while( !q[x].empty() ){
        pii tmp = q[x].front();
        if( e[tmp.first][tmp.second] )q[x].pop();
        else return ;
    }
    return ;
}
int main(){
    n = read();m = read();
    for( int i = 1, u, v ; i <= m ; ++i ){
        u = read();v = read();
        d[u]++;d[v]++;
        e[u][v] = e[v][u] = 1;
    }
    for( int i = 1 ; i <= n ; ++i )
        for( int j = i + 1; j <= n ; ++j )
            if( !e[i][j] )q[d[i] + d[j]].push(make_pair(i,j));
    int tot = m;
    int ans = 20000;
    while( tot < (n * (n-1)) >> 1 ){
        pii tmp;
        for( int i = n * 2 - 2 ; i >= 0 ; --i ){
            if( !q[i].empty() )clean(i);
            if( q[i].empty() )continue;
            tmp = q[i].front();
            break;
        }
        int u = tmp.first, v = tmp.second;
        ans = min(ans,d[u]+d[v]);
        d[u]++;d[v]++;
        e[u][v] = e[v][u] = 1;
        q[d[u] + d[v]].push(make_pair(u,v));
        for( int w = 1 ; w <= n ; ++w ){
            if( w != u && !e[u][w] )q[d[u] + d[w]].push(make_pair(u,w));
            if( v != w && !e[v][w] )q[d[w] + d[v]].push(make_pair(v,w));
        }
        tot++;
    }
    cout << ans << "\n";
    return 0;
}

T2：

因为交换的贡献是两个数字，加之我们不可能交换两个相同的数字，所以我们考虑将贡献记在一次交换中较小的数字上。

这样我们从小到大枚举数字，每次看它的左边和右边比它大的数字的个数的 min 加入答案。

code:

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define rep(x,a,b) for(int x=(a);x<=(b);++x)
#define rop(x,a,b) for(int x=(a);x<(b);++x)
#define per(x,a,b) for(int x=(a);x>=(b);--x)
#define pb push_back
using namespace std;

const int N = 3e5 + 10;

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll llread(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}

int n;
int a[N];
vector<int> pos[N]; 
struct bit{
    int c[N];
    int lowbit( int x ){return x & -x;}
    void update( int x , int w ){while( x <= n ){c[x] += w;x += lowbit(x);}}
    int query( int x ){int res = 0;while(x){res += c[x];x -= lowbit(x);};return res;}
}BIT;
int main(){
    n = read();
    for( int i = 1 ; i <= n ; ++i ){
        a[i] = read();
        pos[a[i]].pb(i);
    }
    ll ans = 0;
    for( int i = 1 ; i <= n ; ++i )BIT.update(i,1);
    for( int i = 1 ; i <= n ; ++i ){
        if( pos[i].empty() )continue;
        for( int j = 0 ; j < pos[i].size() ; ++j )
            BIT.update(pos[i][j],-1);
        for( int j = 0 ; j < pos[i].size() ; ++j ){
            int lsum = BIT.query(pos[i][j]) - BIT.query(0);
            int rsum = BIT.query(n) - BIT.query(pos[i][j]);
            ans += min(lsum, rsum);
        }
    }
    cout << ans << "\n";
    return 0;
}

T3：

我们先考虑有 a_i 怎么求 p_i ,肯定是建出trie tree之后在上面贪心。

那么反过来，我们就考虑将 p 按照下标划分为多个 2^k 长度的段，发现其具有优秀的分治性质。

于是进行分类讨论： 假定一段区间 l ~ r 中的 p ，其中这个区间长度是二的次方。于是为了保证最大，我们必须要求这个区间的左半部分要么和右半部分完全相同（一一对应），要么没有任何的重复元素。如果不满足这两个条件，必会产生一种情况，就是对于重复的元素来说，它要同时满足这个区间所代表的固定位之后的那一位无论取 0/1 都是最大的，但是相同元素只能满足一边，而其他的不同元素在各自的一边肯定有能让取不到1的那一边取到一的方法， 所以就不满足最大的下标的要求了，故无解。

code：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e5 + 10;
const int mod = 1e9 + 7;

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int n, m;
int p[N], vis[N];
ll ans = 1;
void solve( int l , int r ){
    if( l == r )return ;
    int mid = (l + r) >> 1;
    int flag = 0;
    for( int i = l ; i <= mid ; ++i )flag |= p[i] ^ p[i + mid - l + 1];
    if( !flag ){
        ans <<= 1;
        ans %= mod;
        solve(l,mid);
        return ;
    }
    flag = 0;
    for( int i = l ; i <= mid ; ++i )vis[p[i]] = 1;
    for( int i = mid+1 ; i <= r ; ++i )if( vis[p[i]] )ans = 0;
    for( int i = l ; i <= mid ; ++i )vis[p[i]] = 0;
    if(ans){
        solve(l,mid);
        solve(mid+1,r);
        return ;
    }
}
int main(){
    n = read();m = read();
    for( int i = 0 ; i < (1<<m) ; ++i )p[i] = read();
    for( int i = 0 ; i < (1<<m) ; ++i )vis[p[i]] = 1;
    for( int i = 1 ; i <= n ; ++i )if( !vis[i] ){
        cout << 0 << "\n";
        return 0;
    }
    memset(vis,0,sizeof(vis));
    solve(0,(1<<m) - 1);
    cout << ans << "\n";
    return 0;
}

DAY18:

T1:

首先给 a 排个序，然后我们考虑限定只使用前/后 i 个中的元素选出某几个元素的和大于等于 m 的方案数，然后乘上组合数即可得到对每个 k 的贡献。

对于这个方案数的计算，我们考虑背包，设 f_{i,j} 表示用了前 i 个数字，和为 j 的方案数，但是我们发现这样状态为 O(n \Sigma V),过不了。其实后面只要到 m 就行了，比 m 大的算作 m。（又是如此玄学）

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 4e3 + 5;
const int mod = 998244353;

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int n, m;
int a[N], sum[N];
ll ans[N];
ll C[N][N], f[N][N], g[N][N];//C[i][j]±íʾ i¸öÀïÃæÑ¡j¸ö 
bool cmp( int A , int B ){return A > B;}

void init(){
    for( int i = 0 ; i <= 4000 ; ++i )C[i][0] = 1;
    for( int i = 1 ; i <= 4000 ; ++i ){
        for( int j = 1 ; j <= i ; ++j ){
            C[i][j] = C[i-1][j-1] + C[i-1][j];
            C[i][j] %= mod;
        }
    }
}
int main(){
    n = read();m = read();
    for( int i = 1 ; i <= n ; ++i ){
        a[i] = read();
    }
    sort(a+1,a+n+1,cmp);
    init();
    for( int i = 0 ; i <= n ; ++i )g[i][0] = 1;
    for( int i = 1 ; i <= n ; ++i ){
        for( int j = 1 ; j <= m ; ++j )g[i][j] = g[i-1][j];
        for( int j = a[i] ; j < m ; ++j ){
            f[i][j] += g[i-1][j - a[i]];
            g[i][j] += g[i-1][j - a[i]];
            f[i][j] %= mod;
            g[i][j] %= mod;
        }
        for( int j = max(m - a[i], 0) ; j <= m ; ++j ){
            f[i][m] += g[i-1][j];
            g[i][m] += g[i-1][j];
            f[i][m] %= mod;
            g[i][m] %= mod;
        }
    }
        for( int i = 1 ; i <= n ; ++i ){
    for( int k = 0 ; k <= n ; ++k ){
            ans[k] += (C[n - i][k] * f[i][m]) % mod;
            ans[k] %= mod;
        }
    }
    for( int i = 0 ; i <= n ; ++i )cout << ans[i] << " ";
    return 0;
}

或者另外简单版：

#define fo(x,y,z) for( int (x) = (y) ; (x) <= (z) ; ++(x) )
#define rep(x,y,z) for( int (x) = (y) ; (x) >= (z) ; --(x) )
int main(){
    init();
    n=read(),m=read();
    fo(i,1,n) a[i]=read();
    sort(a+1,a+n+1);
    f[n+1][0]=1;
    rep(i,n,1)
    {
        fo(j,0,3001) f[i][j]=f[i+1][j];
        fo(j,0,3001)
        {
            (f[i][min(j+a[i],3001)]+=f[i+1][j])%=mod;
        }
    }
    fo(i,1,n) rep(j,3000,0) (f[i][j]+=f[i][j+1])%=mod;
    fo(k,0,n-1) fo(i,k+1,n) (ans[k]+=C[i-1][k]*(f[i][m]-f[i+1][m]+mod))%=mod;
    fo(i,0,n) cout << ans[i] << " ";
    return 0;
}

还有,记得检查自己的模数写没写对。。。艹

T2：

首先，肯定是左右括号数相等的才能通过操作二转化，而操作一的最小次数就是左右括号个数之差的绝对值。

对于字典序最小，我们发现我们只会在最头/尾添加左/右括号，说明答案序列去掉添加的括号也是字典序最小的情况。而对于只有两种字符的字典序最小，可以表示为1/-1（小/大字典序字符），的前缀和的和最大。O(n) 判断即可。

code:

T3:

T4:

首先注意到，一个环上的最高的边一定是无用的，所以先做一次最小生成树。

其次，发现答案具有单调性，就是往1号筒中注入的水越多，那么所查询的筒 p 中的水量一定不会减少，考虑二分答案 mid。 对于这个 mid，那么跟 p 相连的所有在最小生成树中的路径边权最大值小于 mid 的节点一定都有 mid 的水量。记这些节点为集合 S，令 x = |S|，其中以1为根进行dfs后深度最小的点为 t , 可以使用 kruskal重构树 + 倍增求出。

这样我们注水的过程就拆分为两步，第一步是往1加水直到 t 开始有水， 此时用水量记为 f_t ，然后继续加水 x * mid 使 p 也有 mid 的水量。

那么怎么求 f_t 呢？我们照抄上面的思路，设 t 的父亲为 fa , 两点之间的边权为 w ，再设 S^{'} 为与 fa 之间简单路径边权最大值小于 w 的节点的集合，令 x^{'} = |S^{'}|, 深度最小的点为 t ^{'}, 这样就有：

同样使用 kuruskal重构树求出，然后发现这个一定是由深度小的点往深度大的点转移，所以进行 bfs (不过老师写的是 dfs ，应该都行)。

最后二分判断时，只需要比较 f_t + x * mid 和 a 的大小即可。

code:

DAY19:

T1:

思考最后的答案序列的样子，发现对于一个交换的位置，只有交换奇数次才会产生一次的贡献。然后相邻两次交换会使之间的数字与前一个交换的数字分离，直接从后往前扫描一遍，每次判断元素应当从后往前加入还是从前往后加入即可。

code:记得删调试就行，实现过于简单

T2：

发现答案要求的就是 n - \varphi(n) ，然后注意到（第一个），如果 n=pq, p\neq q, 且 p,q 为指数，那么所求就是 f(pq) = p + q - 1 = m , 然后又注意到，这个是哥猜，并且其在 1e9 内肯定成立，所以可以从小到大枚举较小的质数，又因为 1e9 内其答案的较小指数较小，直接暴力枚举质数 p ,看 m - p + 1 是不是质数即可。

答案就是 p * (m - p+ 1)

code：

bool is_prime( int x ){
    if( x == 0 || x == 1 )return false;
    if( x == 2 )return true;
    if( x == 3 )return true;
    for( int i = 3 ; i <= sqrt(x + 0.5) ; ++i ){
        if( x % i == 0 )return false;
    }
    return true;
}
int m;
ll ans = -1;
int main(){
    m = read();
    if( m == 3 ){
        cout << 9 << "\n";
        return 0;
    }
    m = m + 1;
    for( int i = 1 ; i < m - i ; i += 2 ){
        if( is_prime(i) && is_prime(m - i) ){
            ans = 1ll * i * (m-i);
            break;
        }
    }
    cout << ans << "\n";
    return 0;
}

T3：

法一：我们发现性质：

所以我们只需要统计在查询路径 lca 的有值路径，和查询路径覆盖的有值路径 lca 的个数。再去重即可。

法二：

考虑树的容斥 ：点数减边数等于 1 ，因为路径的交还是路径，而路径又是树，所以可以将路径的点权 +w， 边权 -w。最后求查询路径的路径和即为答案。

code(法二)：

int n, m, q;
int ecnt, head[N];
ll v1[N], v2[N], d[N];
struct Edge{
    int to, nxt;
}e[N<<1];
void addedge( int u , int v ){
    e[++ecnt] = (Edge){v,head[u]};head[u] = ecnt;
    e[++ecnt] = (Edge){u,head[v]};head[v] = ecnt;
}
int f[21][N], dfn[N], dn, fa[N];
int get( int x , int y ){return dfn[x] < dfn[y] ? x : y;}
int lca( int u , int v ){
    if( u == v )return u;
    if((u = dfn[u]) > (v = dfn[v]))swap(u,v);
    int l = __lg(v - u++);
    return get(f[l][u],f[l][v - (1<<l) + 1]);
}
void dfs( int u , int fh ){
    fa[u] = fh;
    f[0][dfn[u] = ++dn] = fh;
    for( int i = head[u] ; i ; i = e[i].nxt ){
        int v = e[i].to;
        if( v == fh )continue;
        dfs(v,u);
    }
    return ;
}
void dfs2( int u , int fh ){
    v1[u] += v1[fh];
    v2[u] += v2[fh];
    for( int i = head[u] ; i ; i = e[i].nxt ){
        int v = e[i].to;
        if( v == fh )continue;
        dfs2(v,u);
    }
}
void dfs3( int u , int fh ){
    for( int i = head[u] ; i ; i = e[i].nxt ){
        int v = e[i].to;
        if( v == fh )continue;
        dfs3(v,u);
        v1[u] += v1[v];
        v2[u] += v2[v];
    }
}
int main(){
    n = read();m = read();q = read();
    for( int i = 1, u, v ; i < n ; ++i ){
        u = read();v = read();
        addedge(u,v);
    }
    dfs(1,0);
    for( int j = 1 ; j <= __lg(n) ; ++j )
        for( int i = 1 ; i <= (n - (1<<j) + 1) ; ++i )
            f[j][i] = get(f[j-1][i],f[j-1][i + (1<<(j-1))]);
    for( int i = 1, x, y, w ; i <= m ; ++i ){
        x = read();y = read();w = read();
        int LCA = lca(x,y);
        v1[x] += w, v1[y] += w, v1[LCA] -= w, v1[fa[LCA]] -= w;
        v2[x] -= w, v2[y] -= w, v2[LCA] += 2 * w;
    }
    dfs3(1,0);
    dfs2(1,0);
    int x, y;
    while( q-- ){
        x = read();y = read();
        int LCA = lca(x,y);
        ll ans = v1[x] + v1[y] - v1[LCA] - v1[fa[LCA]];
        ans += v2[x] + v2[y] - v2[LCA] - v2[LCA];
        cout << ans << '\n';
    }
    return 0;
}