「JSOI2018 RoundII」「BZOJ5314 - 5319」题解

BZOJ5314 潜入行动

看到这道题就很容易想到一个裸的$O(nk^2)$的 DP,但是时间复杂度上似乎不是很能承受,但是实际上这个题的时间复杂度是 $O(nk)$的。分三类情况讨论,一种是两个子树大小都大于 $k$的,这个时候合并复杂度为$k^2$,但是这样的情况最多出现 $\frac{n}{k}$次。第二种是一个大于 $k$,一个小于等于 $k$,这个时候对于小于等于 $k$ 的节点的子树,每个点贡献一个 $k$ 的复杂度,同时可以发现每个点最多贡献一次,因为小于 $k$ 的向上合并一次就必定大于等于 $k$ 了。最后是两个点都小于等于 $k$ 的,复杂度可以均摊到每个节点上,这样复杂度也是 $O(nk)$ 的。

具体实现的时候可能需要一些寻址的常数优化。

时间复杂度 $O(nk)$。

#include <bits/stdc++.h>

using namespace std;

#define ll      long long
#define db      double
#define up(i,j,n)   for (int i = j; i <= n; i++)
#define down(i,j,n) for (int i = j; i >= n; i--)
#define cadd(a,b)   a = add(a, b)
#define cpop(a,b)   a = pop(a, b)
#define cmul(a,b)   a = mul(a, b)
#define pr      pair<int, int>
#define fi      first
#define se      second
#define bin(i)      (1 << (i))
#define SZ(x)       (int)x.size()
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & a, T b) { return b > a ? a = b, true : false; }
template<typename T> inline bool cmin(T & a, T b) { return b < a ? a = b, true : false; }

const int MAXN = 1e5 + 5;
const int MAXK = 105;
const int oo = 0x3f3f3f3f;
const int mod = 1e9 + 7;

inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return (ll)a * b % mod;}

int N, K;

struct edge {
    int y, next;
}e[MAXN << 1];

int LINK[MAXN], len = 0, f[MAXN][MAXK][2][2], siz[MAXN], g[MAXK][2][2];

inline void ins(int x, int y){
    e[++len].next = LINK[x]; LINK[x] = len;
    e[len].y = y;
}

inline void Ins(int x, int y){
    ins(x, y);
    ins(y, x);
}

void DFS(int node, int fa){
    f[node][0][0][0] = f[node][1][0][1] = 1; siz[node] = 1;
    Auto (i, node) if (e[i].y != fa) {
        DFS(e[i].y, node);
        siz[node] += siz[e[i].y];
    }
    if (!fa) return;
    int n = min(K, siz[node]);
    up (i, 0, n) {
        int m = min(K - i, siz[fa]);
        up (j, 0, m) {
            int *ss[2], *tt[2];
            up (k, 0, 1) {
                ss[k] = f[node][i][k];
                tt[k] = f[fa][j][k];
            }
            if (ss[0][0]) {
                cadd(g[i + j][0][1], mul(ss[0][0], tt[0][1]));
                cadd(g[i + j][1][1], mul(ss[0][0], tt[1][1]));
            }
            if (ss[0][1]) {
                cadd(g[i + j][1][1], mul(ss[0][1], tt[0][1]));
                cadd(g[i + j][1][1], mul(ss[0][1], tt[1][1]));
            }
            if (ss[1][0]) {
                cadd(g[i + j][0][0], mul(ss[1][0], tt[0][0]));
                cadd(g[i + j][0][1], mul(ss[1][0], tt[0][1]));
                cadd(g[i + j][1][0], mul(ss[1][0], tt[1][0]));
                cadd(g[i + j][1][1], mul(ss[1][0], tt[1][1]));
            }
            if (ss[1][1]) {
                cadd(g[i + j][1][0], mul(ss[1][1], tt[0][0]));
                cadd(g[i + j][1][0], mul(ss[1][1], tt[1][0]));
                cadd(g[i + j][1][1], mul(ss[1][1], tt[0][1]));
                cadd(g[i + j][1][1], mul(ss[1][1], tt[1][1]));
            }
        }
    }
    n = min(K, siz[fa] + siz[node]);
    up (i, 0, n) {
        memcpy(f[fa][i], g[i], sizeof(g[i]));
        memset(g[i], 0, sizeof(g[i]));
    }
}

