Sparse Table

稀疏表,又称ST表,预处理 O(n \log n),查询 O(1)

st[i][j] 表示在数组中,[i,i+2^j-1] 区间的最值。

当我们需要查询 [L,R] 的最值时,由于 R-L+1 可能不是正好 2^j 形式,那么我们可以考虑用某个 j,查询 [L,L+2^j-1][R-2^j+1,R],并使这两个区间交叠。

int a[1010];
int st[1010][12];

void init(int n)
{
    for (int i = 0; i < n; i++)
        st[i][0] = a[i];
    for (int j = 1; (1<<j) <= n; j++)
        for (int i = 0; i+(1<<j)-1 < n; i++)
            st[i][j] = min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
}

int search(int l, int r)
{
    int k = int(log2(r-l+1.0));
    return min(st[l][k], st[r-(1<<k)+1][k]);
}

并且由代码可以看出,它还可以处理区间最大值/最值坐标等。

Camp Day7 Div2

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_AB(x)=x^2+x+C_B。那么,进行一下分类讨论好了。

  • 当同时存在有 A(x)B(x) 时,令 A(x)=B(x),即有 x=C_A – C_B 处两者相交。

  • 当三者均为 A(x) 型时

    • C_1C_2 不同奇偶性,令 A_1(x+1)=A_2(x),则有 2x+1+C_1-C_2=0
    • C_1C_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_1C_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;
}

Camp Day5 Div2

Problem A – Gactus Draw

由于有要求边不能有公共点,那么我们可以让每颗子树都相离较远。如果我们将树的 dfs序 作为横坐标,depth 作为纵坐标,那么构造出来的图形一定是符合要求的。

Problem C – Division

题中的操作相当于将数字进行一次右移,相当于减去了某个某个指定的数值。

如果我们将会被减去的数记录下来,至多 32n 个,那么先把和保存下来,然后减去的数保存下来排个序,把最前面至多 k 个数字加进和即可。

Problem F – Kropki

考虑做一个状压dp,记为 dp[S][n],表示以状态 S 排布的数字以 n 为结尾的方案数,其中 S 中已选上的元素数量为 c(S)。另外点的01串存在 stat[] 中。那么有

dp[S][n] = \begin{cases} \sum_{u=2n,n/2} dp[S-\lbrace n \rbrace][u], & stat[c(S)]=1 \\ \sum_{u\not= 2n,n/2}dp[S-\lbrace n\rbrace][u], & stat[c(S)]=0 \end{cases}

然后计算即可。可以写成搜索的形式,用起bitset,然后记忆化,这样写法似乎会舒服一点(大雾)。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int LEN = 1 << 15;
const int mod = 1e9+7;
lld dp[LEN][16], n, dpt;
char st[20];

lld dfs(int S, int end)
{
    bitset<15> wtf(S);
    size_t len = wtf.count();
    if (!wtf[end-1]) return 0;
    if (len == 1) return 1;
    if (dp[S][end] != -1) return dp[S][end];

    lld ans = 0;
    wtf.flip(end-1);
    dpt++;
    for (int i = 1; i <= n; i++)
    {
        if (!wtf[i-1]) continue;

        if (end == i * 2)
        {
            if (st[len-2] == '1')
                ans += dfs(wtf.to_ulong(), i);
        }
        else if (i == end * 2)
        {
            if (st[len-2] == '1')
                ans += dfs(wtf.to_ulong(), i);
        }
        else
        {
            if (st[len-2] == '0')
                ans += dfs(wtf.to_ulong(), i);
        }
    }

    return dp[S][end] = ans % mod;
}

int main()
{
    memset(dp, -1, sizeof(dp));
    scanf("%lld %s", &n, st);
    lld ans = 0;
    for (int i = 1; i <= n; i++)
        ans = (ans + dfs((1<<n)-1, i)) % mod;
    printf("%lld\n", ans);
    return 0;
}

很迷啊,不会写最原始的状压dp,所以只能写写这种奇怪的东西了。

Problem H – Nested Tree

考虑一棵树的每对点间距离和的一个性质:对于某个边 e(u,v),在距离和中的贡献是 u 侧的节点数乘以 v 侧节点数。那么,我们可以利用一次dfs,对以某节点为根的子树进行搜索,统计出子树中的节点个数 x,则边另一侧的节点个数为 nm-x,所以答案就可以很轻松的维护出来。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int mod = 1e9+7;
vector<int> G[1000010];
bool vis[1000010];
int n, m;
long long ans;

int dfs(int u)
{
    if (vis[u]) return -1;
    vis[u] = true;

    int cnt = 1;
    for (auto v : G[u])
    {
        int x = dfs(v);
        if (x == -1) continue;
        ans += 1LL * x * (n*m - x) % mod;
        cnt += x;
    }

    return cnt;
}

int main()
{
    int a, b, u, v;
    scanf("%d %d", &n, &m);

    for (int i = 1; i < n; i++)
    {
        scanf("%d %d", &u, &v);

        for (int j = 0; j < m; j++)
        {
            G[j*n+u].push_back(j*n+v);
            G[j*n+v].push_back(j*n+u);
        }
    }

    for (int i = 1; i < m; i++)
    {
        scanf("%d %d %d %d", &a, &b, &u, &v);
        G[(a-1)*n+u].push_back((b-1)*n+v);
        G[(b-1)*n+v].push_back((a-1)*n+u);
    }

    assert(dfs(1) == n*m);
    printf("%lld\n", (ans % mod + mod) % mod);
    return 0;
}

