自动搬运

查看原文

来自洛谷，原作者为

	LionBlaze @wsx 我这么弱你还说我批话/ll || 有实力或没那么有实力的欢迎加入 WROI /team/96917 || 前置声明：不当除了 WROI 之外任何公开赛的背锅人。接受私信协商。

搬运于2025-08-24 22:15:51，当前版本为作者最后更新于2025-06-23 18:32:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题外话：众所周知，不能连续发送相同电平是非常真实的，因为这样难以知道你发送了几个这样的电平。比如 _—_—_——_（_ 为 $0$，— 为 $1$）很容易看清，而 —————— 不是很容易。现在的解法大概是，异或上一个相位差距为半个脉冲时间的时钟信号，可能比较抽象但是确实能够解决问题。比如 ——————，为了便于表示我们拉长为两倍，也就是 ————————————，而时钟信号是 _——__——__——_（同样扩倍，但是已经加上相位），异或结果就是 —__——__——__—，这样脉冲最多 $1$ 个频率的时间就会变化一次了（注意，这里两个字符表示一个脉冲的时间）。

先不考虑如何进行大数运算（这也是一个不算很简单的地方，难度大概是黄），考虑算法主体部分。

由于 $\dfrac{n}{m}$ 是整数，我们只考虑单个数据包。如果一个数据包能够表示 $x$ 种不同的脉冲波，则包含 $\log_2 x$ 位信息，而 $y$ 个这样的数据包能够包含 $\log_2(x^y)$ 位信息，显然这东西等于 $y\log_2x$。也就是答案为 $\dfrac{n}{m}\log_2x$，其中 $x$ 是单个数据包（也就是 $m$ 个连续脉冲）能够包含的不同包数量。

这也就说明，实际上 $n$ 的范围是 $100$（也就是 $m$ 的范围），因为我们只需要考虑 $m$。

那么自然地，设 $f_{i,j,p}$ 为考虑前 $i$ 个脉冲，最后 $j$ 个脉冲都是 $p$，但是倒数第 $j+1$ 个不是，有多少种可能性。

这样并不好，注意到 $p$ 为任何数字的时候答案都一样（$i,j$ 相同），这一点是显然的。所以我们只需要固定 $p$，答案乘上 $k$ 即可。

分类讨论 $j=1$ 和 $j\ge 2$ 的情况。前者只可能是把一个连续段（长度可能为 $1$）打断而来，状态转移方程详见代码，读者也可以自己推一推。后者只可能是把一个连续段再接上一个同样的，不能包含更多信息（新增的数字唯一）。

边界条件显然是 $f_{1,1}=1$。

那么考虑如何进行大数运算。由于我们只需要直到结果的 $\log$，那么我们可以只存储 $\log$。这样算乘法非常容易，而加法呢，如果差距过于悬殊可以直接将大的作为结果（如 $1+2^{-100}$ 直接当做 $1$），否则就正常地进行计算（展开然后化简，然后求值）。

代码。

#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

class logic
{
public:
    long double lglg;
    logic() : lglg(-1e18) {}
    logic(const logic &r) : lglg(r.lglg) {}
    logic(const long double &r) : lglg(log2(r)) {}
    logic(int r) : lglg(log2(r)) {}
    operator long double() const { return pow(2, lglg); }
    friend logic operator+(logic x, logic y)
    {
        if(x.lglg < y.lglg) swap(x, y);
        // 如果差距太大，超过 2^100
        if(x.lglg - y.lglg >= 100) return x;
        // 否则，x+y=2^a+2^b=2^b(2^(a-b)+1)
        return {y.lglg + log2(pow(2, x.lglg - y.lglg) + 1)};
    }
    friend logic operator*(logic x, logic y) { return {x.lglg + y.lglg}; }
    const logic &operator+=(logic y)
    {
        if(lglg < y.lglg) swap(lglg, y.lglg);
        // 如果差距太大，超过 2^100
        if(lglg - y.lglg >= 100) return *this;
        // 否则，x+y=2^a+2^b=2^b(2^(a-b)+1)
        lglg = y.lglg + log2(pow(2, lglg - y.lglg) + 1);
        return *this;
    }
    const logic &operator*=(logic y) { lglg += y.lglg; return *this; }
};

logic f[105][105];

logic solve(int k, int m, int l)
{
    f[1][1] = 1;
    for(int i=2;i<=m;i++)
    {
        // 处理 j=1
        for(int j=1;j<i&&j<l;j++)
        {
            f[i][1] += f[i-1][j];
        }
        f[i][1] *= k - 1; // 其实应该是上面 f[i][1] += f[i-1][j] * (k - 1)，显然这样写对正确性也没有影响。
        for(int j=2;j<=i&&j<l;j++)
        {
            f[i][j] = f[i-1][j-1];
        }
    }
    logic sum = 0;
    for(int i=1;i<l;i++)
    {
        sum += f[m][i];
    }
    return sum *= k;
}

int main()
{
    int k, n, m, l;
    scanf("%d%d%d%d", &k, &n, &m, &l);
    // printf("result of solve: 2^%.10Lf\n", solve(k, m, l).lglg);
    printf("%d\n", (int)(n / m * solve(k, m, l).lglg));
    return 0;
}