BZOJ 2445 - 最大团

#数学 #阶乘 #中国剩余定理
Published on 2016-12-13

题目地址

描述

一个 n(n≤2⋅109)n(n\le 2\cdot 10^9) 个点的无向图被叫做是一个 symmetric labeled cliquer 当且仅当该图的任意一个连通子图拥有相同的点数，并且任意一个连通子图都是完全图。现在用 m(m≤2⋅109)m(m\le 2\cdot 10^9) 种颜色给所有的 nn 个点的 symmetric labeled cliquer 染色，可以染相同的颜色，问方案数对 999999599999999599 取模的结果。

分析

我们考虑计算联通块的大小为 dd 的时候的答案，设 fkf_k 为已经确定了 kk 个联通块的方案，转移就是枚举标号最小的点所在的联通块的情况：

fk=fk−1⋅(kd−1d−1) f_{k} = f_{k - 1} \cdot \binom {kd - 1} {d - 1}

设 x=ndx = \frac n d，考虑 fxf_x 的封闭形式：

所以答案为：

m∑d∣nn!d!ndnd! m^{\sum_{d\mid n} \frac {n!} {d!^{\frac n d}{\frac n d}!}}

答案对一个质数 999999599999999599 取模，根据费马小定理， mm 的指数可以对 999999598999999598 取模，分解质因数得到 999999599=2∗13∗5281∗7283999999599 = 2 * 13 * 5281 * 7283，于是我们分别算出指数对每一个质数取模的答案，最后用中国剩余定理合并。因为分子分母中都有阶乘，而且 nn 已经超过了质数的大小，有可能出现 00 没有逆元的情况，所以我们用 BZOJ 2142 - 礼物 的方法来处理阶乘。

代码

//  Created by Sengxian on 2016/12/13.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 2445 阶乘的性质 + 中国剩余定理
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MOD = 999999599, MAX_N = 100;
const int MOD_CNT = 4, MODs[] = {2, 13, 5281, 7283}, MAX_MOD = 7283;
int n, m;

inline int modPow(ll a, int b, int MOD) {
    assert(b >= 0);
    ll res = 1;
    while (b) {
        if (b & 1) (res *= a) %= MOD;
        (a *= a) %= MOD;
        b >>= 1;
    }
    return res;
}

inline void extGCD(ll a, ll b, ll &x, ll &y) {
    if (b == 0) x = 1, y = 0;
    else {
        extGCD(b, a % b, y, x);
        y -= (a / b) * x;
    }
}

inline ll inv(ll n, int MOD) {
    ll x = 0, y = 0;
    extGCD(n, MOD, x, y);
    return x % MOD;
}

ll fact[MAX_MOD];

void prepare(int MOD) {
    fact[0] = 1;
    for (int i = 1; i < MOD; ++i) fact[i] = fact[i - 1] * i % MOD;
}

ll modFact(int n, int MOD, ll &b) {
    if (n < MOD) return fact[n];
    b += n / MOD;
    return modPow(fact[MOD - 1], n / MOD, MOD) * fact[n % MOD] % MOD * modFact(n / MOD, MOD, b) % MOD;
}

inline int calc(int d, int MOD) {
    int x = n / d;
    // n! / [(d!) ^ x * x!]
    ll numerator_a = 1, numerator_b = 0, denominator_a = 1, denominator_b = 0;

    (numerator_a *= modFact(n, MOD, numerator_b)) %= MOD;
    (denominator_a *= modFact(d, MOD, denominator_b)) %= MOD;
    denominator_a = modPow(denominator_a, x, MOD), denominator_b *= x;
    (denominator_a *= modFact(x, MOD, denominator_b)) %= MOD;

    ll a = numerator_a * inv(denominator_a, MOD) % MOD, b = numerator_b - denominator_b;
    (a += MOD) %= MOD;
    return a * modPow(MOD, b, MOD) % MOD;
}

int calc(int MOD) {
    prepare(MOD);
    int t = 0;
    for (int i = 1; (ll)i * i <= n; ++i) if (n % i == 0) {
        (t += calc(i, MOD)) %= MOD;
        if (i * i != n) (t += calc(n / i, MOD));
    }
    return t;
}

int main() {
    int caseNum = readInt();
    while (caseNum--) {
        n = readInt(), m = readInt();

        ll res = 0, w = 0, x = 0, y = 0;
        for (int i = 0, a; i < MOD_CNT; ++i) {
            a = calc(MODs[i]);
            w = (MOD - 1) / MODs[i];
            extGCD(w, MODs[i], x, y);
            (res += w * x % (MOD - 1) * a % (MOD - 1)) %= MOD - 1;
        }

        (res += MOD - 1) %= MOD - 1;

        printf("%d\n", modPow(m, res, MOD));
    }
    return 0;
}
CodeChef CHEFBOOK - Chefbook