跳转至

260225 模拟赛

T1

首先观察到递推式

\[ f_m(n)= \begin{cases} 1,&f_m(n-m+1)=n-m+1\\ f_m(n-m+1)+m,&\text{otherwise} \end{cases} \]

于是按照下标模 \(m-1\) 的余数分类，第 \(i\) 类记为 \(A_i\)。注意到第 \(i\) 类形如一些长度为 \(i\times m^x\) 的等差数列按顺序拼接。然后注意到查询本质上就是查询 \(A_i,i\le n\bmod (m-1)\) 的前 \(\lfloor\frac{n}{m-1}\rfloor+1\) 项和以及 \(A_i,i>n\bmod (m-1)\) 的前 \(\lfloor\frac{n}{m-1}\rfloor\) 项。

然后又注意到 \(A_i\) 的前 \(n'\) 项涉及的等差数列的段数在 \(i\in[1,m-1]\) 时最多只有两个不同的值（这个赛时没有注意到）。分讨这两种情况，可以推出快速计算的式子。时间复杂度 \(O(T\log n)\)。

散段的式子差不多就是

\[ \sum_{i=1}^{x}\frac{(n-i\times len)(n-i\times len-1)}{2} \]

然后将它展开可以推出 \(O(1)\) 的式子，整块的式子差不多就是

\[ \sum_{i=0}^{c-1}\sum_{j=1}^{x}\frac{(jm^i)(jm^i-1)}{2} \]

然后展开后可以做到 \(O(c)\) 也就是 \(O(\log n)\)。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
using namespace std;
typedef long long ll;
typedef __int128 lll;
const int MOD = 998244353;
const int half = (MOD + 1) / 2;
const int f4 = 748683265;
const int f6 = (MOD + 1) / 6;
const int f12 = 582309206;

inline void add(int &a, int b) { a += b; (a >= MOD) && (a -= MOD); }

int T; ll m, l, r;

inline int f1(ll n, ll len, ll t) {
    n %= MOD; t %= MOD; len %= MOD;
    return (ll)half * (n * (n - 1) % MOD * t % MOD
                - t * (t + 1) / 2 % MOD * (2 * n - 1) % MOD * len % MOD + MOD
                + t * (t + 1) % MOD * (2 * t + 1) % MOD * f6 % MOD * len % MOD * len % MOD) % MOD;
}
inline int g(ll c, ll x) {
    int res = 0; x %= MOD;
    ll s = 1;
    for(int i = 0; i < c; i++, s = s * (m % MOD) % MOD) {
        add(res, (x * (x + 1) % MOD * (2 * x + 1) % MOD * f12 % MOD * s % MOD * s % MOD - x * (x + 1) % MOD * f4 % MOD * s % MOD + MOD) % MOD);
    }
    return res;
}
inline int f(ll n, ll x) {
    ll k = 1, c = 1, len = 1;
    while(n > len + (lll)k * m) len += (k *= m), ++c;
    ll t = n / len;
    if(x <= t) return (f1(n, len, x) + g(c, x)) % MOD;
    return ((ll)f1(n, len, t) + f1(n, len - k, x) - f1(n, len - k, t) + MOD
                + g(c, t) + g(c - 1, x) - g(c - 1, t) + MOD) % MOD;
}
inline int calc(ll n) {
    ll r = n % (m - 1); n = n / (m - 1) + 1;
    return ((ll)f(n, r) + f(n - 1, m - 1) - f(n - 1, r) + MOD) % MOD;
}

int main() {

#ifndef LOCAL
    freopen("joseph.in", "r", stdin);
    freopen("joseph.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
#endif

    cin >> T;
    while(T--) {
        cin >> m >> l >> r;
        int res = (calc(r) - calc(l - 1) + MOD) % MOD;
        cout << ((ll)res * (m % MOD) % MOD + (r - l + 1)) % MOD << '\n';
    }

    return 0;
}

T2

显然充要条件是每个元素出现的位置都是一段连续的区间。然后乘以 \(\prod cnt_i!\) 转化为对原序列重排。然后发现，如果两个区间有交叉，那么就恰好有正反两种情况。尝试加入第三个交叉的区间，发现仍然只有正反两种情况，继续加也是如此。这里口胡一个证明：考虑归纳，加入一个新的区间的时候显然可以确定它在中介区间的左边还是右边。

然后把所有有交的区间合并成一个，现在只有相互包含的区间了。考虑一个大区间包含一些小区间的情况，方案数显然可以通过对大区间中那些不属于小区间的元素进行插板得到。时间复杂度容易做到 \(O(nm^2)\)。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int M = 64;
const int MOD = 998244353;

int T, n, m, ans;
ll a[N]; int fa[M], sz[M]; ll mask[M];
int tag[M][M];

unordered_map<ll, int> cnt, cnt2;

void clear() {
    for(int i = 0; i < m; i++)
        for(int j = i + 1; j < m; j++)
            tag[i][j] = 0;
    for(int i = 0; i < m; i++) fa[i] = i, sz[i] = 0, mask[i] = (1ll << i);
    ans = 1;
    cnt.clear(); cnt2.clear();
}
inline int find(int x) { if(fa[x] == x) return x; return fa[x] = find(fa[x]); }

int inv[N], fac[N], ifac[N];
inline int A(int a, int b) { return (ll)fac[a] * ifac[a - b] % MOD; }

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    inv[1] = fac[0] = ifac[0] = 1;
    for(int i = 2; i < N; i++) inv[i] = MOD - (ll)inv[MOD % i] * (MOD / i) % MOD;
    for(int i = 1; i < N; i++) fac[i] = (ll)fac[i - 1] * i % MOD;
    for(int i = 1; i < N; i++) ifac[i] = (ll)ifac[i - 1] * inv[i] % MOD;

    cin >> T;
    while(T--) {
        cin >> n >> m;
        clear();
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int i = 1; i <= n; i++) cnt[a[i]]++;
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < m; j++) {
                for(int k = 0; k < m; k++) {
                    int x1 = a[i] >> j & 1, x2 = a[i] >> k & 1;
                    tag[j][k] |= (1 << (x1 << 1 | x2));
                }
            }
        }
        for(int i = 0; i < m; i++) {
            for(int j = i + 1; j < m; j++) {
                if((tag[i][j] & 14) == 14) {
                    mask[find(j)] |= mask[find(i)];
                    fa[find(i)] = find(j);
                }
            }
        }
        for(int i = 0; i < m; i++) {
            if(fa[i] == i && (mask[i] != (mask[i] & -mask[i]))) ans = ans * 2 % MOD;
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < m; j++) {
                if(a[i] & mask[j]) ++sz[j];
            }
        }
        for(int i = 0; i < m; i++) {
            if(fa[i] != i || sz[i] == 0) continue;
            ll sum = -1;
            for(int j = 1; j <= n; j++) {
                if(a[j] & mask[i]) sum &= a[j];
            }
            if(mask[i] == (mask[i] & -mask[i]))
            for(int j = 0; j < m; j++) {
                if(fa[j] == j && (sz[j] < sz[i] || sz[j] == sz[i] && j <= i)) sum &= ~mask[j];
            }
            cnt2[sum]++;
        }
        for(auto [val, c] : cnt) ans = (ll)ans * fac[c] % MOD;
        for(auto [val, c] : cnt2) {
            ans = (ll)ans * A(c + cnt[val], c) % MOD;
        }
        cout << ans << '\n';
    }

    return 0;
}