20191106测试总结

题目过于毒瘤。。。假のCSP，真のNOIplus

我还是直接放Solution和std算了。。。

20191106测试

PS：T2 FSY还提出了另外一种做法。将每个合法区间的左右端点取一个rand值，如果两个节点的前缀异或和相同那么这两点之间就肯定是一个合法区间。离线下来离散化再开个桶记录一下就好了。

T1：WOJ4798

#ifndef K_ON
#define K_ON
#endif

#include <bits/stdc++.h>

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

inline void proc_status()
{
    ifstream t("/proc/self/status");
    cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;
}

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline T read()
{
    register T sum(0), fg(1);
    register char ch(getchar());
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') fg = -1;
    for(;  isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ '0');
    return sum * fg;
}

typedef long long LL;
typedef pair<int, int> pii;

const int MOD = 9990017;

LL n, m, B;

inline void input()
{
    n = read<LL>(), m = read<LL>(), B = read<LL>();
}

inline int fpm(int x, int y)
{
    int res = 1;
    for(; y; y >>= 1, x = (LL) x * x % MOD) if(y & 1) res = (LL) res * x % MOD;
    return res;
}

const int MAXN = (int) pow(1e10, 2.0 / 3);

int fac[MOD], ifac[MOD];
int pre_f0[MAXN + 5];

inline int C0(LL N, LL M) { return N < M ? 0 : (LL) fac[N] * ifac[N - M] % MOD * ifac[M] % MOD; }
inline int C(LL N, LL M) { return N < M ? 0 : (LL) C0(N % MOD, M % MOD) * (N >= MOD ? C(N / MOD, M / MOD) : 1) % MOD; }

inline void MATH_init()
{
    fac[0] = 1;
    for(int i = 1; i < MOD; ++i) fac[i] = (LL) fac[i - 1] * i % MOD;
    ifac[MOD - 1] = fpm(fac[MOD - 1], MOD - 2);
    for(int i = MOD - 2; i >= 0; --i) ifac[i] = (LL) ifac[i + 1] * (i + 1) % MOD;

    for(int i = 1; i <= MAXN; ++i) pre_f0[i] = C(i, B);
    for(int i = 1; i <= MAXN; ++i)
        for(int j = i * 2; j <= MAXN; j += i)
            (pre_f0[j] -= pre_f0[i]) %= MOD;
    for(int i = 1; i <= MAXN; ++i) (pre_f0[i] += pre_f0[i - 1]) %= MOD;
}

unordered_map<LL, int> pre_f;

inline int S(LL N)
{
    if(N <= MAXN) return pre_f0[N];
    if(pre_f.count(N)) return pre_f[N];
    int res = C(N + 1, B + 1);
    for(LL i = 2, j; i <= N; i = j + 1)
    {
        j = N / (N / i);
        res -= (LL) S(N / i) * (j - i + 1) % MOD;
        res = res < 0 ? res + MOD : res;
    }
    return pre_f[N] = res;
}

inline void solve()
{
    MATH_init();

    int ans = 0;
    for(LL i = 1, j; i <= min(n, m); i = j + 1)
    {
        j = min(n / (n / i), m / (m / i));
        (ans += (LL) (S(j) - S(i - 1)) % MOD * (n / i) % MOD * (m / i) % MOD) %= MOD;
    }
    printf("%d\n", (ans + MOD) % MOD);
}

int main()
{
#ifdef K_ON
    freopen("fuwafuwatime.in", "r", stdin);
    freopen("fuwafuwatime.out", "w", stdout);
#endif

    input();
    solve();

    return 0;
}

T2：WOJ4799

// Ho-kago Tea Time

#include <bits/stdc++.h>

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

inline void proc_status()
{
    ifstream t("/proc/self/status");
    cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;
}

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline T read()
{
    register T sum(0), fg(1);
    register char ch(getchar());
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') fg = -1;
    for(;  isdigit(ch); ch = getchar()) sum = sum * 10 - '0' + ch;
    return sum * fg;
}

typedef long long LL;
typedef pair<int, int> pii;

const int MAXN = (int) 1e6;

int n, m;

int p[MAXN * 2 + 5];

inline void input()
{
    n = read<int>(), m = read<int>();
    for(int i = 1; i <= 2 * n; ++i) p[i] = read<int>();
}

namespace TREE
{
    const int MAX_NODE = MAXN * 2;

    int l[MAXN * 2 + 5], r[MAXN * 2 + 5];

    int fa[MAX_NODE + 5];
    vector<int> adj[MAX_NODE + 5];

    const int MAX_LOG = 20;

    int rt[MAX_NODE + 5], dep[MAX_NODE + 5], anc[MAX_LOG + 1][MAX_NODE + 5];