Problem J – Special Judge

线段相交的判断。

Camp Day4 Div2

Problem G – 置置置换

满足条件的排列的模样是这样的:

\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\cdots

那么它的对偶排列是这样的

\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\uparrow\downarrow\cdots

先证明一个引理:已有一个符合条件的长度为 n 的排列时,对于任意一个 i,将该排列中所有大于等于 i 的元素增一,那么排列的增减性不变。由于排列具有局部性质,那么我们可以只考虑一个局部。如果局部中最小的元素增大了,那么最大的元素同时增大;如果局部中较大的元素增大了,那么不影响大小的偏序关系。

于是想要生成长度为 n 的排列时,可以从长度为 n-1 的排列转移而来。考虑生成以 i 为起始元素的排列,我们可以将所有大于 i 的对偶子串接在后面,并将该子串中大于 i 的元素增一。这样,我们就可以得到排列的构造方式了。

dp[n][s] 为长度为 n 的序列,以 s 为起始元素的排列个数,那么满足这样的一个转移方程:

dp[n][s] = \sum_{i=n-s+1}^{n-1} dp[n-1][i]

由于数据范围 1 \le n \le 1000,那么这样转移是 O(n^3) 的。观察到 dp[n-1][i] 在后期不会被修改,并且这是一个前缀和的形式,那么我们可以令

qzh[n][s] = \sum_{i=1}^{s} dp[n][s]

这样我们可以边转移边求前缀和,并且新的转移方程

dp[n][s] = qzh[n-1][n-1] – qzh[n-1][n-s]

这样的转移是 O(n^2) 的。

Problem A – 夺宝奇兵

观察走的路线可以知道:在路线中,A_{1,0}A_{2,0}+A_{2,1}A_{1,1}A_{1,0}A_{2,1}+A_{2,0}A_{1,1} 这两种组合方式必然二选一,并且 A_{n,0}A_{n,1} 一定是会选入的,那么直接一遍扫描计算答案即可。

Problem F – 小小马

首先会知道,马每次跳会改变目标点的奇偶性。所以,如果起终点的奇偶性相同,那么不同颜色点必然是不同的。所以这时候可以忽略。

然后当宽度为 2 时,马只能左前右后跳,所以简单判断一下。如果 n=3,m=3,那么 (2,2) 和其他点就是孤立的,所以判断一下。当更大时,马可以跳满全场,所以~

Problem I – 咆咆咆哮

显然把所有的魔术性卡牌放在最后,这样魔法加成是最大的。因为不知道答案的攻击性卡牌数量,那么可以来一个枚举。

假设目前枚举的是有 x 张攻击性卡牌,那么有 n-x 张魔术性卡牌。考虑利用一个新的权值 c_i=a_i-b_i,那么

\sum_{x \in X}a_x + \sum_{x \not\in X}b_x = \sum_{x \in X}c_x + \sum_{i=1}^n b_i

所以贪心的选择 c_ix 大的几张卡牌作为攻击性卡牌,就可以得到这样的一个权值。对每种枚举的最大值取最大,就可以得到这道题的答案了。

Camp Day3 Div2

Problem B – 集合

一个计算几何题目,如果两人线段与圆相交,那么作切线然后再绕圆弧走;如果两人线段与圆相离,那么两人汇合点与圆心连线是汇合点与两人之间的角平分线,二分即可。(目前不是AC代码)

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const double eps = 1e-8;
const double PI = acos(-1.0);
inline int sgn(double t) { return fabs(t) < eps ? 0 : t > 0 ? 1 : -1; }

struct point
{
    double x, y;
    point operator+(const point &a) const { return point(x+a.x, y+a.y); }
    point operator-(const point &a) const { return point(x-a.x,y-a.y); }
    double operator^(const point &a) const { return x*a.y-y*a.x; }
    double operator*(const point &a) const { return x*a.x+y*a.y; }
    point operator/(double a) const { return point(x/a, y/a); }
    point operator*(double a) const { return point(x*a, y*a); }
    double length() const { return sqrt(x*x+y*y); }
    point(double _x, double _y) noexcept { x = _x; y = _y; }
    double rad(const point &a, const point &b) { point q(a-*this), r=(b-*this); return acos(q*r/q.length()/r.length()); }
    point regulize(double len) { return *this/(length()/len); }
    double arg() const { return atan2(y, x); }
};

struct line
{
    double A, B, C;
    const point &s, &e;
    line(const point &a, const point &b) noexcept : s(a), e(b) { A = B = C = 0; }
    void load() { A = e.y - s.y; B = s.x - e.x; C = s.y*(e.x-s.x) - (e.y-s.y)*s.x; }
    double dis(const point &a) const { return fabs(A*a.x + B*a.y + C) / sqrt(A*A + B*B); }
    double disP2seg(point p) { if (sgn((p-s)*(e-s))<0 || sgn((p-e)*(s-e))<0) return min((p-s).length(),(p-e).length()); else return dis(p); }
};

