Kalorona

「Fortuna OJ」6352 – 给(ca)题解

主要思路

首先，叶子结点为\(k\)时，整个完整的二叉树存在\(2k – 1\)个节点。我们设置一个 DP 来进行计数。

考虑设置状态\(dp[i][j]\)为当前树已有\(i\)个节点，且有当前加入的节点到根的路径有\(j\)单位长度。考虑以下转移：

\[ dp[i + 1][j + 1] += dp[i][j] \\ dp[i + 1][j – 1] += dp[i][j] \]

向新的节点加入统计数据：多了一个叶子结点，要么向左走，加深当前的路径；要么补上最后一个向左走的右节点。

然后就可以写代码了。

Continue reading →

Educational DP Contest : M – Candies 题解

主要思路

我这个傻逼还搞个多重集容斥恶心自己。

首先分析题意，不难想出转移方程：

\[ dp[i][j] = dp[i-1][j]+\sum_{k = limit[i]}^{j} dp[i-1][k] \]

然后考虑用\(O(n)\)的时间先预处理出前缀和\(dp[i-1][k-1]\)，然后大的减小的\(O(1)\)查询即可。

代码

// M.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 110, MAX_K = 1e5 + 200, MOD = 1e9 + 7;
ll n, limit[MAX_N], dp[MAX_N][MAX_K], k, mxk, prefix[MAX_K];
int main()
{
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &limit[i]), dp[i][0] = 1;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        prefix[i] = 0;
        for (int j = 1; j <= k + 1; j++)
            prefix[j] = prefix[j - 1] + dp[i - 1][j - 1];
        for (int j = 1; j <= k; j++)
        {
            dp[i][j] = dp[i - 1][j] + prefix[j] - prefix[max(0LL, j - limit[i])];
            dp[i][j] %= MOD;
        }
    }
    printf("%d", dp[n][k]);
    return 0;
}

U63113:入侵 – 又名 「XG 的数学题」

题目背景

众所周知，XG_Zepto 是一位来自 FZOI 的神仙。他觉得眼下的比赛太简单了，就用扫雷的时间出了一道数学题给 kal0rona。kal0rona 太菜了，看不懂题也不会写，之后求救于你了。

题目思路

