🌑

☀️

小羊儿的心情天空

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

Camp Day7 Div2

Jan 27, 2019 由小羊

Problem G - 抢红包机器人

一个简单的暴力做法。

枚举第 $i$ 个人为机器人，则根据聊天记录查找所有的机器人，例如floyd-warshall算法或者直接拿bitset维护一下，就可以统计出，在他为机器人的时候，有多少人是机器人。

Problem C - 斐波那契数列

首先可以发现， $x \& (x-1)=x-lowbit(x)$ ，那么

ans = \sum_{i=1}^R F_i-\sum_{i=1}^Rlowbit(F_i)

首先斐波那契数列的求和可以通过矩阵快速幂计算。

\begin{aligned} & F_n = F_{n-1} + F_{n-2} \\ \Leftrightarrow\ & S_n = 2S_{n-1} - S_{n-3} \end{aligned}

\left[\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 2 & 0 & -1\end{matrix}\right]^{n-2}\left[\begin{matrix} S_{0} \\ S_{1} \\ S_{2} \end{matrix}\right] = \left[\begin{matrix} S_{n-1} \\ S_{n} \\ S_{n+1} \end{matrix}\right]

关于 $F_n$ 的lowbit的计算。首先我们可以打表注意到，当 $n\not=3k$ 时， $F_n$ 为奇数。那么考虑 $n=3k$ 时，考虑 $F_n$ 的2的幂次。

\begin{aligned} F_n & = \frac{1}{\sqrt5}\left((\frac{1+\sqrt5}{2})^{3k}+(\frac{1-\sqrt5}{2})^{3k}\right) \\ & = \frac{1}{\sqrt5}\left((2+\sqrt5)^k+(2-\sqrt5)^k\right) \\ & = \frac{1}{\sqrt5}\left(\sum_{i=1}^k C_k^i 2^i \left(\sqrt5^{k-i}-(-\sqrt5)^{k-i}\right)\right) \\ & = \sum_{i=1}^k C_k^i 2^i \left(\sqrt5^{k-i-1}+(-\sqrt5)^{k-i-1}\right) \end{aligned}

当 $k$ 为奇数， $i$ 为奇数时，显然和式项对2的幂次无贡献。当 $k$ 为奇数， $i$ 为偶数的时候，考虑 $i=1$ 即可得到 $F_n$ 中2的幂次为 $1$ 。当 $k$ 为偶数时，考虑 $i=2$ ，可以得到 $lowbit(4k)|F_n$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int mod = 998244353;
lld SS[64] = { 0, 2 };

struct matrix
{
    lld V[3][3];
    matrix() noexcept { memset(V, 0, sizeof(V)); }
    lld& operator()(int a, int b) { return V[a][b]; }

    matrix& operator*=(const matrix b)
    {
        static lld tmp[3][3];
        memset(tmp, 0, sizeof(tmp));

        for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
        {
            for (int k = 0; k < 3; k++)
                tmp[i][j] += V[i][k] * b.V[k][j] % mod;
            tmp[i][j] %= mod;
        }

        memcpy(V, tmp, sizeof(tmp));
        return *this;
    }
};

lld SumFib(lld n)
{
    if (n < 3) return n;
    matrix A, B;
    A(0,0) = A(1,1) = A(2,2) = 1;
    B(0,1) = B(1,2) = 1;
    B(2,0) = -1; B(2,2) = 2;

    n -= 2;
    while (n)
    {
        if (n & 1) A *= B;
        B *= B;
        n >>= 1;
    }

    return (A(2,1) + 2 * A(2,2)) % mod;
}

lld Sum001002(lld R)
{
    lld r6 = R / 6;
    lld ans = (r6 % mod) * 6 % mod;
    lld m6 = R % 6;
    ans += m6;
    if (m6 > 2) ans += 1;
    return ans % mod;
}

int log2(lld ans)
{
    int a = 0;
    while (ans)
        ans >>= 1, a++;
    return a;
}

lld Sum1213(lld R)
{
    if (R == 0) return 0;
    lld R2 = R;
    while ((R2&(-R2)) != R2)
        R2 ^= R2&(-R2);
    return (SS[log2(R2)] + Sum1213(R-R2)) % mod;
}

void solve()
{
    lld R; scanf("%lld", &R);
    lld s1 = SumFib(R);
    lld s2 = Sum001002(R);
    lld s3 = Sum1213(R/6)*4%mod;
    printf("%lld\n", ((s1-s2-s3) % mod + mod) % mod);
}

