省流：罚时上天，但是3题

A

签到题，注意到 \bigoplus 是二进制意义下不进位加法，并且有 a\bigoplus b \leq a + b，所以直接输出所有数的和就行了。

C

考虑打表观察，我们发现有 a_k = n \sum\limits_{i = 1}^k i^{n-1}，注意到数据范围 n\times m \leq 10^{12} 很不对劲，考虑数据分治。

• 对于 n 较小的情况，我们直接拉格朗日插值，这样是 \mathcal{O}(n\log n)

• 对于 m 较小的情况，我们暴力时间复杂度是 \mathcal{O}(m\log n) 的

bound 可以设在 10^6 左右，跑的飞快。

ll ffpow(ll a,ll b) {
    ll ans = 1;
    for (;b;b >>= 1) {
        if (b & 1) ans = mul(ans,a);
        a = mul(a,a);
    }
    return ans;
}

const int N = 5e6 + 10;

ll n,m,jc[N],inv[N],pr[N],pl[N];

namespace solver1 {
    ll a[N];
    void solve() {
        ll x = 1,k = n - 1,y = 0,ans = 0;
        jc[0] = inv[0] = pl[0] = pr[k + 3] = 1;
        for (int i = 1;i <= k + 2;++i) {
            jc[i] = jc[i-1] * i % mod;   
            pl[i] = pl[i-1] * (m - i) % mod;
        }
        for (int i = k + 2;i >= 1;--i) {
            pr[i] = pr[i+1] * (m - i) % mod;
        }
        for(int i = 1; i <= k + 2; i ++) {
            y = add(y,ffpow(i, k));
            ll a = pl[i - 1] * 1ll * pr[i + 1] % mod;
            ll b = jc[i - 1] * ((k - i) & 1 ? -1ll : 1ll) * jc[k + 2 - i] % mod;
            b = add(b,mod);
            ans = add(ans,y * a % mod * ffpow(b, mod - 2) % mod) % mod;
        }
        printf("%lld\n",mul(n,add(ans,mod)));
    }
}

namespace solver2 {
    void solve() {
        ll ans = 0;
        for (int i = 1;i <= m;++i) ans = add(ans,ffpow(i,n-1));
        printf("%lld\n",mul(n,ans));
    }
}

signed main() {
    read(n,m);
    if (n <= 1000000)solver1::solve();
    else solver2::solve();
    return 0;
}

D

考虑这个条件的限制，我们很自然想到把 >k 的数设为 1,\leq k 的数设为 0。那么这样合法的一个序列就是一个 01 交替的序列。

考虑区间-子区间问题是一个 2-side 的问题，我们考虑用扫描线算法来解决。

具体来说，我们考虑当 k 变大的时候，我们只需要把 w_i = k 的那些 i 设为 1，离线之后就做到了 \mathcal{O}(n\log n)。接下来我们考虑查询，这个序列实际上有 4 种形态（根据开头/结尾为10/01），以下有：

a = 01 \dots 10\\ b = 01\dots 01\\ c=10\dots 10\\ d = 10\dots 01

我们讨论这四种的合并：

1. a 可以由左 b 右 c，左 a 右 c 得到。
2. b 可以由左 a 右 d，左 b 右 b 得到。
3. c 可以由左 d 右 a，左 c 右 c 得到。
4. d 可以由左 d 右 b，左 c 右 d 得到。

于是直接暴力转移，题解写的好像是用矩阵维护转移？我猜大概是本质相同的东西。

总时间复杂度 \mathcal{O}((n+m)\log n)