标签： 数学

$$ \text{设}f\left( n \right) \text{表示}n\text{个节点的二叉树的个数} \\ f\left( 0 \right) =\text{1,}f\left( n \right) =\sum_{0\le i\le n-1}{f\left( i \right) \times f\left( n-1-i \right)}=Cat_n\left( \text{枚举左右子树节点数} \right) \\ \text{设}f\left( n \right) \text{的生成函数为}F\left( x \right) ,\text{则有} \\ F\left( x \right) =xF^2\left( x \right) +1 \\ \text{解得}F\left( x \right) =\frac{1-\sqrt{1-4x}}{2x}\left( \text{另一根无意义} \right) \\ \text{对于}g\left( n \right) \\ g\left( 0 \right) =0 \\ g\left( n \right) =2\sum_{0\le i\le n-1}{g\left( i \right) \times f\left( n-1-i \right)}\left( \text{枚举左子树大小} \right) \\ \text{设}g\left( n \right) \text{的生成函数为}G\left( x \right) \\ G\left( x \right) =2xG\left( x \right) F\left( x \right) +x \\ G\left( x \right) =\frac{x}{\sqrt{1-4x}}=x\left( 1-4x \right) ^{-\frac{1}{2}} \\ \text{现在在于如何求出}\frac{g\left( n \right)}{f\left( n \right)} \\ \left( xF\left( x \right) \right) `=\left( \frac{1-\sqrt{1-4x}}{2} \right) `=\frac{1}{\sqrt{1-4x}}=\frac{G\left( x \right)}{x} \\ \text{因为}\left( xF\left( x \right) \right) `\text{是数列}\left( n+1 \right) f\left( n \right) \text{的生成函数} \\ \text{所以}\left( n+1 \right) f\left( n \right) =g\left( n+1 \right) \\ nf\left( n-1 \right) =g\left( n \right) \\ \text{所以}\frac{g\left( n \right)}{f\left( n \right)}=\frac{nf\left( n-1 \right)}{f\left( n \right)}=\frac{nCat_{n-1}}{Cat_n} \\ Cat_n=\frac{\left( \begin{array}{c} 2n\\ n\\ \end{array} \right)}{n+1} \\ \frac{g\left( n \right)}{f\left( n \right)}=\frac{n\left( n+1 \right)}{2\left( 2n-1 \right)} $$

n=int(input())
print("%.9f"%(n*(n+1)/(2*(2*n-1))))

数论分块板子。

注意next的取值。

#include <iostream>
#include <algorithm>
using int_t = long long int;

int_t S(int_t x)
{
    return x * (x + 1) / 2;
}

int main()
{
    int_t n, k;
    std::cin >> n >> k;
    int_t result = n * k;
    int_t i = 1;
    while (i <= n)
    {
        int_t next;
        if (k / i == 0)
        {
            next = n;
        }
        else
        {
            next = std::min(n, k / (k / i));
        }
        result -= (S(next) - S(i - 1)) * (k / i);
        i = next + 1;
    }
    std::cout << result << std::endl;
    return 0;
}

$$ \sum_{1\le i\le A}{\sum_{1\le j\le B}{\sum_{1\le k\le C}{\sum_{x|i}{\sum_{y|j}{\sum_{z|k}{\left[ gcd\left( x,y \right) ==1 \right] \left[ gcd\left( x,z \right) ==1 \right] \left[ gcd\left( y,z \right) ==1 \right]}}}}}} \\ \sum_{1\le i\le A}{\sum_{1\le j\le B}{\sum_{1\le k\le C}{\sum_{x|i}{\sum_{y|j}{\sum_{z|k}{\left[ gcd\left( x,y \right) ==1 \right] \left[ gcd\left( x,z \right) ==1 \right] \left[ gcd\left( y,z \right) ==1 \right]}}}}}} \\ \sum_{1\le x\le A}{\sum_{1\le i\le \lfloor \frac{A}{x} \rfloor}{\sum_{1\le y\le B}{\sum_{1\le j\le \lfloor \frac{B}{y} \rfloor}{\sum_{1\le z\le C}{\sum_{1\le k\le \lfloor \frac{C}{z} \rfloor}{\left[ gcd\left( x,y \right) ==1 \right] \left[ gcd\left( x,z \right) ==1 \right] \left[ gcd\left( y,z \right) ==1 \right]}}}}}} \\ \sum_{1\le x\le A}{\sum_{1\le y\le B}{\sum_{1\le z\le C}{\lfloor \frac{A}{x} \rfloor \lfloor \frac{B}{y} \rfloor \lfloor \frac{C}{z} \rfloor \sum_{u|x\ and\ u|y}{\mu \left( u \right)}\sum_{v|x\ and\ v|z}{\mu \left( v \right)}\sum_{w|y\ and\ w|z}{\mu \left( w \right)}}}} \\ \sum_{1\le u\le \min \left( A,B \right)}{\sum_{1\le v\le \min \left( A,C \right)}{\sum_{1\le w\le \min \left( B,C \right)}{\mu \left( u \right) \mu \left( v \right) \mu \left( w \right)}}}\sum_{u|x\ and\ u|y}{\sum_{v|x\ and\ v|z}{\sum_{w|y\ and\ w|z}{\lfloor \frac{A}{x} \rfloor \lfloor \frac{B}{y} \rfloor \lfloor \frac{C}{z} \rfloor}}} \\ \sum_{1\le u\le \min \left( A,B \right)}{\sum_{1\le v\le \min \left( A,C \right)}{\sum_{1\le w\le \min \left( B,C \right)}{\mu \left( u \right) \mu \left( v \right) \mu \left( w \right)}}}\sum_{lcm\left( u,v \right) |x}{\lfloor \frac{A}{x} \rfloor \sum_{lcm\left( u,w \right) |y}{\lfloor \frac{B}{y} \rfloor \sum_{lcm\left( w,v \right) |z}{\lfloor \frac{C}{z} \rfloor}}} \\ \text{设}f\left( p,A \right) =\sum_{p|x\ and\ x\le A}{\lfloor \frac{A}{x} \rfloor} \\ \sum_{1\le u\le \min \left( A,B \right)}{\sum_{1\le v\le \min \left( A,C \right)}{\sum_{1\le w\le \min \left( B,C \right)}{\mu \left( u \right) \mu \left( v \right) \mu \left( w \right) f\left( lcm\left( u,v \right) ,A \right) f\left( lcm\left( u,w \right) ,B \right) f\left( lcm\left( w,v \right) ,C \right)}}} \\ \text{可以注意到不为0的}\mu \left( x \right) \text{的个数不多。} \\ \text{可以构建一张图，图中的点是满足}\mu \left( x \right) \text{不为0的}x\text{，两个点}u,v\text{之间有边当且仅当}\mu \left( u \right) \ne \text{0且}\mu \left( v \right) \ne \text{0且}lcm\left( u,v \right) <\max \left( A,B,C \right) \\ \text{可以断定满足}lcm\left( u,v \right) <10^5\text{的}u,v\text{并不多}. \\ \text{所以直接枚举}lcm\left( u,v \right) \text{建图。} \\ \text{如果要满足}\mu \left( u \right) \ne \text{0且}\mu \left( v \right) \ne \text{0,那么一定满足}\mu \left( uv \right) \ne 0. \\ \text{所以枚举所有}\mu \left( x \right) \ne \text{0且}x\le \max \left( A,B,C \right) \text{的}x,\text{枚举}x\text{的质因子集合}S\text{的一个子集}u\text{，然后再枚举}u\text{的一个子集}v \\ \text{这样}lcm\left( v\times \frac{x}{u},u \right) =x\text{显然成立}. \\ \text{设}S=2\times 3\times 5\times 7 \\ u=2\times 5 \\ \text{则如果一个}v\text{满足}lcm\left( u,v \right) =S,\text{那么}v\text{中一定包含质因子5,7,同时可以包含}u\text{的任何一个子集。} \\ \text{建图之后，去掉所有重边和自环。} \\ \text{然后考虑如何枚举三元环。} \\ \text{直接暴力枚举显然是有问题的。} \\ \text{首先把所有无向边重定向为有向边，对于边}\left( u,v \right) ,\text{如果}deg\left( u \right) <deg\left( v \right) ,\text{则让}u\text{指向}v,\text{如果}deg\left( u \right) =deg\left( v \right) , \\ \text{则让编号小的指向编号大的} \\ \text{可以证明，这样每个点的出度不会超过}\sqrt{n} \\ \text{然后直接对于每个点}u\text{，暴力枚举两条出边}\left( u,v \right) \ \left( u,w \right) ,\text{然后看是否满足}lcm\left( v,w \right) \le \max\text{,如果满足，则说明存在无序三元环} \\ \left( u,v,w \right) ,\text{统计进答案。} \\ \text{这只考虑了三元环三个数均不相同的情况，除此之外还需要考虑两个数相同和三个数都相同的情况。} \\ \\ \\ \\ \\ \ $$

#pragma GCC optimize("O3")
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <assert.h>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int_t mod = 1e9 + 7;

const int_t LARGE = 1e5;

char mu[LARGE + 1];
int_t factor[LARGE + 1];
std::vector<int_t> pfactor[LARGE + 1];
int f[4][LARGE + 1];

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
int lcm(int a, int b)
{
    return a / gcd(a, b) * b;
}
void calc_f(int_t id, int_t A)
{
    for (int_t i = 1; i <= A; i++)
    {
        for (int_t j = 1; j * i <= A; j++)
        {
            f[id][i] = (f[id][i] + A / (j * i)) % mod;
        }
    }
}
int prod(int set, int n)
{
    int prod = 1;
    for (size_t i = 0; i < pfactor[n].size(); i++)
    {
        if (set & (1 << i))
            prod *= pfactor[n][i];
    }
    return prod;
}
int_t process(int_t A, int_t B, int_t C)
{
    struct Pair
    {
        int v1, v2;
    };
    static std::vector<int> graph[LARGE + 1];
    static int degree[LARGE + 1];
    std::vector<Pair> edges;
    memset(f, 0, sizeof(f));
    calc_f(1, A);
    calc_f(2, B);
    calc_f(3, C);
    int max = std::max({A, B, C});
    for (int i = 1; i <= max; i++)
    {
        graph[i].clear();
        degree[i] = 0;
    }
    for (int i = 1; i <= max; i++)
    {
        for (int j = 0; j < (1 << pfactor[i].size()); j++)
        {
            int set = j;
            int c = ((1 << pfactor[i].size()) - 1) & (~set);
            for (int k = 0; k <= j; k++)
            {
                if ((k & j) == k)
                {
                    int v1 = prod(j, i), v2 = prod(k | c, i);
                    edges.push_back({v1, v2});
                    degree[v1] += 1;
                    degree[v2] += 1;
                }
            }
        }
    }
    for (const auto &edge : edges)
    {
        if (degree[edge.v1] < degree[edge.v2] || (degree[edge.v1] == degree[edge.v2] && edge.v1 < edge.v2))
        {
            graph[edge.v1].push_back(edge.v2);
        }
    }

    int_t result = 0;
    ///三个点互异的三元环
    const auto f1 = [&](int a, int b, int c) -> int_t {
        int_t res = 0;
        int p = mu[a] * mu[b] * mu[c];
        int ab = lcm(a, b);
        int bc = lcm(b, c);
        int ca = lcm(c, a);
        //(ab)(bc)(ca)
        res = (res + 1ll * ::f[1][ab] * ::f[2][bc] * ::f[3][ca]) % mod;
        //(ab)(ca)(bc)
        res = (res + 1ll * ::f[1][ab] * ::f[2][ca] * ::f[3][bc]) % mod;
        //(bc)(ab)(ca)
        res = (res + 1ll * ::f[1][bc] * ::f[2][ab] * ::f[3][ca]) % mod;
        //(bc)(ca)(ab)
        res = (res + 1ll * ::f[1][bc] * ::f[2][ca] * ::f[3][ab]) % mod;
        //(ca)(ab)(bc)
        res = (res + 1ll * ::f[1][ca] * ::f[2][ab] * ::f[3][bc]) % mod;
        //(ca)(bc)(ab)
        res = (res + 1ll * ::f[1][ca] * ::f[2][bc] * ::f[3][ab]) % mod;
        return (res * p % mod + mod) % mod;
    };
    for (int i = 1; i <= max; i++)
    {
        auto &curr = graph[i];
        for (int j = 0; j < curr.size(); j++)
        {
            for (int k = j + 1; k < curr.size(); k++)
            {
                if (lcm(curr[j], curr[k]) <= max)
                    result = (result + f1(i, curr[j], curr[k])) % mod;
            }
        }
    }
    //有两个点相同的三元环
    const auto f2 = [&](int a, int b) -> int_t {
        // return 0;
        int_t res = 0;
        int p1 = mu[a] * mu[a] * mu[b];
        int p2 = mu[a] * mu[b] * mu[b];
        int ab = lcm(a, b);
        //(ba) (aa) (ab)
        res = (res + 1ll * p1 * ::f[1][ab] * ::f[2][a] * ::f[3][ab]) % mod;
        //(ab) (ba) (aa)
        res = (res + 1ll * p1 * ::f[1][ab] * ::f[2][ab] * ::f[3][a]) % mod;
        //(aa) (ab) (ba)
        res = (res + 1ll * p1 * ::f[1][a] * ::f[2][ab] * ::f[3][ab]) % mod;
        //(bb) (ba) (ab)
        res = (res + 1ll * p2 * ::f[1][b] * ::f[2][ab] * ::f[3][ab]) % mod;
        //(ba) (ab) (bb)
        res = (res + 1ll * p2 * ::f[1][ab] * ::f[2][ab] * ::f[3][b]) % mod;
        //(ab) (bb) (ba)
        res = (res + 1ll * p2 * ::f[1][ab] * ::f[2][b] * ::f[3][ab]) % mod;
        return (res % mod + mod) % mod;
    };
    for (int i = 1; i <= max; i++)
    {
        auto &curr = graph[i];
        for (int j = 0; j < curr.size(); j++)
        {
            result = (result + f2(i, curr[j])) % mod;
        }
    }
    //三个点都相同的三元环
    const auto f3 = [&](int x) -> int_t {
        return (1ll * mu[x] * mu[x] * mu[x] * f[1][x] * f[2][x] % mod * f[3][x] % mod + mod) % mod;
    };
    for (int_t i = 1; i <= max; i++)
    {
        if (mu[i] != 0)
            result = (result + f3(i)) % mod;
    }
    return result;
}
void init()
{

    for (int_t i = 1; i <= LARGE; i++)
    {
        factor[i] = i;
    }
    for (int_t i = 2; i <= LARGE; i++)
    {
        if (factor[i] == i)
        {
            for (int_t j = i * i; j <= LARGE; j += i)
            {
                factor[j] = i;
            }
        }
    }
    mu[1] = 1;
    for (int_t i = 2; i <= LARGE; i++)
    {
        int_t fact = factor[i];
        if (i / fact % fact == 0)
            mu[i] = 0;
        else
            mu[i] = -mu[i / fact];
    }
    for (int_t i = 2; i <= LARGE; i++)
    {
        if (mu[i] == 0)
            continue;
        int_t curr = i;
        while (curr != 1)
        {
            pfactor[i].push_back(factor[curr]);
            curr /= factor[curr];
        }
    }
}
int main()
{
    init();
    int_t T;
    cin >> T;
    for (int_t i = 1; i <= T; i++)
    {
        int_t A, B, C;
        cin >> A >> B >> C;
        cout << process(A, B, C) << endl;
    }
    return 0;
}

$$ \text{计算}\left( \begin{array}{c} n\\ m\\ \end{array} \right) \ mod\ p,\text{满足}p\le 10^6,n,m\le 10^{18},\text{不保证}p\text{是质数} \\ \text{首先可以考虑将}p\text{进行分解，得到}p_1^{k_1}p_2^{k_2}p_{3}^{k_3}…. \\ \text{然后考虑分别计算出}\left( \begin{array}{c} n\\ m\\ \end{array} \right) \ mod\ p_i^{k_i},\text{然后用}CRT\text{进行合并} \\ \text{现在的问题在于如何计算}\frac{n!}{m!\left( n-m \right) !}\ mod\ p_i^{k_i} \\ \text{因为}p_i^{k_i}\text{不是质数，所以不能用卢卡斯定理，但是我们考虑到}p_i^{k_i}\text{中只有}p_i\text{一个质因子，} \\ \text{所以我们可以把}n!\text{中所有的}p_i\text{提出来} \\ \text{例如现在计算11!对}3^2\text{取模} \\ \text{11!}=1\times 2\times 3\times 4\times 5\times 6\times 7\times 8\times 9\times 10\times \text{11\ } \\ =\left( 1\times 2 \right) \times \left( 3 \right) \times \left( 4\times 5 \right) \times \left( 2\times 3 \right) \times \left( 7\times 8 \right) \times \left( 3\times 3 \right) \times \left( 10\times 11 \right) \\ =3^3\times \left( 1\times 2\times 3 \right) \times \left( 1\times 2\times 4\times 5\times 7\times 8\times 10\times 11 \right) \\ =3^3\times \left( 1\times 2\times 3 \right) \times \left( 1\times 2\times 4\times 5\times 7\times 8\times 1\times 2 \right) \\ \text{对于}3^3,\text{额外记录下来，对于}\left( 1\times 2\times 3 \right) ,\text{递归计算,对于}\left( 1\times 2\times 4\times 5\times 7\times 8 \right) \times \left( 1\times 2 \right) ,\text{求出单个循环节和不足一个循环节的部分} \\ \text{每个循环节的长度是}p_i^{k_i}-p_i^{k_i-1},\text{一共循环了}\lfloor \frac{n-\lfloor \frac{n}{p_i} \rfloor}{p_i^{k_i}-p_i^{k_i-1}} \rfloor \text{次,不足一个循环节部分的长度是}\left( n-\lfloor \frac{n}{p_i} \rfloor \right) \ mod\left( p_i^{k_i}-p_i^{k_i-1} \right) \ \\ \text{对于不足一个循环节的部分暴力计算} \\ \text{最后可以得到11!中的3的幂次和除掉3之后的数在模}3^2\text{下的值} \\ \text{复杂度}O\left( p_i^{k_i}\log n \right) \\ \text{这样对于}\left( \begin{array}{c} n\\ m\\ \end{array} \right) =\frac{n!}{m!\left( n-m \right) !},\text{我们可以分别计算出}n!,m!,\left( n-m \right) !\text{中}p_i\text{的幂次和除掉}p_i\text{的幂次的部分，} \\ \text{然后就可以计算了} \\ \\ $$

#include <iostream>
#include <algorithm>
#include <utility>
#include <inttypes.h>
using int_t = int64_t;
using pair_t = std::pair<int_t, int_t>;

using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 1e6;
int_t power(int_t base, int_t index, int_t mod);
int_t gcd(int_t a, int_t b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

pair_t exgcd(int_t a, int_t b)
{
    if (b == 0)
        return pair_t(1, 0);
    auto ret = exgcd(b, a % b);
    return pair_t(ret.second, ret.first - a / b * ret.second);
}

int_t excrt(int64_t *coef, int64_t *mod, int64_t n)
{
    int_t prex = coef[1], M = mod[1];
    for (int_t i = 2; i <= n; i++)
    {
        int_t A = M, B = mod[i];
        int_t C = coef[i] - prex;
        C = (C % B + B) % B;
        int_t gcd = ::gcd(A, B);
        auto x = exgcd(A, B).first;
        x = (x % (B / gcd) + (B / gcd)) % (B / gcd) * (C / gcd);
        int_t preM = M;
        M = M / gcd * mod[i];
        prex = ((prex + x * preM) % M + M) % M;
    }
    return prex;
}
//计算n!中,p的次数和除掉p的幂之后的数对p^k取模的值
void fact(int_t n, int_t p, int_t k, int_t *idx, int_t *rem, int_t *facts)
{
    if (n < p)
    {
        *idx = 0;
        *rem = facts[n];
        return;
    }
    fact(n / p, p, k, idx, rem, facts);
    *idx += n / p;
    int_t prod = 1, remaining = 1;
    int_t count = 0;
    const int_t mod = power(p, k, 998244353);
    int_t length = mod - mod / p;
    for (int_t i = 1; i < mod; i++)
    {
        if (i % p != 0)
        {
            prod = prod * i % mod;
            if (count < (n - n / p) % length)
            {
                remaining = remaining * i % mod;
                count++;
            }
        }
    }
    (*rem) = (*rem) * power(prod, (n - n / p) / (length), mod) % mod * remaining % mod;
}

//计算C(n,m)对p^k取模的结果
int_t C(int_t n, int_t m, int_t p, int_t k)
{
    static int_t fact[LARGE + 1];
    int_t mod = power(p, k, 998244353);
    const int_t phi = mod - (mod / p);
    fact[0] = 1;
    for (int_t i = 1; i < p; i++)
        fact[i] = fact[i - 1] * i % mod;
    int_t idx1, idx2, idx3, rem1, rem2, rem3;
    ::fact(n, p, k, &idx1, &rem1, fact);
    ::fact(m, p, k, &idx2, &rem2, fact);
    ::fact(n - m, p, k, &idx3, &rem3, fact);
    int_t index = idx1 - (idx2 + idx3);
    int_t remaining = rem1 * power(rem2 * rem3 % mod, phi - 1, mod) % mod;
    return power(p, index, mod) * remaining % mod;
}

int main()
{
    int_t n, m, p;
    cin >> n >> m >> p;
    static int_t index[LARGE + 1];
    static int_t prime[LARGE + 1];
    static int_t mod[LARGE + 1];
    static int_t coef[LARGE + 1];
    int_t used = 0;
    for (int_t i = 2; i <= p && p != 1; i++)
    {
        if (p % i == 0)
        {
            used++;
            prime[used] = i;
            while (p % i == 0)
            {
                index[used]++;
                p /= i;
            }
        }
    }
    for (int_t i = 1; i <= used; i++)
    {
        mod[i] = power(prime[i], index[i], 998244353);
        coef[i] = C(n, m, prime[i], index[i]);
    }
    cout << excrt(coef, mod, used) << endl;
    return 0;
}
int_t power(int_t base, int_t index, int_t mod)
{
    int_t result = 1;
    while (index)
    {
        if (index & 1)
            result = result * base % mod;
        base = base * base % mod;
        index >>= 1;
    }
    return result;
}