2019 南昌Regional补题

statement:https://www.jisuanke.com/contest/5530
赛中过题: B C E G L

J.Summon

看到循环同构问题就想到polya计数.
然后相当于求解无循环同构下的子问题.
我们可以状压, 设为开头状态为S1,末尾状态为S2的方案数... 和只要取到即可..
这样子暴力转移的复杂度为，算一下极限情况下1.6e9.
但是有用的值只有（的约数个数）个,打表发现[1,n]约数个数最多的数只有128个，然后我们可以用矩阵来做转移,这样复杂度为,算一下大概3e8左右.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < n; i++)
const int N = 1e5 + 7;
const int mod = 7*17<<23|1;

int power_mod(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;
}

struct Matrix {
    static const int S = 64;
    int e[S][S];
    void clear() { memset(e, 0, sizeof e);}
    Matrix() { clear();}
    void E() { clear(); rep(i,S)e[i][i]=1;}
    Matrix operator * (const Matrix&rhs)const {
        Matrix res;
        rep(i,S)rep(k,S)if(e[i][k])rep(j,S)
            res.e[i][j]=(res.e[i][j]+(ll)e[i][k]*rhs.e[k][j])%mod;
        return res;
    }
    Matrix power(ll n) const {
        Matrix a = *this, res;
        for(res.E(); n; n>>=1,a=a*a)
            if(n&1) res=res*a;
        return res;
    }
};
Matrix A;
struct Info {
    int e, phi;
    Info operator * (const Info &rhs) const {
        return Info{e*rhs.e, phi*rhs.phi};
    }
};

vector<Info> getInfo(int n) {
    vector<Info> res(1, Info{1, 1});
    for(int i = 2; i * i <= n; i++) {
        if(n % i == 0) {
            Info a = {i, i - 1};
            int t = 1;
            while(n % i == 0) n /= i, t++;
            int sz = res.size(), nsz = sz * t;
            res.resize(nsz);
            for(int j = sz; j < nsz; j++) {
                if(j == 2 * sz) a.phi++;
                res[j] = res[j - sz] * a;
            }
        }
    }
    if(n != 1) {
        int sz = res.size(), nsz = sz * 2;
        res.resize(nsz);
        Info a = {n, n - 1};
        for(int j = sz; j < nsz; j++) {
            res[j] = res[j - sz] * a;
        }
    }
    return res;
}

const int S1 = (1 << 6) - 1;
const int S2 = (1 << 8) - 1;
int n, m;
bool ok[256];
bool can[64][64];
int sum[64];

int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
//    freopen("out1.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 0, x; i < m; i++) {
        int mask = 0;
        for(int j = 0; j < 4; j++) {
            cin >> x;
            mask = mask << 2 | x;
        }
        ok[mask] = 1;
    }
    for(int j = 0; j < 64; j++)
        for(int i = 0; i < 64; i++)
            for(int z = 2; z <= 6; z += 2)
                can[j][i] |= ok[(i<<z|j>>6-z)&S2];
    for(int i = 0; i < 64; i++)
        for(int j = 0; j < 4; j++)
            A.e[i][(i<<2|j)&S1] = !ok[i<<2|j];
    vector<Info> Z = getInfo(n);
    int sz = Z.size();
    for(int i = 0; i < sz - 1 - i; i++)
        swap(Z[i].phi, Z[sz - 1-  i].phi);
    int res = 0;
    int t1 = 0, t2 = 0;
    for(int i = 0; i < 4; i++) {
        int mask = i << 6 | i << 4 | i << 2 | i;
        if(!ok[mask]) t1 += 1;
    }
    for(int i = 0; i < 16; i++) {
        int mask = i << 8 | i << 4 | i;
        if(!ok[mask&S2]&&!ok[mask>>2&S2]) t2 += 1;
    }
    for(auto &e : Z) {
        if(e.e >= 3) {
            Matrix t = A.power(e.e - 3);
            int tans = 0;
            for(int i = 0; i < 64; i++)
                for(int j = 0; j < 64; j++)
                    if(!can[i][j]) tans = (tans + t.e[i][j]) % mod;
            res = (res + (ll) tans * e.phi) % mod;
        } else if(e.e == 2) {
            res = (res + (ll) t2 * e.phi) % mod;
        } else if(e.e == 1) {
            res = (res + (ll) t1 * e.phi) % mod;
        }
    }
    res = (ll) res * power_mod(n, mod - 2) % mod;
    cout << res << '\n';
    return 0;
}