struct circle : point
{
    double r;
    circle() noexcept : point(0,0) { r = 0; }
    bool seg(line v) { double dst = v.disP2seg(*this); return sgn(dst-r)<0; }
};

point A1(0,0), A2(0,0);
line px(A1, A2);
circle C;

double ans_seg()
{
    // line corrupts circle
    double bigRad = C.rad(A1, A2);
    double d1 = (A1-C).length();
    double d2 = (A2-C).length();
    double sRad1 = acos(C.r / d1);
    double sRad2 = acos(C.r / d2);
    double dd1 = sqrt(d1*d1-C.r*C.r);
    double dd2 = sqrt(d2*d2-C.r*C.r);
    double ans = dd1 + dd2 + C.r*(bigRad-sRad1-sRad2);
    return ans;
}

double f(double alpha)
{
    point A3 = (A1-C)*alpha + (A2-C)*(1-alpha) + C;
    return A3.rad(A1, C) - A3.rad(A2, C);
}

double ans_bs()
{
    double l = 0.0, r = 1.0, m;
    double fl = f(l), fr = f(r), fm;

    while (r - l > eps)
    {
        m = (r+l)/2;
        fm = f(m);
        if (sgn(fl) * sgn(fm) > 0)
            l = m, fl = fm;
        else
            r = m, fr = fm;
    }

    // so now m is the correct alpha percent.
    point A3 = ((A1-C)*m + (A2-C)*(1-m)).regulize(C.r) + C;
    return (A1-A3).length() + (A2-A3).length();
}

void solve()
{
    scanf("%lf %lf %lf %lf", &A1.x, &A1.y, &A2.x, &A2.y);
    scanf("%lf %lf %lf", &C.x, &C.y, &C.r); px.load();
    printf("%.3lf\n", C.seg(px) ? ans_seg() : ans_bs());
}

int main()
{
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}

Problem F – 小清新数论

对于 1 \le n \le 10^7 (for div2) 或 1 \le n \le 10^{11}

ans = \sum_{i=1}^n\sum_{j=1}^n\mu(\gcd(i,j))

那么对于div2来说,可以暴力枚举 \gcd(i,j) 的值,也可以进一步继续推算,即

\begin{aligned} ans & = \sum_{d=1}^n\mu(d)\times\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=d] \\ & = \sum_{d=1}^n\mu(d)\times\sum_{k=1}^{\lfloor n/d\rfloor}\mu(k)\left\lfloor\frac{n}{dk}\right\rfloor^2 \\ & = \sum_{t=1}^n\left\lfloor\frac{n}{t}\right\rfloor^2\sum_{dk=t}\mu(d)\mu(k) \end{aligned}

那么显然后面那个是 \mu * \mu,也是个积性函数,可以用线性筛来完成。对于div1来说,这时候需要用到 O(n^\frac23) 的杜教筛来完成工作。

f(n)=\sum_{dk=n}\mu(d)\mu(k),现在欲求 F(n)=\sum_{i=1}^nf(i)。考虑 M(n)=\sum_{i=1}^n\mu(i),以及 \mu * \mu * 1 = \mu * e = \mu,那么有

F(n)=M(n)-\sum_{d=2}^nF\left\lfloor\frac{n}{d}\right\rfloor

由于杜教筛主要计算的是 F(n/i)M(n/i) 的值,并且存在记忆化,那么两个函数的计算实际上仍然是原来的复杂度,只要线性筛预处理前 O(n^\frac23) 的前缀和,后面这个函数计算复杂度依然是 O(n^\frac23)

然后在实际写代码的时候遇到了一个坑点:(n/k)*(n/k)神tm会爆long long我没注意到。。

#include <bits/stdc++.h>
typedef long long lld;
using namespace std;
const size_t MAXN = 1e7+5;
const int mod = 998244353;
char isnp[MAXN], miu[MAXN];
int pcn, pri[MAXN], mm[MAXN];
int _M1[MAXN], _F1[MAXN];
map<lld,lld> _M2, _F2;

void init_prime()
{
    miu[1] = mm[1] = _M1[1] = _F1[1] = 1;
    for (int i = 2; i < MAXN; i++)
    {
        if (!isnp[i])
        {
            miu[i] = -1;
            mm[i] = -2;
            pri[pcn++] = i;
        }

        for (int j = 0; j < pcn; j++)
        {
            int k = i * pri[j];
            if (k >= MAXN) break;
            isnp[k] = 1;
            if (i % pri[j] == 0)
            {
                miu[k] = 0;
                mm[k] = ((i/pri[j])%pri[j]==0) ? 0 : mm[i/pri[j]];
                break;
            }
            else
            {
                miu[k] = -miu[i];
                mm[k] = -2*mm[i];
            }
        }

        _M1[i] = (_M1[i-1] + miu[i]) % mod;
        _F1[i] = (_F1[i-1] + mm[i]) % mod;
    }
}

lld M(lld n)
{
    if (n < MAXN) return _M1[n];
    else if (_M2.count(n)) return _M2[n];

    lld ans = 1;
    for (lld k = 2, fk; k <= n; k = fk+1)
    {
        fk = n / (n/k);
        ans -= (fk-k+1)*M(n/k)%mod;
    }

    ans = (ans % mod + mod) % mod;
    return _M2[n] = ans;
}

