2019南京Regional补题

statement: https://www.jisuanke.com/contest/5528
赛中过题: A C H J K

B.Chessboard

这题主要是题面太难读了，我们三个没一个人读出真正的题意...
题意:给一个n*m的方格，有多少种涂色路径使得每次涂完一个格子涂色点的最短路径都能通过已涂色点走出来.
这样就等价于路径上没有"凹"形，特判等于1的情况其他情况的答案就是 $C_{n+m-2}^{m-1}$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2000010;
const int mod = 1e9 + 7;
int fac[N], ifac[N];
int pwm(int a, int b) {
    int res = 1;
    for(; b; b >>= 1, a = (ll) a * a % mod)
        if(b & 1) res = (ll) res * a % mod;
    return res;
}
int C(int n, int m) {
    if(n < m || m < 0) return 0;
    return (ll) fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    fac[0] = ifac[0] = 1;
    for(int i = 1; i < N; i++) {
        fac[i] = (ll) fac[i - 1] * i % mod;
    }
    ifac[N - 1] = pwm(fac[N - 1], mod - 2);
    for(int i = N - 2; i; i--) {
        ifac[i] = (ll) ifac[i + 1] * (i + 1) % mod;
    }
    int _; cin >> _;
    const int inv2 = (mod + 1) / 2;
    while(_--) {
        int n, m; cin >> n >> m;
        int res = 4ll * C(n + m - 2, m - 1) % mod;
        if(n == 1) res = (ll) res * inv2 % mod;
        if(m == 1) res = (ll) res * inv2 % mod;
        cout << res << '\n';
    }
    return 0;
}

E.Observation

$\frac {f(x)}6$ 是积性函数(类似高斯素数)，打表找一下 $f(p^k)$ 的规律，然后直接素数区间筛复杂度为 $O((R-L)logL)$ .

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3200007;
bitset<N> np;
int p[N>>2], pn;
void init() {
    for(int i = 2; i < N; i++) {
        if(!np[i]) p[pn++] = i;
        for(int j = 0; j < pn && i * p[j] < N; j++) {
            np[i * p[j]] = 1;
            if(i % p[j] == 0) break;
        }
    }
}

const int S = 1000010;
ll f[S], rev[S];