    inline void dfs(int u, int rt0)
    {
        rt[u] = rt0;
        dep[u] = fa[u] == -1 ? 1 : dep[fa[u]] + 1;
        anc[0][u] = fa[u];
        for(int i = 1; (1 << i) < dep[u]; ++i) anc[i][u] = anc[i - 1][anc[i - 1][u]];

        for(auto v : adj[u]) dfs(v, rt0);
    }

    inline void build()
    {
        static vector<int> stk;
        stk.clear();

        for(int i = 1; i <= 2 * n; ++i)
        {
            l[i] = min(i, p[i]);
            r[i] = max(i, p[i]);
            while(!stk.empty() && stk.back() >= l[i])
            {
                int p = stk.back();
                stk.pop_back();
                chkmin(l[i], l[p]);
                chkmax(r[i], r[p]);
            }
            stk.push_back(i);
        }

        for(int i = 0; i <= 2 * n; ++i) rt[i] = fa[i] = -1;
        for(int i = 1; i <= 2 * n; ++i) if(r[i] == i)
        {
            fa[i] = l[i] - 1;
            adj[l[i] - 1].push_back(i);
        }

        r[0] = 0;
        for(int i = 0; i <= 2 * n; ++i) if(!adj[i].empty() && rt[i] == -1) dfs(i, i);
    }

    inline int lca(int u, int v)
    {
        if(dep[u] < dep[v]) swap(u, v);
        for(int k = dep[u] - dep[v], i = 0; (1 << i) <= k; ++i) if(k >> i & 1) u = anc[i][u];
        if(u == v) return u;
        for(int i = MAX_LOG; i >= 0; --i) if((1 << i) < dep[u] && anc[i][u] != anc[i][v]) u = anc[i][u], v = anc[i][v];
        return fa[u];
    }

    inline int query(int r1, int r2) { return rt[r1] == -1 || rt[r2] == -1 || rt[r1] != rt[r2] ? 0 : dep[lca(fa[r1], fa[r2])]; }
}

inline void solve()
{
    TREE::build();
    while(m--)
    {
        int r1 = read<int>(), r2 = read<int>();
        if(r1 == 0 || r2 == 0) puts("0");
        else printf("%d\n", TREE::query(r1, r2));
    }
}

int main()
{
#ifdef K_ON // K-ON!
    freopen("hotchkiss.in", "r", stdin);
    freopen("hotchkiss.out", "w", stdout);
#endif

    input();
    solve();

    return 0;
}

T3：WOJ4800

// Ho-kago Tea Time

#include <bits/stdc++.h>

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

inline void proc_status()
{
    ifstream t("/proc/self/status");
    cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;
}

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline T read()
{
    register T sum(0), fg(1);
    register char ch(getchar());
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') fg = -1;
    for(;  isdigit(ch); ch = getchar()) sum = sum * 10 - '0' + ch;
    return sum * fg;
}

typedef long long LL;
typedef pair<int, int> pii;

const int MOD = 998244353;

inline int fpm(int x, int y)
{
    int res = 1;
    for(; y; y >>= 1, x = (LL) x * x % MOD) if(y & 1) res = (LL) res * x % MOD;
    return res;
}

inline int inv(int x) { assert(x != 0); return fpm(x, MOD - 2); }

namespace NTT
{
    const int MAX_LEN = 1 << 10;

    int rev[MAX_LEN], gn[MAX_LEN], len, dis, inv_len;

    inline void init(int L)
    {
        for(len = 1, dis = 0; len <= L; len <<= 1) ++dis;
        for(int i = 0; i < len; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (dis - 1));

        gn[0] = 1;
        for(int G = fpm(3, (MOD - 1) / len), i = 1; i <= len; ++i) gn[i] = (LL) gn[i - 1] * G % MOD;
        inv_len = inv(len);
    }

    inline void DFT(int *x, int type)
    {
        for(int i = 0; i < len; ++i) if(i < rev[i]) swap(x[i], x[rev[i]]);
        for(int k = 2; k <= len; k <<= 1)
            for(int j = 0; j < len; j += k)
                for(int i = 0; i < k >> 1; ++i)
                {
                    int X = x[i + j], Y = (LL) x[i + j + k / 2] * (type == +1 ? gn[len / k * i] : gn[len - len / k * i]) % MOD;
                    x[i + j] = (X + Y) % MOD;
                    x[i + j + k / 2] = (X - Y) % MOD;
                }
        if(type == -1) for(int i = 0; i < len; ++i) x[i] = (LL) x[i] * inv_len % MOD;
    }