lld F(lld n)
{
    if (n < MAXN) return _F1[n];
    else if (_F2.count(n)) return _F2[n];

    lld ans = M(n);
    for (lld k = 2, fk; k <= n; k = fk+1)
    {
        fk = n / (n/k);
        ans -= (fk-k+1)*F(n/k)%mod;
    }

    ans = (ans % mod + mod) % mod;
    return _F2[n] = ans;
}

int main()
{
    init_prime();
    lld n; scanf("%lld", &n);
    lld ans = 0;

    for (lld k = 1, fk; k <= n; k = fk+1)
    {
        fk = n / (n/k);
        ans += (((n/k)%mod)*((n/k)%mod))%mod * (F(fk)-F(k-1)) % mod;
    }

    ans = (ans % mod + mod) % mod;
    printf("%lld\n", ans);
    return 0;
}

Problem G – 排列

简单题,过。

Camp Day2 Div2

Problem J – Cosmis Cleaner

这题是个三维的计算几何,需要比较强的微积分知识。不过现场还是推了球缺公式的:

V(h,r) = \int_h^r \pi(r^2-x^2)dx = \frac{2\pi}3r^3-\pi r^2h+\frac\pi3h^3

其中 h 为球心到切割屏幕的距离。另外很容易得到两球交平面解析式与点到平面距离公式:

d_0=\frac{|Ax_0+By_0+Cz_0+D|}{\sqrt{A^2+B^2+C^2}}

然后根据球在空间中的不同位置进行分类讨论即可。

ans_n = \begin{cases}0, & 球在区域外 \\ V(-r_n, r_n), & 球在区域内 \\ V(h_0,r_0)+V(d,r_n), & 球一大半在外 \\ V(h_0,r_0)+V(-d,r_n), & 球一大半在内 \end{cases}

其中 h_0 为清除区域球心到交面距离,d 为被切割的球到交面的距离。

Problem A – Erase Numbers II

即选择两个数字,使得两者以字符串连接的形式得到的数字最大。

为了使数字最大,那么选取的数字必然是长度最长的两个。而且,最大的数字一定会被选到,因为:如果最大的数字在拼接数字的前部,那么没有比前部更大的;如果最大的数字在拼接数字的后部,那么当前部取最大时没有比后部更大的。

那么,我可以忽略另外一个数字的长度第二长条件,假装不知道的给最大的数和另外所有的数来一次拼接,用sprintf和sscanf再带上unsinged long long就可以完成一个 O(n) 的贪心。

比赛时的锅:

  • 队友给出了一个分类讨论的思想,然后写的比较混乱。
  • 后期有了这种贪心的思想的时候却不知20位数字如何比较大小,没有意识到ull和int128的可行性,然后就用strcmp演自己了。

Problem B – Erase Numbers I

利用后缀数组转化为一个字符串匹配问题,将整个大的连接串分割为三个部分。

但是目前还不太会字符串的有关内容QAQ寒假回去一定会恶补!

Camp Day1 Div2

CCPC Wannafly Winter Camp 自闭总结系列

Problem B – 吃豆豆

当时确实有想到将时间 t 作为一维,但是由于不敢确定 t 的范围,所以换了种思路。

dp[c][x][y] 为吃到 c 颗豆豆并且当前坐标在 (x,y) 时的时间。那么它可以由吃到 c-1 颗豆豆时的算法转移过来,大概是这样的一个公式:

dp[c][x][y] = \min\left\lbrace dp[c-1][x’][y’]+|x’-x|+|y’-y|+\Delta t, dp[c-1][x][y]+T[x][y]\right\rbrace

其中 \Delta t(x,y) 处豆豆产生时间的一个取整。当然了,c=1 和最后实际答案需要一个简单的转移。实际上这个吃到正好 c 颗的说法是不准确的,因为可以在前来的路上吃到更多的豆豆,但是,如果可以吃到更多的豆豆,那么这个值会存在吃到实际豆豆数的那个状态里。描述应该改为“吃到至少 c 颗豆豆”。时间复杂度是 O(Cn^2m^2),可以说是很糟糕了。

那么最原始的思路便是处理 dp[t][x][y] 了。可以从问题的实际意义也就是上下左右移动和不移动看出来:

dp[t][x][y] = \min\left\lbrace dp[t-1][x’][y’] + \left[T[x][y]\% t==0\right] \right\rbrace

利用这个公式,可以去做倍增来达到div1的 10^{18} 数量级。这类题我将在之后认真研究,虽然有点咕的欲望但是我会找人监督我的!

在做这道题的过程中,出现了以下的锅:

  • 由于没弄准确delta的意义,加错括号位置了。
  • 没有注意到第一次处理时的公式写法,导致了一个鬼畜错误。

记录下来。

Problem C – 拆拆数

这题一开始简单设置了几个样例,计算了一下,然后猜的结论:互质是 1 组,不互质是 2 组。当时想,如果能够构造出来,那么就相当于证明了这一猜想的正确性。可惜想偏了,在往 \gcd(A,B) 的方向想。

这题的正确证明需要用到一个性质:100 以内的素数有很多个,相乘之后超过 10^{18}。由于 AB 都不超过这个范围,不论有没有超过 100 的素因子,那么必然存在一个 100 以内的素数 p,那么 p \nmid A \wedge p\nmid B