int main(){
    scanf("%d%d", &N, &K);
    up (i, 2, N) {
        int x, y; scanf("%d%d", &x, &y);
        Ins(x, y);
    }
    DFS(1, 0);
    printf("%d\n", add(f[1][K][1][0], f[1][K][1][1]));
    return 0;
}

BZOJ5315 防御网络

题面很唬人,又是仙人掌又是斯坦纳树什么的。但是实际上,我们对每条边来计算贡献,对于树边可以直接 $O(1)$计算,环边的话把环拆开 DP 即可,具体细节不再赘述,可以参考代码。

时间复杂度 $O(n^3)$

#include <bits/stdc++.h>

using namespace std;

#define ll      long long
#define db      double
#define up(i,j,n)   for (int i = j; i <= n; i++)
#define down(i,j,n) for (int i = j; i >= n; i--)
#define cadd(a,b)   a = add(a, b)
#define cpop(a,b)   a = pop(a, b)
#define cmul(a,b)   a = mul(a, b)
#define pr      pair<int, int>
#define fi      first
#define se      second
#define bin(i)      (1 << (i))
#define SZ(x)       (int)x.size()
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)
#define FILE        "defense"

template<typename T> inline bool cmax(T & a, T b) { return b > a ? a = b, true : false; }
template<typename T> inline bool cmin(T & a, T b) { return b < a ? a = b, true : false; }

const int mod = 1e9 + 7;
const int MAXN = 405;
const int MAXM = MAXN * MAXN;
const int oo = 0x3f3f3f3f;

inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return (ll)a * b % mod;}

int qpow(int a, int b){
    int c = 1;
    while (b) {
        if (b & 1) cmul(c, a);
        cmul(a, a); b >>= 1;
    }
    return c;
}

int N, M;

struct edge {
    int y, next;
}e[MAXM];

int LINK[MAXN], len = 0;

inline void ins(int x, int y){
    e[++len].next = LINK[x]; LINK[x] = len;
    e[len].y = y;
}

inline void Ins(int x, int y){
    ins(x, y);
    ins(y, x);
}

int pw2[MAXN], dep[MAXN], siz[MAXN], fa[MAXN], cnt, ans;
vector<int> ss[MAXN];
bool vis[MAXN], ban[MAXN];

void DFS(int node){
    siz[node] = 1;
    Auto (i, node) if (!dep[e[i].y]) {
        dep[e[i].y] = dep[node] + 1;
        fa[e[i].y] = node;
        DFS(e[i].y);
        siz[node] += siz[e[i].y];
    }
    Auto (i, node) if (dep[e[i].y] < dep[node] - 1) {
        int x = node; ss[++cnt].push_back(x);
        do {
            ban[x] = 1;
            ss[cnt].push_back(x = fa[x]);
        }while (x != e[i].y);
    }
    Auto (i, node) if (dep[e[i].y] == dep[node] + 1 && !ban[e[i].y]) {
        int n = siz[e[i].y], m = N - n;
        n = pop(pw2[n], 1); m = pop(pw2[m], 1);
        cadd(ans, mul(n, m));
    }
}

void Fix(int node){
    vis[node] = siz[node] = 1;
    Auto (i, node) if (!vis[e[i].y]) {
        Fix(e[i].y);
        siz[node] += siz[e[i].y];
    }
}

int nodes[MAXN], n, f[MAXN], g[MAXN], a[MAXN];