很好的一道计数 DP，出自神仙组长 XG_Zepto 之手。首先，设\(f[i][j]\)为长度为\(i\)，换弹次数为\(j\)时满足条件的排列数量。之后，考虑枚举第\(i\)个数字出现的位置\(k\)，对于位置\(k\)后面的数字是不会有特殊贡献的（贡献为\((i-k)!\)），而对于前面的数，可以进行枚举前一段进行转移，一共有\({k-1}\choose{i-1}\)种选数字的方案和\(f[i-1][j-1\)种排列，乘起来即可，也就是：

\[ F[i][j] = \sum_{k = 1}^{i}f[k-1][j-1]* {{k-1} \choose {i-1}} *(i-1)! \]

可以化简，并用前缀和优化：

\[ F[i][j] = (i-1)!\sum_{k=1}^{i}\frac{f[k-1][j-1]}{(k-1)!} \]

代码

// U63113.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 5050, mod = 998244353;
ll f[MAX_N], prefix[MAX_N], level[MAX_N], inv[MAX_N], n, m;
ll quick_pow(ll bas, ll tim)
{
    ll ans = 1;
    while (tim)
    {
        if (tim & 1)
            ans = ans * bas % mod;
        bas = bas * bas % mod;
        tim >>= 1;
    }
    return ans;
}
int main()
{
    scanf("%lld%lld", &n, &m);
    level[0] = 1, inv[0] = 1;
    for (int i = 1; i <= n; i++)
        level[i] = level[i - 1] * i % mod;
    inv[n] = quick_pow(level[n], mod - 2);
    for (int i = n; i >= 1; i--)
        inv[i - 1] = inv[i] * i % mod;
    for (int i = 0; i <= n; i++)
        prefix[i] = 1;
    for (int j = 1; j <= m; j++)
    {
        for (int i = j; i <= n; i++)
            f[i] = prefix[i - 1] * level[i - 1] % mod;
        for (int i = j; i <= n; i++)
            prefix[i] = f[i] * inv[i] % mod;
        for (int i = j + 1; i <= n; i++)
            prefix[i] = (prefix[i] + prefix[i - 1]) % mod;
    }
    printf("%lld", f[n]);
    return 0;
}

POJ1037:A decorative fence 题解

主要思路

这道题是计数类 DP 中一道非常好的题。

我先来简述一下“试填法”。很多做过数位 DP 的神仙们都可能比较熟悉这样的技巧，一次次相减尝试并统计答案。这就是试填法，特别是在一些递推形式的数位 DP 中会经常简单这样的方法。

那我们开始来分析一下这道题吧。首先，设\(F[i][j][0/1]\)为木板数为\(i\)时，最后放置的木板排名为\(j\)且处于低位（0）或高位（1）。可以写出递推式：

\[ F[i][j][0] = \sum_{h=j}^{i-1} F[i-1][h][1] \\ F[i][j][1] = \sum_{h = 1}^{j-1} F[i-1][h][0] \]

之后，我们可以试图找出第一块木板的排名，设\(last\)为上一块木板的排名，\(k\)为上一块木板是否为高位（0/1）。通过枚举高度并试填：

  • 当枚举到的方案数小于目前的方案余量，余量减去并继续枚举。
  • 当方案数大于方案余量，记下状态并跳出。

对于之后的\([2,n]\)块木板，道理是一样的。需要注意的是，我们的枚举顺序从\(n\)到\(1\)，保证完整性。

代码

// POJ1037.cpp
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
ll n, m, T, f[25][25][2];
bool vis[25];
void initialize()
{
    f[1][1][0] = f[1][1][1] = 1;
    for (int i = 1; i <= 20; i++)
        for (int j = 1; j <= i; j++)
        {
            for (int k = j; k <= i - 1; k++)
                f[i][j][0] += f[i - 1][k][1];
            for (int k = 1; k <= j - 1; k++)
                f[i][j][1] += f[i - 1][k][0];
        }
}
int main()
{
    scanf("%d", &T);
    initialize();
    while (T--)
    {
        memset(vis, 0, sizeof(vis));
        scanf("%lld%lld", &n, &m);
        // to determine the first condition;
        ll last, k;
        for (int j = 1; j <= n; j++)
        {
            if (f[n][j][1] >= m)
            {
                last = j, k = 1;
                break;
            }
            else
                m -= f[n][j][1];
            if (f[n][j][0] >= m)
            {
                last = j, k = 0;
                break;
            }
            else
                m -= f[n][j][0];
        }
        vis[last] = true;
        printf("%lld", last);
        for (int i = 2; i <= n; i++)
        {
            k ^= 1;
            int j = 0;
            for (int len = 1; len <= n; len++)
            {
                if (vis[len])
                    continue;
                j++;
                if ((k == 1 && len > last) || (k == 0 && len < last))
                    if (f[n - i + 1][j][k] >= m)
                    {
                        last = len;
                        break;
                    }
                    else
                        m -= f[n - i + 1][j][k];
            }
            printf(" %lld", last);
            vis[last] = true;
        }
        puts("");
    }
    return 0;
}

CH3602:Counting Swaps 题解

主要思路

这是道好题，运用了图论建模的方法，可谓是十分精妙了。

对于每一个\(i\)与\(arr[i]\)都连一条有向边，比如说数列\(2\ 1\ 4\ 3\)：

可以通过 DFS 染色的方式找出\(k\)个环，并且将每个环的长度记为\(l_i\)。我们可以得出一个引理：

在图中，对于长度为\(n\)的环，将其变为自环的最小步骤为\(n-1\)。

就是这样的性质，我们可以记\(F[i]\)为当环长为\(i\)时变为自环的方案数，那么我们可以基于分裂的思想，设\(T(x,y)\)为当环长为\(x+y\)时分裂为环长分别为\(x,y\)时的方案数，显然：

\[T(x,y) = \begin{cases} \frac{n}{2}, x = y \\ n, x \neq y \end{cases}\]

所以，我们可以照例推出：

\[ F[i] = \sum_{x+y=i} T(x,y)*F[x]*F[y]*\frac{(n-2)!}{(x-1)!(y-1)!} \]

我来解释一下这个式子的意义：首先，枚举\(x\)和\(y\)的情况，然后乘上这两个本身变成自环的方案数，也就是\(F[x]*F[y]\)，之后根据多重集排列公式和上面那个引理，两者步数分别为\(x-1,y-1\)，所以也不难得出上面那一坨了。

答案为\(\prod_{i = 1}^k {F_{l_i}} * \frac{(n-k)!}{\prod_{i = 1}^{k}(l_i-1)}\)，时间复杂度为\(O(n^2)\)，然而通过人类智慧等方法，发现\(F[n]=n^{n-2}\)，所以通过快速幂降为\(O(n \log n)\)。

代码

// CH3602.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 1e5 + 200, mod = 1e9 + 9;
int T, n, arr[MAX_N], head[MAX_N], current, k, li[MAX_N], vis[MAX_N];
ll level[MAX_N], inv[MAX_N];
struct edge
{
    int to, nxt;
} edges[MAX_N << 1];
void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}
int dfs(int u, int fa)
{
    vis[u] = true;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
        {
            if (vis[edges[i].to])
                return 1;
            return dfs(edges[i].to, u) + 1;
        }
    return 1;
}
ll quick_power(ll bas, ll tim)
{
    ll ans = 1;
    while (tim)
    {
        if (tim & 1)
            ans = ans * bas % mod;
        bas = bas * bas % mod;
        tim >>= 1;
    }
    return ans;
}
ll Fn(int n) { return (n == 1) ? 1 : quick_power(n, n - 2); }
int main()
{
    scanf("%d", &T);
    level[0] = inv[0] = 1;
    for (int i = 1; i < MAX_N; i++)
        level[i] = level[i - 1] * i % mod;
    inv[MAX_N - 1] = quick_power(level[MAX_N - 1], mod - 2);
    for (int i = MAX_N - 1; i >= 2; i--)
        inv[i - 1] = inv[i] * i % mod;
    while (T--)
    {
        memset(head, -1, sizeof(head)), current = 0;
        memset(li, 0, sizeof(li)), k = 0;
        memset(vis, 0, sizeof(vis));
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &arr[i]), addpath(arr[i], i), addpath(i, arr[i]);
        for (int i = 1; i <= n; i++)
            if (!vis[i])
                li[++k] = dfs(i, 0);
        ll ans = 1;
        for (int i = 1; i <= k; i++)
            ans = ans * Fn(li[i]) % mod;
        ans = (ans * level[n - k] % mod);
        for (int i = 1; i <= k; i++)
            ans = ans * inv[li[i] - 1] % mod;
        printf("%lld\n", ans);
        continue;
    }
    return 0;
}