    inline void mul(int *f, int N, int *g, int M, int *s)
    {
        if(N + M == 0) { s[0] = (LL) f[0] * g[0] % MOD; return; }

        static int S[MAX_LEN];

        static const int LIM = 500;
        if(N + M <= LIM)
        {
            for(int i = 0; i <= N + M; ++i) S[i] = 0;
            for(int i = 0; i <= N; ++i) for(int j = 0; j <= M; ++j)
            {
                (S[i + j] += (LL) f[i] * g[j] % MOD) %= MOD;
                S[i + j] = S[i + j] >= MOD ? S[i + j] - MOD : S[i + j];
            }

            for(int i = 0; i <= N + M; ++i) s[i] = S[i];
            return;
        }

        static int F[MAX_LEN], G[MAX_LEN];

        init(N + M);
        for(int i = 0; i < len; ++i) F[i] = i <= N ? f[i] : 0;
        for(int i = 0; i < len; ++i) G[i] = i <= M ? g[i] : 0;
        DFT(F, +1);
        DFT(G, +1);
        for(int i = 0; i < len; ++i) S[i] = (LL) F[i] * G[i] % MOD;
        DFT(S, -1);
        for(int i = 0; i <= N + M; ++i) s[i] = S[i];
    }
}

namespace poly
{
    using NTT::MAX_LEN;

    inline void Inv(int *f, int n, int *s)
    {
        static int F[MAX_LEN], G[MAX_LEN];
        for(int N = 1 << (32 - __builtin_clz(n)), i = 0; i < N; ++i) F[i] = i <= n ? f[i] : 0;

        G[0] = inv(F[0]);
        for(int N = 1; N <= n; N <<= 1)
        {
            static int h[MAX_LEN];

            NTT::mul(F, 2 * N - 1, G, N - 1, h), (--h[0]) %= MOD;
            NTT::mul(G, N - 1, h + N, N - 1, h + N);

            for(int i = 0; i < N; ++i) (G[i] -= h[i]) %= MOD;
            for(int i = N; i < N << 1; ++i) G[i] = -h[i];
        }
        for(int i = 0; i <= n; ++i) s[i] = G[i];
    }

    inline void Mod(int *f, int n, int *g, int m, int *r)
    {
        if(n < m)
        {
            for(int i = 0; i <= n; ++i) r[i] = f[i];
            return;
        }

        static int F[MAX_LEN], G[MAX_LEN];

        for(int i = 0; i <= n; ++i) F[i] = f[n - i];
        for(int i = 0; i <= m; ++i) G[i] = g[m - i];

        static int Q[MAX_LEN];

        Inv(G, n - m, G);
        NTT::mul(F, n - m, G, n - m, Q);
        reverse(Q, Q + n - m + 1);
        NTT::mul(g, m, Q, n - m, F);

        for(int i = 0; i < m; ++i) r[i] = (f[i] - F[i]) % MOD;
    }
}

/*
namespace BM
{
    const int MAXN = (int) 1e4;

    inline int solve(int *fst, int *lst, int *r)
    {
        static vector<int> rs[MAXN + 5];
        static int fail[MAXN + 5], d[MAXN + 5];
        int cnt = 0;

        rs[0].push_back(1);
        for(int t = 0, i = 1, *it = fst; it != lst; ++it, ++i)
        {
            int d0 = 0;
            for(int j = 0; j < SZ(rs[cnt]); ++j) (d0 += (LL) rs[cnt][j] * *(it - j) % MOD) %= MOD;
            d[i] = d0;
            if(d0 == 0) continue;

            fail[cnt] = i;
            if(cnt == 0) { rs[++cnt].push_back(1), rs[cnt].resize(i + 1); continue; }

            vector<int> &res = rs[cnt + 1];
            int k = (LL) -d0 * inv(d[fail[t]]) % MOD;

            res.resize(i - fail[t]);
            for(auto j : rs[t]) res.push_back((LL) k * j % MOD);
            if(SZ(res) < SZ(rs[cnt])) res.resize(SZ(rs[cnt]));
            for(int j = 0; j < SZ(res); ++j) (res[j] += rs[cnt][j]) %= MOD;

            if(i - fail[t] + SZ(rs[t]) >= SZ(rs[cnt])) t = cnt;
            ++cnt;
        }

        for(int i = 0; i < SZ(rs[cnt]); ++i) r[i] = rs[cnt][i];
        return SZ(rs[cnt]) - 1;
    }
}
*/

const int MAXK = 130;