所以,构造的方案是 (a_1, a_2, b_1, b_2)=(p, A – p, B – p, p) 即可。其中证明只需要用到 \gcd(a,b)=\gcd(a-b,b)

那么没做出来的锅:

  • 当时脑子里已经全是最大公约数构造,思路偏了。

Problem F – 爬爬爬山

挖山嘛,由于体力的势能那样的意义,其实只要把山挖到零势能面就可以啦,不需要继续往下挖。这题模型很容易让人联想到最短路,并且是无负权的图。既然是无负权图,那么一定不会走出一个环,即不会走到某个点两次。由无负权最短路联想到 dijkstra,由每个点只能走到一次莫名其妙想到了…网络流拆点。(???什么鬼脑洞)那么,如果有了拆点这个操作,入点与出点之间连接的边的意义就很明显了:dls挖山的花费。如果最短路会经过这座山,也就是经过这座山的入点和出点,那么挖山的费用也就加入了最短路的cost。

其中,拆点的具体做法是这样的:

将所有入边连接到 i 号点,出边的起始点选为 i+n,然后在 ii+n 之间连一条挖山花费的边就好了。是把一个无向图通过拆点变成了一个有向图呢!运行 dijkstra 堆优化版本即可通过。

那么多WA很多发的锅:

  • 自己只有脑洞,却没有认真练习过做图论题,连现成用的熟悉的模板都找不到。
  • 队友拆点连边错误没有看出来。
  • 队友交代码前没有认真审阅,没有注意到爆int的可能,也因为他使用宏定义而没有立刻发现输入的问题。以后拒绝使用任何 #define

寒假的时候要对图论类题目进行专项练习,不能和之前抱学长大腿的时候只会数论组合那样了,要成为一个全面型的选手,不然有组合题也不会dp计算(雾),有图论计数也不知道怎么整一个生成函数(呜呜呜)。

数论筛小结

简单的整理了一下目前自己会的鬼畜东西QAQ

埃拉托斯特尼筛 / 普通筛

这个可能是小学课本就讲过的素数筛法吧。

每一个数(非1)的倍数一定是合数,那么把这些数字打上标记就可以了。

T(n) = O\left(\sum_{i=2}^{n}\left\lfloor\frac{n}{i}\right\rfloor\right) \approx O\left(\int_1^n\frac{n}{x}dx\right) = O(n \log n)

最大的问题是,一个数如果之前被枚举到了,那么对它的倍数进行枚举是无用的操作。如果我们对已经打过标记的数不再枚举它的倍数,那么我们的复杂度约为 O(n \log \log n)

那么为什么今天我要提它呢?因为。我们可以来大区间素数筛选啊!

考虑这样的一个问题:求出 [a,b] 内的所有素数,其中 a \le 10^9, b-a \le 10^6。显然不能用线性筛。

我们可以发现这样的一个性质:[a,b] 中的每个合数,最大质因子一定不会超过 \sqrt{b}

那么,这个筛就可以拿去用啦~

欧拉筛 / 线性筛

考虑某个数出现平方项后不再筛选它,就有了欧拉筛法。

对于任意一个整数 n,如果它有一些的质数幂次超过1,那么它会被最小的那个质数筛选到。

如果没有,那么它会被最大的质因子筛选到。

另外介绍一下积性函数的概念:

f 是定义在 Z^+ 上的函数,如果满足 gcd(n,m)=1 则有 f(n)f(m) = f(nm),那么称为它是积性函数。

常见的积性函数有:

  • 欧拉函数 \varphi(n) = \sum_{i=1}^n [gcd(i,n)=1]

  • 莫比乌斯函数 \mu(n) = (-1)^k\ or\ 0

  • 元函数 e(n) = [n=1]

  • 恒等函数 1(n) = 1

  • 单位函数 id(n) = n

  • 幂函数 id^k(n) = n^k

  • 除数函数 \sigma_k(n) = \sum_{d|n} d^k

  • 约数个数函数 d(n) = \sum_{d|n}1

  • 约数和函数 \sigma(n) = \sum_{d|n}d

我们在做素数筛选的时候,由于我们的分界条件很明显,以两个数是否互质为标准,于是我们可以顺便求出可乘函数的所有值。

欧拉筛法代码如下。并且,由于每个数只会被访问一次,所以我们认为它的时间复杂度是 O(n)​ 的。

char miu[MAXN], c[MAXN], isnp[MAXN];
int phi[MAXN], d[MAXN], pri[MAXN], pcn;

void init_prime()
{
    isnp[0] = isnp[1] = 1;
    miu[1] = phi[1] = d[1] = 1;
    for (int i = 2; i < MAXN; i++)
    {
        if (!isnp[i])
        {
            pri[pcn++] = i;
            c[i] = 1;
            d[i] = 2;
            miu[i] = -1;
            phi[i] = i-1;
        }

        for (int j = 0; j < pcn; j++)
        {
            int k = i * pri[j];
            if (k >= MAXN) break;
            isnp[k] = 1;
            if (i % pri[j] == 0)
            {
                c[k] = c[i] + 1;
                d[k] = d[i] / c[k] * (c[k]+1);
                miu[k] = 0;
                phi[k] = phi[i] * pri[j];
                break;
            }
            else
            {
                c[k] = 1;
                d[k] = 2 * d[i];
                miu[k] = -miu[i];
                phi[k] = phi[i] * (pri[j]-1);
            }
        }
    }
}