int main(){
    scanf("%d%d", &N, &M);
    pw2[0] = 1;
    up (i, 1, N) pw2[i] = add(pw2[i - 1], pw2[i - 1]);
    up (i, 1, M) {
        int x, y; scanf("%d%d", &x, &y);
        Ins(x, y);
    }
    DFS(dep[1] = 1);
    up (o, 1, cnt) {
        up (i, 1, N) vis[i] = siz[i] = 0;
        n = 0; up (i, 0, SZ(ss[o]) - 1) nodes[++n] = ss[o][i];
        up (i, 1, n) vis[nodes[i]] = 1;
        up (i, 1, n) Fix(nodes[i]);
        up (i, 1, n) nodes[n + i] = nodes[i];
        up (i, 1, n + n) a[i] = pop(pw2[siz[nodes[i]]], 1);
        up (cl, 1, n) up (cr, cl + 1, n) {
            int len = n - (cr - cl);
            f[cl] = g[cl] = a[cl]; f[cl - 1] = g[cl - 1] = 0;
            up (i, cl + 1, cr) {
                f[i] = mul(a[i], pop(g[i - 1], g[max(i - len - 1, cl - 1)]));
                g[i] = add(g[i - 1], f[i]);
            }
            cadd(ans, mul(cr - cl, f[cr]));
//          printf("%d %d %d\n", cl, cr, f[cr]);
        }
        up (cl, 1, n) up (cr, n + 1, cl + n - 1) {
            int len = n - (cr - cl);
            f[cl] = g[cl] = a[cl]; f[cl - 1] = g[cl - 1] = 0;
            up (i, cl + 1, cr) {
                f[i] = mul(a[i], pop(g[i - 1], g[max(i - len, cl - 1)]));
                int x = i - len, y = i;
                if (cl <= x && (y <= n)) cadd(f[i], mul(a[i], f[x]));
                g[i] = add(g[i - 1], f[i]);
            }
            cadd(ans, mul(cr - cl, f[cr]));
//          printf("%d %d %d\n", cl, cr, f[cr]);
        }
    }
//  printf("%d\n", ans);
    cmul(ans, qpow(pw2[N], mod - 2));
    printf("%d\n", ans);
    return 0;
}

BZOJ5316 绝地反击

小清新计几题。

首先考虑二分答案,简单的计算可以得到每个区间可以覆盖的圆弧的角度范围,同时我们发现,对于任意一种合法的状态,一定可以调整为某一个等分点在区间边界上的情况,同时每个分界点最多属于一个等分点的移动范围,所以只有本质不同的 $n$ 个状态,我们拆分成加入和删除的事件即可。

这个时候转化成了给定一个二分图,每次插入边,删除边,询问是否存在完美匹配。我们用网络流解决,加入边时增广,删除边时退流即可。

时间复杂度 $O(n^3 \log n)$

#include <bits/stdc++.h>

using namespace std;

#define ll          long long
#define db          double
#define up(i,j,n)       for (int i = j; i <= n; i++)
#define down(i,j,n) for (int i = j; i >= n; i--)
#define cadd(a,b)       a = add (a, b)
#define cpop(a,b)       a = pop (a, b)
#define cmul(a,b)       a = mul (a, b)
#define pr          pair<db, db>
#define fi          first
#define se          second
#define SZ(x)       (int)x.size()
#define bin(i)      (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const db eps = 1e-8;
const db PI = acos(-1);
const db PI2 = PI + PI;
const int MAXN = 405;
const int MAXM = MAXN * MAXN;
const int oo = 0x3f3f3f3f;