void sieve(ll l, ll r) {
    for(ll i = l; i <= r; i++) {
        f[i - l] = 1;
        rev[i - l] = i >> __builtin_ctzll(i);
    }
    //l = max(1ll, l);
    for(int i = 1; i < pn; i++) {
        int pp = p[i];
        int z = pp % 4 == 3;
        if((ll) pp * pp > r) break;
        for(ll k = max((l + pp - 1) / pp * pp, (ll) 2 * pp); k <= r; k += pp) {
            ll zz = 1;
            while(rev[k - l] % pp == 0) {
                zz = zz * pp + z * 2;
                rev[k - l] /= pp;
            }
            f[k - l] *= zz;
        }
    }

    for(ll i = l; i <= r; i++) {
        if(rev[i - l] != 1) {
            f[i - l] = f[i - l] * (rev[i - l] + (rev[i - l] % 4 == 3) * 2);
        }
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    init();
    int _; cin >> _;
    while(_--) {
        ll l, r, k, p;
        cin >> l >> r >> k >> p;
        ll res = 0;
        if(l == 0) res = (1 ^ k) % p;
        l = max(l, 1ll);
        if(l > r) {
            cout << res << '\n';
            continue;
        }
        sieve(l, r);
        for(ll i = l; i <= r; i++) {
            res = (res + ((f[i-l] * 6ll) ^ k)) % p;
        }
        cout << res << '\n';
    }

    return 0;
}

F.Paper Grading

静态情况下可以可持久化字典树或者或者数据结构维护字典树dfs序.
可持久化字典树很难维护，因此带修改情况下用第二种方法.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int kind = 26;
const int N = 1 << 18 | 7;


struct bit_segment_tree {
    int ch[N*80][2], val[N*80], tot;
    int root[N], n, m;
    void init(int _n, int _m) {
        tot = 0;
        n = _n; m = _m;
        for(int i = 1; i <= n; i++) root[i] = 0;
    }
    int newnode() {
        ++tot;
        val[tot] = 0;
        memset(ch[tot], 0, sizeof ch[tot]);
        return tot;
    }
    void ins(int &o, int l, int r, int x, int v) {
        if(!o) o = newnode();
        val[o] += v;
        if(l == r) return;
        int mid = (l + r) >> 1;
        if(mid >= x) ins(ch[o][0], l, mid, x, v);
        else ins(ch[o][1], mid + 1, r, x, v);
    }
    int query(int o, int l, int r, int ql, int qr) {
        if(!o || ql <= l && r <= qr) return val[o];
        int mid = (l + r) >> 1, res = 0;
        if(mid >= ql) res += query(ch[o][0], l, mid, ql, qr);
        if(mid < qr) res += query(ch[o][1], mid + 1, r, ql, qr);
        return res;
    }
    void update(int x, int y, int v) {
        for(; x <= n; x += x&-x)
            ins(root[x], 1, m, y, v);
    }
    int query(int x, int ql, int qr) {
        int res = 0;
        for(; x; x -= x&-x)
            res += query(root[x], 1, m, ql, qr);
        return res;
    }
    int query(int x1, int x2, int y1, int y2) {
        return query(x2, y1, y2) - query(x1 - 1, y1, y2);
    }
} t1;

struct Trie {
    vector<int> id[N];
    int ch[N][kind], rid[N], tot, root;
    int dfn[N], nfd[N], sz[N], dfs_clock;
    void init() {
        tot = 0;
        dfs_clock = 0;
        root = newnode();
    }
    int newnode() {
        ++tot;
        id[tot].clear();
        memset(ch[tot], 0, sizeof ch[tot]);
        return tot;
    }
    void ins(char *s, int idx) {
        int cur = root;
        while(*s) {
            if(!ch[cur][*s-'a']) ch[cur][*s-'a'] = newnode();
            cur = ch[cur][*s-'a'];
            s++;
        }
        id[cur].push_back(idx);
        rid[idx] = cur;
    }
    void dfs(int u) {
        dfn[u] = ++dfs_clock;
        nfd[dfn[u]] = u;
        sz[u] = 1;
        for(int i = 0; i < 26; i++) {
            if(ch[u][i]) {
                dfs(ch[u][i]);
                sz[u] += sz[ch[u][i]];
            }
        }
    }

    void build(int n) {
        dfs(root);
        t1.init(tot, n);
        for(int i = 1; i <= tot; i++) {
            for(auto &e : id[nfd[i]]) {
                t1.update(i, e, 1);
            }
        }
    }
    int go(char *s, int l, int r) {
        int cur = root;
        while(*s) {
            if(ch[cur][*s-'a']) cur = ch[cur][*s-'a'];
            else return 0;
            s++;
        }
        return t1.query(dfn[cur], dfn[cur]+sz[cur]-1, l, r);
    }
    void _swap(int l, int r) {
        if(l == r) return;
        int posl = rid[l], posr = rid[r];
        t1.update(dfn[posl], l, -1);
        t1.update(dfn[posr], l, 1);
        t1.update(dfn[posr], r, -1);
        t1.update(dfn[posl], r, 1);
        swap(rid[l], rid[r]);
    }
} t2;


char s[N];

int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n, q; cin >> n >> q;
    t2.init();
    for(int i = 1; i <= n; i++) {
        cin >> s;
        t2.ins(s, i);
    }
    //return 0;
    t2.build(n);
    for(int i = 0, op, k, l, r; i < q; i++) {
        cin >> op;
        if(op == 1) {
            cin >> l >> r;
            t2._swap(l, r);
        } else {
            cin >> s >> k >> l >> r;
            s[k] = '\0';
            cout << t2.go(s, l, r) << '\n';
        }
    }
    return 0;
}