狄利克雷卷积

f(n), g(n) 是积性函数,我们称
(f*g)(n)=\sum_{i\times j=n}f(i)g(j)
是这两个函数的狄利克雷卷积。很容易证明,f * g 依然是个积性函数。

那么,设 G=\lbrace f\ |\ f\ is\ multiplicative\ function\rbrace * 是按上述规则构成的运算,那么 (G, *) 构成了一个阿贝尔群,我们称这个群为积性函数的狄利克雷卷积群,其单位元就是 e(n)=[n=1]

列举群中的几个常见运算吧。

\mu * 1 = e

\varphi * 1=id

id * \mu = \varphi

1*1=d

\mu * d = 1

id * 1 = \sigma

id^k * 1 = \sigma_k

没错。其实在这个群中,\mu1 互为逆元。

杜教筛

显然对于积性函数 f(n) 和较大的 n \ge 10^{12},我们很难线性计算 S(n) = \sum_{i=1}^n f(n)

我们希望能找到一个 g(n),使得它们的狄利克雷卷积的求和尽可能方便地计算。
\sum_{k=1}^n \sum_{ij=k} g(i)f(j) = \sum_{i=1}^n\sum_{j=1}^{\lfloor n/i \rfloor}g(i)f(j) = \sum_{i=1}^ng(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)

所以有
g(1)S(n) = \sum_{i=1}^n(f*g)(i) – \sum_{i=2}^ng(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)
显然后面那个东西是可以进行分块计算的。

假设我们对 g(n)(f*g)(n) 求和是线性的,那么计算的时间复杂度为

T(n) = O\left(\sum_{i=1}^{\sqrt{n}}\sqrt{i}\right) + O\left(\sum_{i=1}^{\sqrt{n}}\sqrt{\left\lfloor\frac{n}{i}\right\rfloor}\right) \approx O\left(\int_0^{\sqrt{n}}\sqrt{\frac{n}{x}}dx\right) = O\left(n^\frac{3}{4}\right)

如果我们可以先用线性筛预处理出 S(n) 的前 n^\frac23 项,那么

T(n) = O\left(\sum_{i=1}^{n/k}\sqrt{\frac{n}{i}}\right) = O\left(\frac{n}{\sqrt{k}}\right) = O\left(n^\frac{2}{3}\right)

我们就可以 O(n^\frac23) 计算了。

例如对于莫比乌斯函数的前缀和与欧拉函数的前缀和,我们有

\begin{aligned} & M(n) = \sum_{d=1}^n\mu(d) = 1-\sum_{d=2}^nM\left(\left\lfloor\frac{n}{d}\right\rfloor\right) \\\\ & \phi(n) = \sum_{d=1}^n\varphi(d) = \frac{n(n+1)}2-\sum_{d=2}^n\phi\left(\left\lfloor\frac{n}{d}\right\rfloor\right) \\\\ & B(n) = \sum_{d=1}^nd\varphi(d) = \frac{n(n+1)(2n+1)}6-\sum_{d=2}^ndB\left(\left\lfloor\frac{n}{d}\right\rfloor\right) \end{aligned}

洲阁筛

占坑

min_25筛

占坑

快速沃尔什变换

新的卷积

卷积的东西都很好玩呀。有时间一定好好学泛函.jpg

前面提到了,离散傅里叶变换的多项式卷积是对于每个 k 获得 i+j=k\sum a_i \times a_j,而在数论中比较多的狄利克雷卷积是对于每个 k 获得 i \times j = k\sum a_i \times a_j。在实际题目中,我们可能会遇到这样的一类卷积:

对于每个 k,获得 i \otimes j = k\sum a_i \times a_j。其中 \otimes 是任意按位逻辑运算,如 \&, |, \oplus 等。

很显然,我们如果按照最朴素的枚举方法:先枚举 i,再获得可行的 k,复杂度是 O(n^2) 朝上走的。如果 n \ge 10^5 不就完蛋了吗。按照这个架势,我们应该是要找复杂度为 O(n\log n)O(n \log \log n)O(n \log^2 n) 的算法。

很幸运的是,我们可以通过分治来完成这样的一件事情。当然了,由于位运算的值域是 2^n 级别的,我们也要像 FFT 那样将数列长度补齐。

快速沃尔什变换

注意到,位运算是有位独立性的。每一位之间并不会互相影响。那么,我们每次只考虑某一位?

我们令 A_{xy} = (A_{0y}, A_{1y})B_{xy} = (B_{0y}, B_{1y}),行向量分块,其中 y 是任意01序列,那么我们想要
C_{xy} = A_{xy} * B_{xy} = \left(\sum_{a \otimes b = 0} A_{ay} * B_{by}\ , \sum_{a \otimes b = 1} A_{ay} * B_{by} \right)
由于逻辑运算是确定的,我们可以很容易的计算出 \otimes 的真值表,并且后续又变成了规模更小的卷积,就是一个分治的过程啦。

假如构造了一个变换 \mathfrak{T}(A),满足 \mathfrak{T} (C) = \mathfrak{T} (A) \times \mathfrak{T} (B),并且可以很短时间内求得 \mathfrak{T}(A)\mathfrak{T}^{-1}(A),就可以像FFT一样卷积了。