int main()
{
    for (int i = 2; i < 64; i++)
        SS[i] = (SS[i-1]*2 + (1LL<<(i-1))) % mod;
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}

Problem D - 二次函数

首先可以注意到，将 $F(x)=x^2+ax+b$ 进行水平移动 $F(x-\lfloor a/2\rfloor)$ ，不改变对应相同处的函数值。在平移后，所有的二次函数都可以被规约为 $A(x)=x^2+C_A$ 和 $B(x)=x^2+x+C_B$ 。那么，进行一下分类讨论好了。

当同时存在有 $A(x)$ 和 $B(x)$ 时，令 $A(x)=B(x)$ ，即有 $x=C_A - C_B$ 处两者相交。
当三者均为 $A(x)$ 型时
- 有 $C_1$ 与 $C_2$ 不同奇偶性，令 $A_1(x+1)=A_2(x)$ ，则有 $2x+1+C_1-C_2=0$
- 有 $C_1$ 与 $C_2$ 同奇偶性且 $C_1 \equiv C_2 \mod 4$ ，令 $A_1(x+2)=A_2(x)$ ，则有 $4x+4+C_1-C_2=0$
- 可以证明，如果三个函数各不相同，根据抽屉原理，必定存在上述两种情况之一
当三者均为 $B(x)$ 型时
- 有 $C_1$ 与 $C_2$ 同奇偶性，令 $B_1(x+1)=B_2(x)$ ，则有 $2x+2+C_1-C_2=0$
- 可以证明，如果三个函数各不相同，根据抽屉原理，必定是有两个函数同奇偶性

可以证明，所有函数一定可以规约到以上规范形式。

Problem J - 强壮的排列

和前几天的置置置换是很像的，都是 $p[2n]>\max\lbrace p[2n-1], p[2n+1]\rbrace$ ，但是敦哥哥给了个更适合这题的做法。记 $f_n$ 为长度为 $n$ 的排列符合题目要求的概率，则 $n!f_n$ 就是本题的答案。

考虑到在此序列中， $n$ 为最大数字在 $i$ 的位置，那么我们可以将此序列一切两半，得到这样的一个递推公式。

f_{n} = \frac{1}{n}\sum_{i=1}^{n}f_{n-i}f_{i-1} = \frac{1}{n} \sum_{i+j=n-1} f_i f_j

这个式子可以考虑使用分治FFT来做，复杂度为 $O(n \log^2 n)$ 。

进一步考虑，令 $F(x)=\sum_{n=0}^\infty f_n x^n$ ，那么有

\begin{aligned} nf_n &= \sum_{i=1}^{n}f_{n-i}f_{i-1} \\ \Leftrightarrow\ nf_nx^{n-1} &= \sum_{i+j=n-1}f_i x^i \times f_j x^j \\ \Leftrightarrow\ F'(x) &= F(x)^2 + f_1 \end{aligned}

其中 $f_0=1$ ，根据观察（大雾）可以发现 $F(x) = \tan x = \frac{\sin x}{\cos x}$ 是这个微分方程的一个解。

利用麦克劳林展开，得到 $\sin x$ 和 $\cos x$ 的组合型生成函数表示，然后使用NTT来进行多项式求逆和乘法，即可得到我们的答案。预处理阶乘和阶乘逆元 $O(n)$ ，生成两者多项式 $O(n)$ ，处理逆元 $O(n \log n)$ ，多项式乘法 $O(n\log n)$ ，所以总复杂度是 $O(n \log n)$ 。

#include <bits/stdc++.h>
typedef long long lld, num_t;
using namespace std;
const int mod = 998244353, G=3;
const size_t max_len = 19;
const int MAXN = 524289;
int fac[MAXN], inv[MAXN], invs[MAXN];

void init_factory()
{
    invs[0] = inv[0] = fac[0] = 1;
    inv[1] = fac[1] = invs[1] = 1;
    for (int i = 2; i < MAXN; i++)
    {
        fac[i] = 1LL * fac[i-1] * i % mod;
        inv[i] = 1LL * (mod-mod/i) * inv[mod%i] % mod;
        invs[i] = 1LL * inv[i] * invs[i-1] % mod;
    }
}