inline int dcmp(db x){
    if (fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}

inline pr operator + (const pr & a, const pr & b) { return make_pair(a.fi + b.fi, a.se + b.se); }
inline pr operator - (const pr & a, const pr & b) { return make_pair(a.fi - b.fi, a.se - b.se); }

inline db crs(const pr & a, const pr & b) { return a.fi * b.se - a.se * b.fi; }
inline db dot(const pr & a, const pr & b) { return a.fi * b.fi + a.se * b.se; }
inline db length(const pr & a) { return sqrt(dot(a, a)); }

inline db sqr(db x) { return x * x; }

int N;
pr a[MAXN];
db R, w;

struct sta {
    int x, y, v; db t;
    inline sta (db t = 0, int x = 0, int y = 0, int v = 0) : t(t), x(x), y(y), v(v) {}
    inline bool operator < (const sta & w) const { return t < w.t; }
}c[MAXM];

int siz;

struct edge {
    int y, flow, next, rev;
}e[MAXM << 5];

int LINK[MAXN], cnt, S, T, ss[MAXN], tt[MAXN], len;

inline void ins(int x, int y, int flow, int rev){
    e[++len].next = LINK[x]; LINK[x] = len;
    e[len].y = y; e[len].flow = flow; e[len].rev = len + rev;
}

inline void Ins(int x, int y, int flow){
    ins(x, y, flow, 1);
    ins(y, x, 0, -1);
}

int level[MAXN];
deque<int> q;

bool makelevel(int st, int ed){
    up (i, 1, cnt) level[i] = -1;
    level[st] = 0; q.push_back(st);
    while (!q.empty()) {
        int node = q.front(); q.pop_front();
        Auto (i, node) if (level[e[i].y] == -1 && e[i].flow) {
            level[e[i].y] = level[node] + 1;
            q.push_back(e[i].y);
        }
    }
    return level[ed] != -1;
}

int addflow(int node, int flow, int ed){
    if (node == ed) return flow;
    int maxflow = 0, d;
    for (int i = LINK[node]; i && maxflow < flow; i = e[i].next)
        if (level[e[i].y] == level[node] + 1 && e[i].flow)
            if (d = addflow(e[i].y, min(e[i].flow, flow - maxflow), ed)) {
                e[i].flow -= d;
                e[e[i].rev].flow += d;
                maxflow += d;
            }
    if (!maxflow) level[node] = -1;
    return maxflow;
}

int play(int st, int ed){
    int flow = 0, d;
    while (makelevel(st, ed)) 
        while (d = addflow(st, oo, ed))
            flow += d;
    return flow;
}

void ins(db cl, db cr, int x, int y){
    cmax(cl, 0.0); cmin(cr, w - eps);
    if (dcmp(cl - cr) > 0) return;
    if (dcmp(cl) == 0) Ins(ss[x], tt[y], 1);
    else c[++siz] = sta(cl, x, y, 1);
    if (dcmp(cr - (w - eps)) != 0) c[++siz] = sta(cr, x, y, -1);
}

bool vaild(db D){
    w = PI2 / N; siz = len = 0;
    memset(LINK + 1, 0, sizeof(int) * cnt);
    up (i, 1, N) Ins(S, ss[i], 1);
    up (i, 1, N) Ins(tt[i], T, 1);
    up (i, 1, N) {
        db d = length(a[i]), cl, cr;
        if (dcmp(d + D - R) < 0) return 0;
        if (dcmp(d - D - R) > 0) return 0;
        if (dcmp(d + R - D) <= 0) {
            cl = 0; 
            cr = PI2 - eps;
        }else {
            db dd = (sqr(R) - sqr(D) + sqr(d)) / (d + d);
            db o = atan2(a[i].se, a[i].fi), h = acos(dd / R);
            cl = o - h + PI2; cr = o + h + PI2;
            if (dcmp(cl - PI2) >= 0) cl -= PI2;
            if (dcmp(cr - PI2) >= 0) cr -= PI2;
        }
        up (j, 1, N) {
            db o = (j - 1) * w;
            if (dcmp(cr - cl) >= 0) ins(cl - o, cr - o, i, j);
            else {
                ins(cl - o, PI2 - eps - o, i, j);
                ins(-o, cr - o, i, j);
            }
        }
    }
    sort(c + 1, c + siz + 1);
    int cur = play(S, T);
    if (cur == N) return 1;
    for (int cl = 1, cr; cl <= siz; cl = cr + 1) {
        cr = cl;
        while (cr + 1 <= siz && dcmp(c[cr + 1].t - c[cl].t) == 0) cr++;
        up (i, cl, cr) if (c[i].v == 1) {
            int x = ss[c[i].x], y = tt[c[i].y], id = 0;
            Auto (j, x) if (e[j].y == y) id = j;
            if (!id) {
                Ins(x, y, 1);
                id = len - 1;
            }
            e[id].flow = 1; e[e[id].rev].flow = 0;
        }
        cur += play(S, T);
        if (cur == N) return 1;
        up (i, cl, cr) if (c[i].v == -1) {
            int x = ss[c[i].x], y = tt[c[i].y], id = 0;
            Auto (j, x) if (e[j].y == y) id = j;
            int d = e[e[id].rev].flow;
            e[id].flow = e[e[id].rev].flow = 0;
            cur -= d;
            if (d) {
                makelevel(x, S); addflow(x, 1, S);
                makelevel(T, y); addflow(T, 1, y);
            }
        }
    }
    return 0;
}

int main(){
    scanf("%d%lf", &N, &R);
    up (i, 1, N) scanf("%lf%lf", &a[i].fi, &a[i].se);
    S = ++cnt; T = ++cnt;
    up (i, 1, N) ss[i] = ++cnt;
    up (i, 1, N) tt[i] = ++cnt;
    db le = 0, ri = 300, mi;
    while (dcmp(ri - le) > 0) {
        mi = (le + ri) / 2;
        if (vaild(mi))  ri = mi;
        else le = mi;
    }
    printf("%.10lf\n", ri);
    return 0;
}

BZOJ5317 部落战争

同样是一道计几题,可以发现合法的移动向量是构成一个凸包的,考虑如何求出这个凸包。

我们发现,所以合法的移动向量边界一定属于两个凸包任意两个点的差所构成的点集,发现其类似于闵可夫斯基和的定义,所以我们把$B$点集的坐标全部取反,求一遍闵可夫斯基和即可。

然后我们只需要每次判定一个点是否在凸包中,拿 std::set维护一下上凸包与下凸包即可。

#include <bits/stdc++.h>

using namespace std;

#define ll          long long
#define db          double
#define up(i,j,n)       for (int i = j; i <= n; i++)
#define down(i,j,n) for (int i = j; i >= n; i--)
#define cadd(a,b)       a = add (a, b)
#define cpop(a,b)       a = pop (a, b)
#define cmul(a,b)       a = mul (a, b)
#define pr          pair<int, int>
#define fi          first
#define se          second
#define SZ(x)       (int)x.size()
#define bin(i)      (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}
template<typename T> inline T dmax(T & x, T & y){return x > y ? x : y;}
template<typename T> inline T dmin(T & x, T & y){return x < y ? x : y;}

inline pr operator + (const pr & a, const pr & b) { return make_pair(a.fi + b.fi, a.se + b.se); }
inline pr operator - (const pr & a, const pr & b) { return make_pair(a.fi - b.fi, a.se - b.se); }

inline ll crs(const pr & a, const pr & b) { return (ll)a.fi * b.se - (ll)a.se * b.fi; }
inline ll dot(const pr & a, const pr & b) { return (ll)a.fi * b.fi + (ll)a.se * b.se; }

const int MAXN = 4e5 + 5;
const int oo = 0x3f3f3f3f;

int top;
pr q[MAXN];

struct Con {
    int n; pr a[MAXN];
    void init(bool rev){
        up (i, 1, n) scanf("%d%d", &a[i].fi, &a[i].se); 
        if (rev) up (i, 1, n) a[i] = make_pair(-a[i].fi, -a[i].se);
        sort(a + 1, a + n + 1);
        top = 0;
        up (i, 1, n) {
            while (top > 1 && crs(a[i] - q[top - 1], q[top] - q[top - 1]) <= 0) top--;
            q[++top] = a[i];
        }
        int o = top;
        down (i, n - 1, 1) {
            while (top > o && crs(a[i] - q[top - 1], q[top] - q[top - 1]) <= 0) top--;
            q[++top] = a[i];
        }
        n = top;
        memcpy(a + 1, q + 1, sizeof(a[0]) * n);
    }
    void push(pr w) { a[++n] = w; }  
    pr ttop() { return a[n];}
}A, B, C;

int n;
pr a[MAXN];

int Q;

set<pr> upp, low;
set<pr>::iterator pre, nxt, it;
set<pr>::reverse_iterator rit;

bool vaild(pr o){
    int cl = (*upp.begin()).fi, cr = (*upp.rbegin()).fi;
    if (o.fi < cl || o.fi > cr) return 0;
    else if (o.fi == cl) {
        int L = (*low.begin()).se, U = (*upp.begin()).se;
        it = low.begin();
        while ((*++it).fi == cl) cmin(L, (*it).se);
        it = upp.begin();
        while ((*++it).fi == cl) cmax(U, (*it).se);
        return L <= o.se && o.se <= U;
    }else if (o.fi == cr) {
        int L = (*low.rbegin()).se, U = (*upp.rbegin()).se;
        rit = low.rbegin();
        while ((*--rit).fi == cl) cmin(L, (*rit).se);
        rit = upp.rbegin();
        while ((*++rit).fi == cl) cmax(U, (*rit).se);
        return L <= o.se && o.se <= U;
    }else {
        pre = nxt = upp.lower_bound(o); --pre;
        if (crs(o - *pre, *nxt - *pre) < 0) return 0;
        pre = nxt = low.lower_bound(o); --pre;
        if (crs(o - *pre, *nxt - *pre) > 0) return 0;
        return 1;
    }
}

int main(){
#ifdef cydiater
    freopen("input.in", "r", stdin);
#endif
    scanf("%d%d%d", &A.n, &B.n, &Q);
    A.init(0); B.init(1);
    int cl = 1, cr = 1;
    C.push(A.a[cl] + B.a[cr]);
    while (cl < A.n || cr < B.n) {
        if (cl == A.n) C.push(A.a[cl] + B.a[++cr]);
        else if (cr == B.n) C.push(A.a[++cl] + B.a[cr]);
        else {
            pr x = A.a[cl + 1] + B.a[cr], y = A.a[cl] + B.a[cr + 1], o = C.ttop();
            crs(x - o, y - o) <= 0 ? (C.push(x), cl++) : (C.push(y), cr++);
        }
    }
    n = C.n; up (i, 1, n) a[i] = C.a[i];
    upp.insert(a[1]);
    int mi = -1;
    up (i, 2, n) if (a[i].fi >= a[i - 1].fi) upp.insert(a[i]);
    else {
        mi = i - 1;
        break;
    }
    down (i, n, mi) low.insert(a[i]);
    while (Q--) {
        pr o; scanf("%d%d", &o.fi, &o.se);
        puts(vaild(o) ? "1" : "0");
    }
    return 0;
}

BZOJ5318 扫地机器人

通过打表发现,对于$n \times m$的矩阵来说,令 $d=(n, m)$,可以把矩阵分成 $\frac{nm}{d^2}$个小矩阵,每个子矩形里的方案都是一样的。同时,对于一个 $d\times d$的矩阵内,其向下的格子数一定和 $n$ 互质,同时向右的格子一定和 $m$ 互质。可以发现这就是合法的充要条件。

然后我们考虑 DP,枚举所有合法的向下移动的步数,再枚举第一次遇到障碍的轮数,做一个简单的 DP 就没了。

时间复杂度 $O(n^4)$。

#include <bits/stdc++.h>

using namespace std;

#define ll          long long
#define db          double
#define up(i,j,n)       for (int i = j; i <= n; i++)
#define down(i,j,n) for (int i = j; i >= n; i--)
#define cadd(a,b)       a = add (a, b)
#define cpop(a,b)       a = pop (a, b)
#define cmul(a,b)       a = mul (a, b)
#define pr          pair<int, int>
#define fi          first
#define se          second
#define SZ(x)       (int)x.size()
#define bin(i)      (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}
template<typename T> inline T dmax(T x, T y){return x > y ? x : y;}
template<typename T> inline T dmin(T x, T y){return x < y ? x : y;}

const int mod = 998244353;
const int MAXN = 55;
const int oo = 0x3f3f3f3f;

inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return (ll)a * b % mod;}