Fast Walsh-Hadamard Transform,这个神奇的变换,我们分别称变换与逆变换为 FWT(A)UFWT(A),那么

对于与运算 \& 来说,有

FWT(A) = \left(\ FWT(A_0) + FWT(A_1)\ ,\ FWT(A_1)\ \right)
UFWT(A) = \left(\ UFWT(A_0) – UFWT(A_1)\ ,\ UFWT(A_1)\ \right)

并且

FWT(A)[i] = \sum_{i \& j = i} A[j]

void FWT(lld X[], int l, int r, int dft = 1)
{
    if (l == r) return;
    int m = (l+r)>>1;
    FWT(X, l, m, dft);
    FWT(X, m+1, r, dft);
    for (int i = 0; i <= m-l; i++)
        X[l+i] += X[m+1+i] * dft;
}

对于或运算 | 来说,有

FWT(A) = \left(\ FWT(A_0)\ ,\ FWT(A_0) + FWT(A_1)\ \right)
UFWT(A) = \left(\ UFWT(A_0)\ ,\ UFWT(A_1) – UFWT(A_0)\ \right)

并且

FWT(A)[i] = \sum_{i | j = i} A[j]

void FWT(lld X[], int l, int r, int dft = 1)
{
    if (l == r) return;
    int m = (l+r)>>1;
    FWT(X, l, m, dft);
    FWT(X, m+1, r, dft);
    for (int i = 0; i <= m-l; i++)
        X[m+1+i] += X[l+i] * dft;
}

异或运算 \oplus
FWT(A) = \left(\ FWT(A_0) + FWT(A_1)\ ,\ FWT(A_0) – FWT(A_1)\ \right)
UFWT(A) = \left(\ UFWT(\frac{A_0 + A_1}2)\ ,\ UFWT(\frac{A_0-A_1}{2})\ \right)

暂时没有找到比较明显的规律

void FWT(lld X[], int l, int r, int dft)
{
    if (l == r) return;
    int m = (l+r)>>1;
    FWT(X, l, m, dft);
    FWT(X, m+1, r, dft);

    for (int i = 0; i <= m-l; i++)
    {
        lld x = X[l+i], y = X[m+1+i];
        X[l+i] = dft == 1 ? x+y : (x+y)/2;
        X[m+1+i] = dft == 1 ? x-y : (x-y)/2;
    }
}

例子

链接:https://ac.nowcoder.com/acm/contest/295/H
来源:牛客网

Niuniu likes playing games. He has n piles of stones. The i-th pile has ai stones. He wants to play with his good friend, UinUin. Niuniu can choose some piles out of the n piles. They will play with the chosen piles of stones. UinUin takes the first move. They take turns removing at least one stone from one chosen pile. The player who removes the last stone from the chosen piles wins the game. Niuniu wants to choose the maximum number of piles so that he can make sure he wins the game. Can you help Niuniu choose the piles? 

给出 n 个数字,记为 a_0, a_1, a_2, …, a_{n-1},且 a_i \le 5\times10^5,求 max|A|, \oplus_{a\in A} a = 0

不妨记 \oplus_{i=0}^{n-1}a_i = sum,那么我们构造一个最小的堆,使得其异或和为 sum 即可。

我们只要记录可以被构造出来的堆值,就可以在第一次这个堆被构造出来时停止。由于 x \oplus x = 0,所以我们直接用已经构造出来的集合和原始给出的集合进行逻辑运算卷积。因为不需要记录方案数,所以直接置1即可。

B_{k}^n = \left[\left(\sum_{i \oplus j = k} A_{i} B_{j}^{n-1}\right) > 0 \right],相当于记录了,有 B 的堆和 A 原来堆,异或后能构造的值的集合。显然这个数字不会超过 2^{19},所以做19次卷积即可。

#include <cstring>
#include <cstdio>
typedef long long lld;
const int MAX = 524287;
lld a[MAX+1], b[MAX+1] = {1};

void FWT(lld X[], int l, int r, int dft)
{
    if (l == r) return;
    int m = (l+r)>>1;
    FWT(X, l, m, dft);
    FWT(X, m+1, r, dft);

    for (int i = 0; i <= m-l; i++)
    {
        lld x = X[l+i], y = X[m+1+i];
        X[l+i] = dft == 1 ? x+y : (x+y)/2;
        X[m+1+i] = dft == 1 ? x-y : (x-y)/2;
    }
}

int main()
{
    int n, tmp, sum = 0; scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &tmp);
        a[tmp]++;
        sum ^= tmp;
    }

    FWT(a, 0, MAX, 1);
    int max_ans = 0;
    while (!b[sum])
    {
        if (max_ans++ == 19) break;
        FWT(b, 0, MAX, 1);
        for (int j = 0; j <= MAX; j++)
            b[j] = a[j] * b[j];
        FWT(b, 0, MAX, -1);
        for (int j = 0; j <= MAX; j++)
            b[j] = !!b[j];
    }

    printf("%d\n", n - max_ans);
    return 0;
}

Polya置换

置换

M 是一个非空的有限集合,M 的一个一对一变换称为一个置换。

M 的元素为 a_1, a_2, \cdots, a_n,则 M 的置换 \sigma 可以简记为