POJ1737:Connected Graph 题解

主要思路

这道题的计数方程和思想非常有趣，下面开始进行分析。

我们设\(F[i]\)为点数为\(i\)时的无向连通图种类。我们可以尝试容斥：\(n\)个点的无向图种类有\(2^{\frac{n(n-1)}{2}}\)，我们可以枚举\(k\)，删去大小为\(k\)的连通块来保持连通性。因为本题要求点标号，所以这些连通块的种类为：

\[\sum_{k=1}^{i-1}(F[k]*C_{i-1}^{j-1}*2^{\frac{(i-k)(i-k-1)}{2}})\]

其中，\(F[k]\)为连通块大小为\(k\)时的连通块个数，然后\(C_{i-1}^{j-1}\)是标号对答案的贡献，之后另一个残余块的种类为\(2^{\frac{(i-k)(i-k-1)}{2}}\)，乘起来即可。

这道题的加强版需要使用 NTT 和卷积的知识：BZOJ 3456:城市规划题解

代码

// POJ1737.cpp
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
const int MAX_N = 60;
ll f[MAX_N], C[MAX_N][MAX_N], tmp;
int main()
{
    C[1][0] = C[1][1] = 1;
    for (int i = 2; i < MAX_N; i++)
    {
        C[i][0] = 1;
        for (int j = 1; j < MAX_N; j++)
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    }
    f[1] = 1;
    for (int i = 2; i < MAX_N; i++)
    {
        f[i] = (1 << ((i * (i - 1)) >> 1));
        for (int j = 1; j < i; j++)
            f[i] -= f[j] * C[i - 1][j - 1] * (1 << (((i - j) * (i - j - 1)) >> 1));
    }
    while (~scanf("%d", &tmp) && tmp != 0)
        printf("%lld\n", f[tmp]);
    return 0;
}