K.Tree

树上启发式合并+线段树合并(计蒜客评测机太慢了,加快读勉强卡过...)
还有一种方法是pb_ds+启发式合并.

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define fi first
#define se second
const int N = 2e5 + 10;
int root[N], ch[N*80][2], val[N*80], tot;
void init() {
    tot = 0;
}
int newnode() {
    ++tot;
    val[tot] = 0;
    memset(ch[tot], 0, sizeof ch[0]);
    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 x) {
    if(!o || r <= x) return val[o];
    int mid = (l + r) >> 1;
    int res = query(ch[o][0], l, mid, x);
    if(mid < x) res += query(ch[o][1], mid + 1, r, x);
    return res;
}
int Union(int u, int v) {
    if(!u || !v) return u + v;
    int rt = newnode();
    val[rt] = val[u] + val[v];
    ch[rt][0] = Union(ch[u][0], ch[v][0]);
    ch[rt][1] = Union(ch[u][1], ch[v][1]);
    return rt;
}

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
int n, k;
vector<int> E[N];
map<int, int> S[N];
int a[N], dep[N];
int maxdep = 0;
ll res = 0;

void calc(int o1, int o2, int l, int r, int du) {
    if(!o2 || k < l - du * 2) return;
    if(l == r) {
        res += 2 * val[o2] * query(o1, 1, maxdep, min(k - l + du * 2, maxdep));
        return;
    }
    int mid = (l + r) >> 1;
    calc(o1, ch[o2][0], l, mid, du);
    calc(o1, ch[o2][1], mid + 1, r, du);
}
void U(map<int, int> &a, map<int, int> &b, int v, int du) {
    if(a.size() < b.size()) swap(a, b);
    for(auto &e : b) {
        auto it = a.find(2 * v - e.fi);
        if(it != a.end()) {
            calc(it->se, e.se, 1, maxdep, du);
        }
    }
    for(auto &e : b) {
        a[e.fi] = Union(a[e.fi], e.se);
    }
}
void prepare(int u, int f) {
    dep[u] = dep[f] + 1;
    maxdep = max(maxdep, dep[u]);
    for(auto &v : E[u]) prepare(v, u);
}

void dfs(int u, int f) {
    for(auto &v : E[u]) {
        dfs(v, u);
        U(S[u], S[v], a[u], dep[u]);
    }
    ins(root[u], 1, maxdep, dep[u], 1);
    S[u][a[u]] = Union(S[u][a[u]], root[u]);
}

namespace Fastio {
    inline char nextchar() {
        static char buf[N], *p1=buf, *p2=buf;
        return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++;
    }
    template<class T> int _R(T &x) {
        char c = nextchar(); T sign = 1;
        while(!isdigit(c)&&c!=EOF)
            c=nextchar(),sign=c=='-'?-1:sign;
        if(c==EOF) return -1;
        for(x=0; isdigit(c); c=nextchar())
            x=(x<<3)+(x<<1)+(c&15);
        x *= sign;
        return 1;
    }
    template<class T, class...Args>
    int _R(T &x, Args&...args) { return min(_R(args...), _R(x));}
    template<class T> void W(T x) { if(x)W(x/10), putchar(x%10+'0');}
    template<class T> void _W(T x) { if(!x)putchar('0'); if(x<0)putchar('-'),x=-x; W(x);}
    template<class T> void _Wn(T x) { _W(x); putchar('\n');}
    template<class T, class...Args>
    void _Wn(T x, Args...args) { _W(x), putchar(' '), _Wn(args...);}
};
using namespace Fastio;

