🌑

☀️

小羊儿的心情天空

我的博客我的实验友情链接

2019 ICPC南昌网络赛部分题解

Sep 8, 2019 由小羊

A. Enju with Math Problem

给定欧拉函数表中连续100项，求是否存在或从哪个点开始。

考虑和去年EC筛 $\mu^2(n)$ 一样的思路，检查 $5, 7, 9, 11, 13, 17, 23$ 的倍数所在位置，利用中国剩余定理求解可能位置，然后利用区间筛筛出该区间的欧拉函数，对比。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MAXN = 2e4+5;
int pri[MAXN], pcn; bool isnp[MAXN];
int test[100], qaq[100], phi[100];

void init_prime()
{
    for (int i = 2; i < MAXN; i++)
    {
        if (!isnp[i]) pri[pcn++] = i;
        for (int j = 0; j < pcn; j++)
        {
            if (i * pri[j] >= MAXN) break;
            isnp[i * pri[j]] = true;
            if (i % pri[j] == 0) break;
        }
    }
}

int check(int y)
{
    phi[0] = qaq[0] = y;
    for (int i = 1; i < 100; i++)
        phi[i] = qaq[i] = qaq[i-1] + 1;

    int stt = qaq[0];
    if (stt <= 0 || qaq[99] > 150000000) return -1;

    for (int i = 0; i < pcn; i++)
    {
        int ft = ((stt - 1) / pri[i] + 1) * pri[i] - stt;
        for (int j = ft; j < 100; j += pri[i])
        {
            phi[j] = phi[j] / pri[i] * (pri[i] - 1);
            while (qaq[j] % pri[i] == 0) qaq[j] /= pri[i];
        }
    }

    for (int i = 0; i < 100; i++)
        if (qaq[i] > 1)
            phi[i] = phi[i] / qaq[i] * (qaq[i] - 1);
    for (int i = 0; i < 100; i++)
        if (test[i] != phi[i])
            return -1;
    return stt;
}

lld extgcd(lld a, lld b, lld &x, lld &y)
{
    if (!b) return x = 1, y = 0, a;
    lld d = extgcd(b, a % b, y, x);
    return y -= (a / b) * x, d;
}

pair<lld,lld> modeqs(lld b[], const int w[], int k)
{
    lld bj = b[0], wj = w[0], x, y, d;
    for (int i = 1; i < k; i++)
    {
        b[i] %= w[i]; d = extgcd(wj, w[i], x, y);
        if ((bj - b[i]) % d != 0) return make_pair(0LL, -1LL);
        x = x * (b[i] - bj) / d % (w[i] / d), y = wj / d * w[i];
        bj = ((bj + x * wj) % y + y) % y, wj = y;
    }
    return make_pair(bj, wj);
}

int bs[8][25]; lld b[8];
const int m[8] = { 6, 4, 6, 10, 12, 16, 18, 22 };
const int W[8] = { 9, 5, 7, 11, 13, 17, 19, 23 };
vector<int> poss[8];

int dfs(int i)
{
    if (i == 8)
    {
        auto getAns = modeqs(b, W, 8);
        if (getAns.first == 0) return -1;
        return check(getAns.first);
    }
    else
    {
        for (auto v : poss[i])
        {
            b[i] = W[i] - v;
            int t = dfs(i+1);
            if (t > 0) return t;
        }

        return -1;
    }
}

int solve()
{
    memset(bs, 0, sizeof(bs));
    for (int i = 0; i < 8; i++)
        poss[i].clear();

    for (int i = 0; i < 100; i++)
    {
        scanf("%d", &test[i]);
        for (int j = 0; j < 8; j++)
            if (test[i] % m[j] == 0)
                bs[j][i % W[j]]++;
    }

    for (int i = 0; i < 8; i++)
        for (int j = 0; j < W[i]; j++)
            if (bs[i][j] >= 100 / W[i])
                poss[i].push_back(j);
    return dfs(0);
}

int main()
{
    init_prime();
    int T; scanf("%d", &T);

    while (T--)
    {
        int ans = solve();
        if (ans == -1) printf("NO\n");
        else printf("YES\n%d\n", ans);
    }

    return 0;
}

D. Interesting Series

考虑 $F_n = 1 + a + a^2 + \cdots + a^{n-1} = \frac{a^n - 1}{a-1}$

那么所求相当于是

Answer(K) = \frac{\sum_{s \in K} a^s - C_{N}^{|K|}}{a-1}

考虑构造多项式

f(n) = \prod_{i=1}^n (1 + a^s x)

那么所求 $\sum_{s \in K} a^s$ 就是 $f(n)$ 的 $x^{|K|}$ 项系数之和。

分治FFT计算即可。注意到模数比较小，所以考虑用double或者long double跑FFT，但是要注意预处理精度（感谢Claris姐姐呜呜呜），不能多次乘。

#include <bits/stdc++.h>
typedef long long lld;
const double PI = acos(-1.0);
const int MOD = 100003;
typedef std::complex<double> cplx;
int fac[MOD], inv[MOD], invs[MOD];