/*
namespace BIT_OPERATOR
{
    int vis[4][4], cur = 0;

    inline int dfs(int x, int y, int S)
    {
        vis[x][y] = cur;

        static const int d[4][2] = {{0, -1}, {-1, 0}, {0, +1}, {+1, 0}};

        int res = 1;
        for(int k = 0; k < 4; ++k)
        {
            int x0 = x + d[k][0], y0 = y + d[k][1];
            if(x0 >= 0 && y0 >= 0 && x0 < 4 && y0 < 4 && (S >> (x0 + y0 * 4) & 1) && vis[x0][y0] != cur) res += dfs(x0, y0, S);
        }
        return res;
    }

    inline bool chk(int S)
    {
        int res = 0;
        for(int x = 0; x < 4; ++x) if(S >> (x + 3 * 4) & 1)
        {
            ++cur, res = dfs(x, 3, S);
            break;
        }
        return res == __builtin_popcount(S);
    }
}
using namespace BIT_OPERATOR;
*/

const int m = 35;

int a[] = {1,1,4,23,117,454,2003,9157,40899,179399,796558,3546996,15747348,69834517,310058192,378623792,122781000,179638924,664040578,693857604,150068224,487780789,81153444,201496361,206356061,443239188,923221963,678050018,834687149,938086801,37535712,164288625,780488339,49747373,890150065,992668567};
int r[] = {-1,-3,3,13,-998244303,-998244230,998244314,998244128,998243694,998242877,-60,-998243251,-998241753,-998238306,-998243864,-2786,-3210,998234787,998243251,3349,1620,6885,-998243300,-1970,998243939,998242095,998243884,548,76,290,77,998244299,-8,-8,998244351,1};

/*
inline void init()
{
    static int blk[1 << 16], cnt = 0;

    for(int S = 1; S < 1 << 16; ++S) if(__builtin_popcount(S) == 4 && chk(S))
        blk[++cnt] = S;

    static int bs[1 << 16];

    bs[0] = 1;
    for(int S = 0; S < 1 << 16; ++S)
        for(int i = 1; i <= cnt; ++i) if(!(S & blk[i]) && ((S >> 12) == 0 || __builtin_clz(S >> 12) > __builtin_clz(blk[i] >> 12)))
            (bs[S | blk[i]] += bs[S]) %= MOD;

    static int dp[MAXK * 2 + 5][1 << 12];
    static int trans[1 << 12][1 << 12];

    for(int S = 0; S < 1 << 12; ++S)
    {
        for(int T = S >> 4; T < 1 << 12; T = (T + 1) | (S >> 4))
        {
            int T0 = (T << 4) | ((1 << 4) - 1);
            if(bs[T0 ^ S]) trans[S][T] = bs[T0 ^ S];
        }
    }

    const int U = (1 << 12) - 1;

    dp[0][U] = 1;
    for(int i = 0; i < MAXK * 2; ++i)
        for(int S = 0; S < 1 << 12; ++S) if(dp[i][S])
            for(int T = 0; T < 1 << 12; ++T)
                (dp[i + 1][T] += (LL) dp[i][S] * trans[S][T] % MOD) %= MOD;

    a[0] = 1;
    for(int i = 1; i <= MAXK * 2; ++i) a[i] = dp[i][U];

    m = BM::solve(a, a + MAXK * 2 + 1, r);
    reverse(r, r + m + 1);

    for(int i = 0; i <= m; ++i) printf("%d,", a[i]);
    puts("");
    for(int i = 0; i <= m; ++i) printf("%d,", r[i]);
    puts("");
}
*/

int n;

inline void input()
{
    n = read<int>();
}

inline void solve()
{
    if(n <= m) { printf("%d\n", (a[n] + MOD) % MOD); return; }

    static int H[MAXK * 2 + 5], X[MAXK * 2 + 5];

    X[0] = 0;
    X[1] = 1;
    H[0] = 1;
    for(int t = n, N = 0, M = 1; t; t >>= 1, NTT::mul(X, M, X, M, X), M *= 2, poly::Mod(X, M, r, m, X), chkmin(M, m - 1)) if(t & 1)
        NTT::mul(H, N, X, M, H), N += M, poly::Mod(H, N, r, m, H), chkmin(N, m - 1);

    int ans = 0;
    for(int i = 0; i < m; ++i) (ans += (LL) a[i] * H[i] % MOD) %= MOD;
    printf("%d\n", (ans + MOD) % MOD);
}

int main()
{
#ifdef K_ON // K-ON!
    freopen("fudepen.in", "r", stdin);
    freopen("fudepen.out", "w", stdout);
#endif

//	init();
    for(int T = read<int>(); T--; )
    {
        input();
        solve();
    }

    return 0;
}

搜索此博客

EarringYYR

20191106测试总结

评论

发表评论

此博客中的热门博文

LOJ6070 【2017 山东一轮集训 Day4」基因】题解

二项式反演

五边形数定理