int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
#endif
    _R(n, k);
    for(int i = 1; i <= n; i++) {
        _R(a[i]);
    }
    for(int i = 2, f; i <= n; i++) {
        _R(f);
        E[f].push_back(i);
    }
    prepare(1, 0);
    dfs(1, 0);
    _Wn(res);
    return 0;
}

M.XOR Sum

对于我们对分奇偶讨论一下就能得到表达式...
最后会化成若干项比较好求和的部分和一个自然幂级数.
用多项式求逆预处理出伯努利数然后做卷积即可.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int p = 1e9 + 7;
const db pi = acos(-1.0);
int power_mod(int a, int b) {
    int res = 1;
    for(; b; b >>= 1, a = (ll) a * a % p)
        if(b & 1) res = (ll) res * a % p;
    return res;
}


namespace FFT {
    struct Comp {
        db x, y;
        Comp(){}
        Comp(db _x, db _y = 0) : x(_x), y(_y){}
        Comp operator + (const Comp &rhs) const {
            return Comp(x + rhs.x, y + rhs.y);
        }
        Comp operator - (const Comp &rhs) const {
            return Comp(x - rhs.x, y - rhs.y);
        }
        Comp operator * (const Comp &rhs) const {
            return Comp(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x);
        }
        Comp operator / (const db &r) const {
            return Comp(x / r, y / r);
        }
        friend Comp conj(const Comp &r) { return Comp(r.x, -r.y);}
    };
    Comp Exp(const db &r) { return Comp(cos(r), sin(r));}
    const int L = 18, N = 1 << L;
    Comp roots[N];
    int rev[N];
    void fft_init() {
        for(int i = 0; i < N; i++) {
            rev[i] = (rev[i>>1]>>1)|((i&1)<<L-1);
        }
        roots[1] = {1, 0};
        for(int i = 1; i < L; i++) {
            db angle = 2 * pi / (1 << i + 1);
            for(int j = 1 << i - 1; j < 1 << i; j++) {
                roots[j << 1] = roots[j];
                roots[j<<1|1] = Exp((j * 2 + 1 - (1 << i)) * angle);
            }
        }
    }
    void fft(Comp *a, int n, int idft = 0) {
        assert((n & (n - 1)) == 0);
        int zeros = __builtin_ctz(n), shift = L - zeros;
        for(int i = 0; i < n; i++) {
            if(i < (rev[i] >> shift)) {
                swap(a[i], a[rev[i] >> shift]);
            }
        }
        for(int i = 1; i < n; i <<= 1) {
            for(int j = 0; j < n; j += i * 2) {
                for(int k = 0; k < i; k++) {
                    Comp z = a[i + j + k] * (idft ? conj(roots[i + k]) : roots[i + k]);
                    a[i + j + k] = a[j + k] - z;
                    a[j + k] = a[j + k] + z;
                }
            }
        }
        if(idft) for(int i = 0; i < n; i++) a[i] = a[i] / n;
    }
    const Comp half = 0.5, zero = 0;
    const int M = (1 << 15) - 1;
    Comp fa[N], fb[N];
    void conv(int *a, int *b, int *c, int l1, int l2, int eq = 0) {
        int need = l1 + l2 - 1, sz = 1 << (32 - __builtin_clz(need - 1));
        for(int i = 0; i < sz; i++) {
            fa[i] = i < l1 ? Comp(a[i]&M, a[i]>>15) : zero;
        }
        fft(fa, sz);
        if(eq) memcpy(fb, fa, sz * sizeof(Comp));
        else {
            for(int i = 0; i < sz; i++) {
                fb[i] = i < l2 ? Comp(b[i]&M, b[i]>>15) : zero;
            }
            fft(fb, sz);
        }
        for(int i = 0; i <= (sz >> 1); i++) {
            int j = (sz - i) & (sz - 1);
            Comp xx = fa[i] * fb[i];
            Comp yy = conj(fa[j]) * fb[i];
            Comp zz = fa[i] * conj(fb[j]);
            Comp ww = conj(fa[j]) * conj(fb[j]);
            if(i != j) {
                Comp _x = fa[j] * fb[j];
                Comp _y = conj(fa[i]) * fb[j];
                Comp _z = fa[j] * conj(fb[i]);
                Comp _w = conj(fa[i]) * conj(fb[i]);
                fa[j] = (_x + _y) * half;
                fb[j] = (_z - _w) * half;
            }
            fa[i] = (xx + yy) * half;
            fb[i] = (zz - ww) * half;
        }
        fft(fa, sz, 1);
        fft(fb, sz, 1);
        ll d[4];
        for(int i = 0; i < need; i++) {
            d[0] = fa[i].x + 0.5;
            d[1] = fa[i].y + 0.5;
            d[2] = fb[i].x + 0.5;
            d[3] = fb[i].y + 0.5;
            c[i] = (((d[2] % p) << 30) + d[0] + ((d[1] + d[3]) % p << 15)) % p;
        }
    }
    void sqr(int *a, int *b, int l) { conv(a, a, b, l, l, 1);}
    void poly_inv(int *a, int *b, int len) {
        static int t[N];
        if(len == 1) return b[0] = power_mod(a[0], p - 2), void(b[1] = 0);
        poly_inv(a, b, (len + 1) >> 1);
        sqr(b, t, (len + 1) >> 1);
        conv(a, t, t, len, len);
        for(int i = (len + 1) >> 1; i < len; i++) {
            b[i] = (-t[i] + p) % p;
        }
    }
}
using namespace FFT;

