省流:罚时上天,但是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 可以由左 bc,左 ac 得到。
  2. b 可以由左 ad,左 bb 得到。
  3. c 可以由左 da,左 cc 得到。
  4. d 可以由左 db,左 cd 得到。

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

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

文章目录