inline num_t fpow(lld a, lld k)
{
    lld ans = 1;
    while (k)
    {
        if (k & 1) ans = ans * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return ans;
}

class Fourier
{
public:
    int len, N;

private:
    num_t wmk[1 << max_len];
    int rev[1 << max_len];

    inline num_t create(int m)
    {
        int k = (mod-1)/m;
        if (k < 0) k += mod-1;
        return fpow(G, k);
    }

    void dft(num_t a[], int DFT)
    {
        for (int i = 0; i < N; i++)
            if (i < rev[i])
                swap(a[i], a[rev[i]]);

        for (int m = 2; m <= N; m <<= 1)
        {
            int m2 = m >> 1;
            num_t wm = create(DFT * m);
            wmk[0] = 1;
            for (int j = 1; j < m2; j++)
                wmk[j] = wmk[j-1] * wm % mod;
            num_t t, u;

            for (int k = 0; k < N; k += m)
            {
                for (int j = 0; j < m2; j++)
                {
                    t = wmk[j] * a[k+j+m2] % mod;
                    u = a[k+j];
                    a[k+j] = (u + t) % mod;
                    a[k+j+m2] = ((u - t) % mod + mod) % mod;
                }
            }
        }

        if (DFT == -1)
            for (int i = 0; i < N; i++)
                a[i] = (a[i] * inv[N] % mod + mod) % mod;
    }

public:
    void init(int _len)
    {
        len = _len, N = 1 << _len;
        for (int i = 0; i < N; i++)
            rev[i] = (rev[i>>1]>>1)|((i&1)<<len-1);
    }

    void DFT(num_t a[]) { dft(a, 1); }
    void IDFT(num_t a[]) { dft(a, -1); }

    int log2_ceil2(int len)
    {
        int ans = 0;
        while (len) len >>= 1, ans++;
        return ans;
    }
} trans;

num_t x[MAXN], y[MAXN], dp[MAXN];

void cdqFFT(int L, int R)
{
    if (L == R)
    {
        if (L == 0) dp[L] = 0;
        else if (L == 1) dp[L] = 1;
        else dp[L] = (dp[L] * inv[L] % mod + mod) % mod;
        return;
    }

    int mid = (L + R) >> 1;
    cdqFFT(L, mid);

    int len = R - L + 1;
    trans.init(trans.log2_ceil2(len));

    // x = dp[0], dp[1], dp[2], ..., dp[len], 0, 0, ...
    // y = dp[L], dp[L+1], dp[L+2], ..., dp[mid], 0, 0, ...
    for (int i = 0; i < trans.N; i++)
    {
        x[i] = i < len ? dp[i] : 0;
        y[i] = (i <= mid-L) ? dp[i+L] : 0;
    }

    trans.DFT(x); trans.DFT(y);
    for (int i = 0; i < trans.N; ++i)
        x[i] = x[i] * y[i] % mod;
    trans.IDFT(x);

    for (int i = mid + 1; i <= R; ++i)
        dp[i] = (dp[i] + x[i-L-1] * (L?2:1)) % mod;
    cdqFFT(mid + 1, R);
}

void get_inv(num_t a[], num_t b[], int len)
{
    static num_t A[MAXN], B[MAXN];

    if (len == 1)
    {
        b[0] = fpow(a[0], mod-2);
        return;
    }

    get_inv(a, b, len>>1);
    trans.init(trans.log2_ceil2(len));
    for (int i = 0; i < len; i++)
        A[i] = a[i], B[i] = b[i], A[i+len] = 0, B[i+len] = 0;
    trans.DFT(A); trans.DFT(B);
    for (int i = 0; i < trans.N; i++)
        A[i] = (A[i] * B[i] % mod) * B[i] % mod;
    trans.IDFT(A);

    for (int i = 0; i < len; i++)
        b[i] = (2LL * b[i] % mod - A[i] + mod) % mod;
}

int main()
{
    init_factory();

#ifdef CDQFFT
    // f_n = 1/n * \sum {i+j=n-1} f_i*f_j
    cdqFFT(0, 131071);
#else
    // y for cosx then x for secx
    // then y for sinx then dp for secx+tanx
    for (int i = 0; i < 262144; i++)
        y[i] = (i&1) ? 0 : (i&2) ? mod-invs[i] : invs[i];
    get_inv(y, x, 262144);
    for (int i = 1; i < 262144; i++)
        y[i] = (i&1) ? (i&2) ? mod-invs[i] : invs[i] : 0;
    trans.init(19);
    trans.DFT(x); trans.DFT(y);
    for (int i = 0; i < trans.N; i++)
        dp[i] = x[i] * y[i] % mod;
    trans.IDFT(dp);
#endif

    int T, n; scanf("%d", &T);

    while (T--)
    {
        scanf("%d", &n);
        printf("%lld\n", dp[n] * fac[n] % mod);
    }

    return 0;
}