void dft(cplx a[], int DFT, int N) {
    static int rev[1<<20]; static cplx w[1<<20], ww[1<<20];
    for (int i = 0; i < N; i++) {
        rev[i] = (rev[i>>1]>>1)|((i&1)?N>>1:0);
        if (i < rev[i]) swap(a[i], a[rev[i]]);
        w[i] = cplx(cos(PI*i/N), sin(PI*i/N));
        ww[i] = cplx(w[i].real(), -w[i].imag());
    }
    for (int d = 0, ctz = __builtin_ctz(N); (1<<d) < N; d++) {
        cplx u, t; int m2 = 1<<d, m = m2<<1;
        for (int k = 0; k < N; k += m)
            for (int j = 0; j < m2; j++)
                t = (DFT==1?w:ww)[j<<(ctz-d)] * a[k+j+m2], u = a[k+j],
                a[k+j] = u + t, a[k+j+m2] = u - t;
    }
    if (DFT == -1) for (int i = 0; i < N; i++) a[i] /= N;
}

lld fpow(lld a, lld k) {
    lld b = 1;
    for (; k; k>>=1, a=a*a%MOD)
        if (k&1) b=b*a%MOD;
    return b;
}

int t[131072], ss[MOD], a;

void solve(int l, int r, int L, int R)
{
    if (R - L <= 31)
    {
        int len = R-L+1, sz = 1;
        for (int i = 0; i < len; i++) t[L+i] = !i;
        for (int w = l; w <= r; w++, sz++)
            for (int i = sz; i > 0; i--)
                (t[L+i] += t[L+i-1] * fpow(a, ss[w]) % MOD) %= MOD;
    }
    else
    {
        int mid = (L+R)>>1, m = (l+r)>>1, len=R-L+1;
        solve(l, m, L, mid), solve(m+1, r, mid+1, R);
        static cplx a[131072], b[131072];
        for (int i = 0; i < len/2; i++)
            a[i] = t[L+i], b[i] = t[mid+1+i],
            a[len/2+i] = b[len/2+i] = 0;
        dft(a, 1, len), dft(b, 1, len);
        for (int i = 0; i < len; i++) a[i] *= b[i];
        dft(a, -1, len);
        for (int i = 0; i < len; i++)
            t[L+i] = lld(a[i].real()+0.5) % MOD;
    }
}

int main()
{
    inv[0] = fac[0] = invs[0] = invs[1] = inv[1] = fac[1] = 1;
    for (int i = 2; i < MOD; i++)
        fac[i] = 1ll * fac[i-1] * i % MOD,
        inv[i] = 1ll * (MOD-MOD/i) * inv[MOD%i] % MOD,
        invs[i] = 1ll * invs[i-1] * inv[i] % MOD;

    int N, Q, s;
    scanf("%d %d %d", &N, &a, &Q);
    for (int i = 1; i <= N; i++)
        scanf("%d", &ss[i]);
    int sz = 30, st = 32;
    while (sz < N) sz <<= 1, st <<= 1;
    solve(1, N, 0, st-1);

    while (Q--)
    {
        scanf("%d", &s);
        lld ans = t[s] - 1ll * fac[N] * invs[s] * invs[N-s] % MOD;
        ans = (ans + MOD) * inv[a-1] % MOD;
        printf("%lld\n", ans);
    }

    return 0;
}

话说回来补题的时候一直没过竟然是因为……输出答案时那个组合数写错了呜呜呜，变量意义改变不改名，调试两行泪。

H. The Nth Item

考虑作出 $f(n+x) = a \times f(n) + b \times f(n+1)$ 的表达式，然后分段打表。

#include <cstdio>
using namespace std;
typedef long long lld;
const int MAXN = 5e5+5;
const int MOD = 998244353;
int trans[1002][2], f[MAXN][2];

int main()
{
    trans[0][0] = trans[1][1] = f[0][1] = 1;

    for (int i = 2; i <= 1001; i++)
    {
        trans[i][0] = 2ll * trans[i-1][1] % MOD;
        trans[i][1] = (trans[i-1][0] + 3ll * trans[i-1][1]) % MOD;
    }

    for (int i = 1; i < MAXN; i++)
    {
        f[i][0] = (1ll * trans[1000][0] * f[i-1][0] + 1ll * trans[1000][1] * f[i-1][1]) % MOD;
        f[i][1] = (1ll * trans[1001][0] * f[i-1][0] + 1ll * trans[1001][1] * f[i-1][1]) % MOD;
    }

    int Q; lld N; scanf("%d %lld", &Q, &N);
    lld lastAns = N, tot = 0; N = 0;

    for (int i = 0; i < Q; i++)
    {
        lld now = lastAns ^ N; N = now; now %= (MOD-1)/2;
        lld ans = (1ll * trans[now%1000][0] * f[now/1000][0] + 1ll * trans[now%1000][1] * f[now/1000][1]) % MOD;
        tot ^= ans; lastAns = ans * ans;
    }

    printf("%lld\n", tot);
    return 0;
}