\sigma = \left(
\begin{array}{cccc}
a_1 & a_2 & \cdots & a_n\\
b_1 & b_2 & \cdots & b_n
\end{array}
\right)

其中 b_i = \sigma(a_i)。如果

\sigma = \left(
\begin{array}{cccc}
a_1 & a_2 & \cdots & a_{n-1} & a_n\\
a_2 & a_3 & \cdots & a_n & a_1
\end{array}
\right)

则简记 \sigma = (a_1 a_2 \cdots a_n)

\sigma\tau 是两个不相杂的轮换,则其乘法适合交换律,即 \sigma\tau = \tau\sigma。可以证明,任意置换 \sigma 恰有一法写成不相交轮换的乘积。

可以分解为奇数个对换之积的置换称为奇置换,可以分解为偶数个对换之积的置换称为偶置换。

Burnside 引理

Gn 元集 S = \lbrace 1, 2, \cdots, n \rbrace 上的置换群 G = \lbrace \sigma_1, \sigma_2, \cdots, \sigma_n \rbrace,把每个 \sigma_i 都表示成不相杂的轮换的乘积,令 \lambda_k(\sigma_i) 表示置换 \sigma_ik 阶轮换的个数,则 GS 上诱导出的等价关系将 S 划分为不同等价类的个数为

L = \frac{1}{|G|} \sum_{j=1}^r \lambda_1(\sigma_j)

其中 \lambda_1(\sigma) 为置换 \sigma 中的不动点(即1阶轮换)的个数。

Polya 定理

Hn 个对象上的一个置换群,用 m 种颜色给这 n 个对象涂色,一个对象涂任意种颜色,则在置换群 H 的作用下不等价的方案数为

L = \frac{1}{|H|} \sum_{\tau \in H} m^{\lambda(\tau)}

其中 \lambda(\tau) 表示置换 \tau 表示为不相杂轮换乘积的形式中轮换的个数。

例如,对于置换群H’ = \lbrace (1)(2)(3), (1 2 3), (1 3 2), (1)(2 3), (2)(1 3), (3)(1 2) \rbrace,不等价的方案数为L’ = \frac{1}{6} \left[3^3 + 2 \times 3^1 + 3 \times 3^2 \right]。记颜色为 \lbrace r, g, b \rbrace,则其生成函数为L(r,g,b) = \frac{1}{6} \left[(r+g+b)^3 + 2 \times (r^3+b^3+g^3) + 3 \times (r+g+b)(r^2+b^2+g^2) \right],其中 r^xg^yb^z 前的系数表示将对应颜色染对应个数时的方案数。

组合数学知识计算。

常见模型举例

圆环的旋转与反射

例题:POJ 2409 / POJ 1286

在轴对称的作用下。奇数阶环的对称轴一定通过其中的一个珠子,那么会形成 (1)(2, n)(3, n-1)\cdots 这样的置换,总共 n 个,不相杂轮换 \frac{n+1}{2} 个。偶数阶环的对称轴可能经过珠子,也可能不经过珠子,那么会形成 (1,n)(2,n-1)(3,n-2)\cdots 型置换 \frac{n}{2} 个、(1)(2,n)(3,n-1)\cdots(\frac{n}{2}+1) 型置换 \frac{n}{2} 个。

在中心对称的作用下,考虑珠子旋转 k\in[0,n-1] 个单位时的情况,不相杂轮换有 gcd(k,n) 个。对于同一个 k,又可以由欧拉函数求出相似者,于是枚举 n 所有的因子即可,对于每个因子 d 都有 \varphi(\frac{n}{d}) 个共轭的置换。

while (!factors.empty()) {
    int d = factors.back();
    sum += phi[n/d] * fpow(c, d);
    factors.pop_back();
}

if (n & 1) {
    sum += n * fpow(c, (n+1)>>1);
} else {
    sum += (n>>1) * fpow(c, n>>1);
    sum += (n>>1) * fpow(c, 1+(n>>1));
}

sum /= n*2;

正方形的旋转与反射

例题:HDU 1812

对于 N\times N 的正方形,有1个 n^2 的恒等置换,有1个 \lceil \frac{n^2}{2} \rceil 的 180° 旋转,有2个 \lceil \frac{n^2}{4} \rceil 的 90° 旋转,有2个 \lceil \frac{n}{2} \rceil n 的纵向横向反射,有2个 \frac{n(n+1)}{2} 的斜反射。

BigInteger sum = BigInteger.valueOf(0);
sum = sum.add(colors.pow(n*n));
sum = sum.add(colors.pow((n*n+1)/2));
sum = sum.add(colors.pow((n*n+3)/4).shiftLeft(1));
sum = sum.add(colors.pow((n+1)/2*n).shiftLeft(1));
sum = sum.add(colors.pow(n*(n+1)/2).shiftLeft(1));
System.out.println(sum.shiftRight(3));

正方体的旋转

1x静止、4x2x体对角线、6x对棱中心连线、3x3x对立面中心连线

lld solve2(int i = 0, int s = 6) {
    if (i >= 6) return 1;
    if (cnt[i] % 2) return 0;
    return C[s][cnt[i]/2] * solve2(i+1, s-(cnt[i]/2));
} // 提取 (a2+b2+c2+d2+e2+f2)^6 的某项系数