int qpow(int a, int b){
    int c = 1;
    while (b) {
        if (b & 1) cmul(c, a);
        cmul(a, a); b >>= 1;
    }
    return c;
}

int gcd(int a, int b){return !b ? a : gcd(b, a % b);}

int mn[MAXN][MAXN], T, N, M, f[MAXN][MAXN], g[MAXN][MAXN];
char s[MAXN][MAXN];

int main(){
#ifdef cydiater
    freopen("input.in", "r", stdin);
#endif
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &N, &M);
        up (i, 0, N - 1) scanf("%s", s[i]);
        int d = gcd(N, M), n = N * M / d;
        int ans = 0;
        up (dx, 0, d) {
            int dy = d - dx;
            if (gcd(dx, N) != 1) continue;
            if (gcd(dy, M) != 1) continue;
            memset(mn, 0x3f, sizeof(mn));
            int cx = 0, cy = 0;
            up (i, 1, n) {
                up (tx, 0, dx) up (ty, 0, dy) {
                    int x = (cx + tx) % N, y = (cy + ty) % M;
                    if (s[x][y] == '0') continue;
                    cmin(mn[tx][ty], i);
                }
                (cx += dx) %= N;
                (cy += dy) %= M;
            }
            up (i, 1, n) {
                memset(f, 0, sizeof(f));
                memset(g, 0, sizeof(g));
                up (x, 0, dx) up (y, 0, dy) if (mn[x][y] > i) {
                    if (x == 0 && y == 0) {
                        f[x][y] = 1;
                        continue;
                    }   
                    if (0 <= x - 1) cadd(f[x][y], f[x - 1][y]);
                    if (0 <= y - 1) cadd(f[x][y], f[x][y - 1]);
                }
                down (x, dx, 0) down(y, dy, 0) if (mn[x][y] >= i) {
                    if (x + y == d - 1) g[x][y] = 1;
                    cadd(g[x][y], g[x + 1][y]);
                    cadd(g[x][y], g[x][y + 1]);
                }
                up (x, 0, dx) up (y, 0, dy) if (mn[x][y] == i) {
                    int ss = 0; 
                    if (x - 1 >= 0) cadd(ss, f[x - 1][y]);
                    if (y - 1 >= 0) cadd(ss, f[x][y - 1]);
                    if (x == 0 && y == 0) ss = 1;
                    cmul(ss, g[x][y]);
                    cadd(ans, mul(ss, d * (i - 1) + x + y));
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

BZOJ5319 军训列队

傻逼题,直接主席树。

#include <bits/stdc++.h>

using namespace std;

#define ll      long long
#define db      double
#define up(i,j,n)   for (int i = j; i <= n; i++)
#define down(i,j,n) for (int i = j; i >= n; i--)
#define cadd(a,b)   a = add(a, b)
#define cpop(a,b)   a = pop(a, b)
#define cmul(a,b)   a = mul(a, b)
#define pr      pair<int, int>
#define fi      first
#define se      second
#define bin(i)      (1 << (i))
#define SZ(x)       ((int)x.size())
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)
#define FILE        "line"

template<typename T> inline bool cmax(T & a, T b) { return b > a ? a = b, true : false; }
template<typename T> inline bool cmin(T & a, T b) { return b < a ? a = b, true : false; }

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

const int MAXN = 5e5 + 5;
const int MAXM = 2e6 + 5;
const int oo = 0x3f3f3f3f;

inline ll calc(ll le, ll ri) { return (le + ri) * (ri - le + 1) / 2; }

int N, Q, L;

struct tree {
    int son[2], siz, le, ri;
    ll sum;
}t[MAXN * 30];

inline int getsiz(int cl, int cr) {
    int len = t[cl].ri - t[cl].le + 1;
    return len - (t[cr].siz - t[cl].siz);
}

inline ll getsum(int cl, int cr){
    ll sum = calc(t[cl].le, t[cl].ri);
    return sum - (t[cr].sum - t[cl].sum);
}

int root[MAXN], cnt;

inline int NewNode(int le, int ri, int s0, int s1, int siz, ll sum){
    int k = ++cnt;
    t[k].son[0] = s0; t[k].son[1] = s1;
    t[k].siz = siz; t[k].sum = sum;
    t[k].le = le; t[k].ri = ri;
    return k;
}

void ins(int le, int ri, int &k, int o){
    k = NewNode(le, ri, t[k].son[0], t[k].son[1], t[k].siz + 1, t[k].sum + o);
    if (le == ri) return;
    int mi = (le + ri) >> 1;
    o <= mi ? ins(le, mi, t[k].son[0], o) : ins(mi + 1, ri, t[k].son[1], o);
}

void Build(int le, int ri, int &k){
    k = NewNode(le, ri, 0, 0, 0, 0);
    if (le == ri) return;
    int mi = (le + ri) >> 1;
    Build(le, mi, t[k].son[0]);
    Build(mi + 1, ri, t[k].son[1]);
}

int getsiz(int le, int ri, int cl, int cr, int L, int R){
    if (L > R) return 0;
    if (L <= le && ri <= R) return ri - le + 1 - getsiz(cl, cr);
    int siz = 0, mi = (le + ri) >> 1;
    if (L <= mi)         siz += getsiz(le, mi, t[cl].son[0], t[cr].son[0], L, R);
    if (mi + 1 <= R) siz += getsiz(mi + 1, ri, t[cl].son[1], t[cr].son[1], L, R);
    return siz;
}

struct ROOT {
    int le, ri, cl, cr;
    inline ROOT (int le = 0, int ri = 0, int cl = 0, int cr = 0) : le(le), ri(ri), cl(cl), cr(cr) {}
    int siz() { return getsiz(cl, cr); }
    inline ll sum() { return getsum(cl, cr); }
}rts[MAXN];

int siz;

void Fix(int le, int ri, int cl, int cr, int L, int R){
    if (L <= le && ri <= R) {
        rts[++siz] = ROOT(le, ri, cl, cr);
        return;
    }
    int mi = (le + ri) >> 1;
    if (L <= mi)     Fix(le, mi, t[cl].son[0], t[cr].son[0], L, R);
    if (mi + 1 <= R) Fix(mi + 1, ri, t[cl].son[1], t[cr].son[1], L, R);
}

ll getsum(int le, int ri, int cl, int cr, int rk){
    int siz = getsiz(cl, cr), mi = (le + ri) >> 1; ll sum = getsum(cl, cr);
    if (siz == rk) return sum;
    siz = getsiz(t[cl].son[0], t[cr].son[0]); sum = 0;
    if (siz) sum = getsum(le, mi, t[cl].son[0], t[cr].son[0], min(siz, rk));
    rk -= min(siz, rk);
    if (rk) sum += getsum(mi + 1, ri, t[cl].son[1], t[cr].son[1], rk);
    return sum;
}

ll calc(int le, int ri, int cl, int cr, int rk) {
    if (cl > cr) return 0;
    siz = 0; Fix(1, L, root[le - 1], root[ri], cl, cr);
    ll sum = 0;
    up (i, 1, siz){
        if (rk == 0) break;
        if (rts[i].siz() <= rk) {
            sum += rts[i].sum();
            rk -= rts[i].siz();
        }else {
            sum += getsum(rts[i].le, rts[i].ri, rts[i].cl, rts[i].cr, rk);
            break;
        }
    }
    return sum;
}

int main(){
    N = read(); Q = read(); L = 1e6 + N;
    Build(1, L, root[0]);
    up (i, 1, N) {
        root[i] = root[i - 1];
        ins(1, L, root[i], read());
    }
    while (Q--) {
        int le = read(), ri = read(), cl = read(), cr = cl + ri - le;
        int n = getsiz(1, L, root[le - 1], root[ri], 1, cl - 1);
        ll sum = calc(le, ri, cl, cr, n), ans = sum - (calc(1, cl - 1) - calc(le, ri, 1, cl - 1, oo));
        sum = calc(le, ri, cl, cr, oo) - sum;
        ans += (calc(cr + 1, L) - calc(le, ri, cr + 1, L, oo)) - sum;
        printf("%lld\n", ans);
    }
    return 0;
}