int fac[N], ifac[N], B[N];
int a[N], b[N], c[N];

int t;
ll x, y;

int ff(ll n) {
    if(n == 0) return 0;
    int z = (n + 1) % p, now = z;
    b[0] = 0;
    for(int i = 1; i <= t + 1; i++) {
        b[i] = (ll) now * ifac[i] % p;
        now = (ll) now * z % p;
    }
    conv(a, b, c, t + 1, t + 2);
    int res = 0, aa = 1;
    for(int k = 1; k <= t; k++) {
        aa = (ll) aa * 2ll * k % p;
        res = (res + (ll) c[k + 1] * aa) % p;
    }
    return res;
}

int g(ll n) {
    if(n == 0) return 0;
    ll t1 = (n + 3) / 4 % p * t % p;
    ll t2 = (n + 2) / 4 % p;
    ll t3 = (n + 1) / 4 % p * (t / 2) % p;
    ll t4 = ff(n / 2);
    return (t1 + t2 + t3 + t4) % p;
}

int test_k = 1;
int C(int n, int m) {
    if(n < m || m < 0) return 0;
    return (ll) fac[n] * ifac[m] % p * ifac[n - m] % p;
}
int test(ll n) {
    int res = 0, now = (n + 1) % p;
    for(int i = test_k; i >= 0; i--) {
        res = (res + (ll) C(test_k + 1, i) * B[i] % p * now) % p;
        now = (ll) now * (n + 1) % p;
    }
    res = (ll) res * fac[test_k] % p * ifac[test_k + 1] % p;
    return res;
}


int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    fft_init();
    cin >> t >> x >> y;
    /*
    int r = 0;
    for(int i = x; i <= y; i++) {
        r += F(i, t);
    }
    cout << r << endl;*/
    //t = 1000;
    fac[0] = ifac[0] = 1;
    for(int i = 1; i <= t + 10; i++) {
        fac[i] = (ll) fac[i - 1] * i % p;
    }
    ifac[t + 10] = power_mod(fac[t + 10], p - 2);
    for(int i = t + 9; i; i--) {
        ifac[i] = (ll) ifac[i + 1] * (i + 1) % p;
    }
    poly_inv(ifac + 1, B, t + 5);
    for(int i = 0; i <= t + 5; i++) {
        a[i] = B[i];
        B[i] = (ll) B[i] * fac[i] % p;
    }

    int res = (g(y) - g(x - 1)) % p;
    if(res < 0) res += p;


    cout << res << '\n';
    return 0;
}