9.14

“好题分享”，非常恐怖

第一个是ODT，第二个是珠宝商 ， 珠宝商至今没过。

ODT的题维护区间修改和区间出现次数前k大值查询，比较好维护

9.15

题比较简单。

T1 签到题，记得开龙龙

T2 这个稍微得想一想，我直接糊错解还没发现。
实际上只需要对每个点维护他能到达的最小值然后遍历图统计答案即可
实现的话可以把点按照点权排序，每次取出没有扩展的最小点看看他能走到哪些点，把这些点当中之前没有更新过的能到达的最小值置为当前点权。

T3 “两把刷子” 做法是状压枚举子集，每次看当前枚举的子集当中能否通过交换达成目标，若能把当前子集f值记为1，否则记为负无穷

T4 考了类斐波那契数列的两个式子 ：

有了这个之后就可以比较方便的用线段树维护区间操作了。

9.16

A

有一份加密过的便条，加密过程是这样的：

1、由一个正整数 $N$ ，构造一个长度为 $K$ 的数列 $A$ ，为从 $N$ 开始的

连续 $K$ 个数按顺序拼接生成，即 $A=\{N,N+1,N+2,…,N+K-1\}$

2、把数列 $A$ 中的每个数都只保留一个数字，得到数列 $B$。

现在给出 $K$ 和数列 $B$ ，请求出最小的合法的 $N$ 。

$K \le 10^5 ,0 \le B_i \le 9$

显然我们对于 $N$ 有一个不严格的上界 : $102345678900000$ ,所以不存在不合法情况。

做法是每次枚举末位，选择合适的末位加入当前答案，递归处理。

由于每次都会多一位数，所以问题规模缩小到十分之一。

然后复杂度就是 $O(n \lg 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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
typedef long long ll;
int n;
 
ll solve(vector<int> ,int );
 
void main()
{
    scanf("%d",&n);
    vector<int>b;
    for(int i = 0;i < n;i++)
    {
        int x,y;
        scanf("%d",&x);
        y = 1 << x;
        if(!x) y |= (1 << 10);
        b.emplace_back(y);
    }
    printf("%lld\n",solve(b,0));
    return ;
}
 
ll solve(vector<int>b,int dep)
{
    if(dep > 15) return INT_FAST32_MAX / 10;
    bool zero = 1;
    for(auto x : b) zero &= (!x);
    int n = b.size();
    if(n == 1)
    {
        ll res = 0;
        zero = b[0] & 1;
        for(int i = 1;i <= 9;i++)
        {
            if((b[0] >> i) & 1)
            {
                res = res * 10 + i;
                if(zero) res *= 10,zero = 0;
            }
        }
        if(zero) return 10;
        if((b[0] >> 10) & !res) return 1;
        return res;
    }
    ll ans = INT_FAST64_MAX / 10;
    for(int y = 0;y <= 9;y ++ )
    {
        int now = 0;
        vector<int>c;
        for(int i = 0,x = y;i < n;i ++ ,x ++ )
        {
            int tmp = (b[i] & (2047 ^ (1 << x)));
            if(x && (b[i] >> 10) && !(b[i] & 1)) tmp ^= (1 << 10);
            now |= tmp;
            if(x == 9 || i == n-1)
            {
                c.emplace_back(now);
                now = 0,x = -1;
            }
        }
        ans = min(ans,solve(c,dep+1) * 10 + y);
    }
    return ans;
}
 
}
 
signed main()
{
    Pozhu :: main();
    return 0;
}

B

给你三个数 $x,y,z$ ，考虑 $n$ 个数组，每个数组有 $x$ 个 $a_i$ ，$y$ 个 $b_i$ , $z$ 个 $c_i$ ，$a_i,b_i,c_i\in[0,2^k)$ 。

求 $\forall t\in[0,2^k)$ ，从每个数组各取出一个数，这些数 $\text{xor}$ 和为 $t$ 的方案数，模 $998244353$。

$n \le 10^5, k \le 17$

CF1119H

要求把 $n$ 个桶进行 $\text{xor}$ 卷积的结果。。

直接做时间爆炸，考虑优化

发现式子中系数的取值只有八种情况，向这个方向考虑

发现对每个桶先 $\text{xor} a_i$ 可以保证第一个系数为 $0$ ，然后对着四个情况列四个方程解出来就行 ，理论上。

FWT不太会。

放代码 : 

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
89
90
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
const int mod = 998244353;
const int i2 = 499122177;
typedef long long ll;
#define N 1000010
 
int n,m,cnt;
int a,b,c,ans;
ll x,y,z;
ll k[N],f1[N],f2[N],f3[N];
 
ll ksm(ll ,ll );
void FWT(ll[] );
void IFWT(ll[] );
 
void main()
{
    ios :: sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n >> m;
    cnt = 1 << m;
    cin >> x >> y >> z;
    for(int i = 1;i <= n;i++)
    {
        cin >> a >> b >> c;
        b ^= a;
        c ^= a;
        ans ^= a;
        f1[b]++;
        f2[c]++;
        f3[b ^ c]++;
    }
    FWT(f1),FWT(f2),FWT(f3);
    ll s1 = (x + y + z) % mod;
    ll s2 = (x + y - z) % mod;
    ll s3 = (x - y + z) % mod;
    ll s4 = (x - y - z) % mod;
    for(int i = 0;i < cnt;i++)
    {
        ll s = ((n + f1[i] + f2[i] + f3[i]) / 4) % mod;
        k[i] = ksm(s1,s) * ksm(s2,(n + f1[i]) / 2 - s) % mod * ksm(s3,(n + f2[i]) / 2 - s) % mod * ksm(s4,(n + f3[i]) / 2 - s) % mod;
    }
    IFWT(k);
    for(int i = 0;i < cnt;i ++)
    cout << (k[i ^ ans] % mod + mod) % mod << ' ';
    return;
}
 
void FWT(ll k[])
{
    for(int i = 1;i < cnt;i <<= 1 )
    for(int j = 0;j < cnt;j += (i << 1) )
    for(int z = 0;z < i;z ++)
    {
        ll x = k[j + z];
        ll y = k[i + j + z];
        k[j + z] = x + y;
        k[i + j + z] = x - y;
    }
}
 
void IFWT(ll k[])
{
    for(int i = 1;i < cnt;i <<= 1 )
    for(int j = 0;j < cnt;j += (i << 1) )
    for(int z = 0;z < i;z++)
    {
        ll x = k[j + z] * i2 % mod;
        ll y = k[i + j + z] * i2 % mod;
        k[j + z] = (x + y) % mod;
        k[i + j + z] = (x - y + mod ) % mod;
    }
}
 
ll ksm(ll a,ll b)
{
    ll ans = 1;
    for(;b;b>>=1,a = a * a % mod) if(b & 1) ans = ans * a % mod;
    return ans;
}
 
}
 
signed main()
{
    Pozhu :: main();
    return 0;
}

C

给你一个序列 $A(a_1,a_2,\cdots,a_n)$ ，令将所有 $a_i\oplus a_j(i < j)$ 从大到小 排序后得到的序列为 $b_1,b_2,\cdots, b_{n(n-1)/2}$ ，请求出 $\sum_{i=1}^kb_i$ 。

考虑建出trie树。

在trie树上二分可以找到第 $k$ 大。

然后考虑统计答案： 求出所有异或值小于等于 $k$ 的和，考虑在trie树上这些点在什么位置，发现就是对于kth所有二进制位为0的地方去统计他这一位为 $1$ 的数的和。

可以预处理 cnt[x][k] 表示以 $x$ 为根的子树中有多少个数有 $k$ 这一位，然后就好做了。

求和时拆位，逐位累加答案。

可以做到 $O(n \log ^2 n)$

9.17

错题重做

A 是前缀和优化的爆搜，总之没啥问题

B 可以转化成二位数点建主席树，主席树敲不利索所以用线段树+vector被卡常了

C 很巧妙，对于取模乘法取 $\max$ 可以取对数转化为加法，然后普通线段树，不知道为啥写挂了

D 交互题，算是DP，每次操作考虑其贡献然后进行一个转移，zerc写过题解甚至。

9.19

YLCH的模拟赛

A 似乎有锅但不确定，总之没改题

B JOIOI塔，能想到二分答案的话就非常简单了。因为check的**错误挂到50

C 见题面差点以为是 FWT 。结果是玄妙的拆位DP——把每个数拆成前八位和后八位，分开枚举转移。把复杂度指数上的2扔进常数里了属于是，狂暴%YLCH

D 属于是黑题，可以想到tried树和2-SAT，然后考虑如何给2-SAT建边，发现trie树上边具有单向性，然后考虑一个前后缀优化建图，然后就切掉了

9.20

A

显然是打表题。

原题数列是OEIS A202061 ，求这个数列的前50项（原题题面太冗长了）

然后写个爆搜，发现这辈子都打不完这个表。

考虑优化，写个高维DP。

有两维的状态是用来记录下一个数取值区间的 $l,r$ ，然后发现只和相对大小有关，所以扔掉 $l$ ，进行一个区间平移，剪掉一堆枝。

然后加一些其他的小优化就可以跑的飞快了

贴一个打表程序 ： 

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
89
90
91
#include <cstdio>
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int mod = 258280327;
inline int add(int &x, int y)
{
    return ((x += y) >= mod) ? (x -= mod) : x;
}
inline int dec(int &x, int y)
{
    return ((x -= y) < 0) ? (x += mod) : x;
}
int n;
unordered_map<ll, int> f[2][55][2];
int get_last(ll s, bool tag)
{
    int cnt = 0;
    for(int i = 0;i <= n;i++)
    if ((s >> i) & 1)
    {
        ++cnt;
        if (cnt == 1 && tag == 0)
            return i;
        else if (cnt == 2 && tag == 1)
            return i;
    }
    return -1;
}
int work()
{
    f[1][1][0][1] = 1;
    for(int i = 1;i < n;i++)
    {
        bool cur = i & 1;
        for(int j = 0;j <= i;j++)
        for(int z = 0;z <= 1;z++)
        f[cur ^ 1][j][z].clear();
        for(int j = 0;j <= i;j++)
        {
            for(int z = 0;z <= 1;z++)
            {
                for (auto [key,val] : f[cur][j][z])
                {
                    if (val == 0)
                        continue;
                    int x = get_last(key, z);
                    int mn = get_last(key, 0);
                    for(int k = 0;k <= j;k++)   // 之后一个数
                    {
                        int nw_j = j;
                        if (k > x)
                            ++nw_j;
                        int xj = 0;
                        if (k > mn)
                            for(int o = k-1;o>=0;o--)
                            if ((key >> o) & 1)
                            {
                                xj = o;
                                break;
                            }
                        ll nw_s = key | (1ll << k);
                        add(f[cur ^ 1][nw_j - xj][(k <= mn) ? 0 : 1][nw_s >> xj], val);
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int j = 0;j <= n;j++)
    for(int z = 0;z <= 1;z++)
    for (auto s : f[n & 1][j][z]) add(ans, s.second);
    printf("%d\n", ans);
    return 0;
}

int main()
{
    for(int i = 1;i<=50;i++)
    {
        n = i;
        printf("%d ",i);
        work();
        for(int i = 0;i < 2;i++)
        for(int j = 0;j < 55;j++)
        for(int k = 0;k < 2;k++)
        f[i][j][k].clear();
    }
    return 0;
}

然后贴一个打出来的表 ： 

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
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
int n;
void main()
{
    scanf("%d",&n);
    if(n == 1) puts("1");
    else if(n == 2) puts("2");
    else if(n == 3) puts("5");
    else if(n == 4) puts("14");
    else if(n == 5) puts("42");
    else if(n == 6) puts("133");
    else if(n == 7) puts("442");
    else if(n == 8) puts("1535");
    else if(n == 9) puts("5546");
    else if(n == 10) puts("20754");
    else if(n == 11) puts("80113");
    else if(n == 12) puts("317875");
    else if(n == 13) puts("1292648");
    else if(n == 14) puts("5374073");
    else if(n == 15) puts("22794182");
    else if(n == 16) puts("98462847");
    else if(n == 17) puts("174218332");
    else if(n == 18) puts("121259321");
    else if(n == 19) puts("205564312");
    else if(n == 20) puts("242673871");
    else if(n == 21) puts("24048716");
    else if(n == 22) puts("201445404");
    else if(n == 23) puts("256924638");
    else if(n == 24) puts("37968000");
    else if(n == 25) puts("203987697");
    else if(n == 26) puts("189324192");
    else if(n == 27) puts("73730680");
    else if(n == 28) puts("169893620");
    else if(n == 29) puts("39375207");
    else if(n == 30) puts("244353896");
    else if(n == 31) puts("112514764");
    else if(n == 32) puts("12886945");
    else if(n == 33) puts("55643440");
    else if(n == 34) puts("117418646");
    else if(n == 35) puts("185100581");
    else if(n == 36) puts("131021502");
    else if(n == 37) puts("233036844");
    else if(n == 38) puts("220164805");
    else if(n == 39) puts("175300576");
    else if(n == 40) puts("133424141");
    else if(n == 41) puts("199426077");
    else if(n == 42) puts("52884814");
    else if(n == 43) puts("256891447");
    else if(n == 44) puts("137178358");
    else if(n == 45) puts("109043926");
    else if(n == 46) puts("232984055");
    else if(n == 47) puts("170261978");
    else if(n == 48) puts("43283200");
    else if(n == 49) puts("167818822");
    else if(n == 50) puts("216351011");
    return;
}
 
}
 
signed main()
{
    Pozhu :: main();
    return 0;
}

B

“短码阴间题”

做法极度先进 —— 把求和转化成求期望，再乘方案数以便于分析。

方案数是极好求的，考了求期望——考虑每种状态对期望的贡献。

期望学好了的话到这里大概是不难，虽然我不擅期望。

式子挺长，代码挺短，所以放代码 ： 

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
#include <bits/stdc++.h>
using namespace std;
const int p = 998244353;
 
int n, m, q, ans;
 
int Pow(int a, int b) {
    int res = 1;
    for ( ; b; b >>= 1, a = 1ll * a * a % p)
        if (b & 1) res = 1ll * res * a % p;
    return res;    
}
 
int Sum(int k) {
    if (k == 1) return q;
    return 1ll * (Pow(k, q) + p - 1) % p * Pow(k - 1, p - 2) % p;
}
 
int main() {
    scanf("%d %d %d", &n, &m, &q);
    int r = Pow(2 * m + 1, p - 2);
    for (int i = 1; i <= n; ++ i) {
        int z = 1ll * i * (n - i + 1) % p * Pow(n, p - 2) % p * Pow(n + 1, p - 2) % p;
        int y = p + 1 - z;
        int s = Sum((2ll * m * y % p + 1) % p * r % p);
        ans = (ans + 1ll * z * (m - 1) % p * r % p * (q + p - s) % p) % p;
    }
    ans = 1ll * ans * Pow(1ll * n * (n + 1) / 2 % p * (2 * m + 1) % p, q) % p;
    printf("%d\n", ans);
    return 0;
}

C

数轴上有 $n$ 个点 $(p_1,p_2,p_3,\cdots, p_n)$ ，这些点对应的数都是非负偶数。
在每一时刻，这 $n$ 个点可以向左移动一单位，向右移动一单位或原地不动。
你需要求出 最小的所需时间 $K$，使得 存在一种策略 满足对于 每对点 $(p_i,p_{i+1})$ ，至少有一个时刻 它们重合。

可以证明 $K$ 必定是整数。

容易发现移动肯定比不动好。

考虑怎么移动 ：

对于每个点，它都必须和上一个点以及下一个点碰面，所以一定是进行先左后右或者先右后左的移动。

可以使用类似贪心微扰法的方式证明不会有连续两个点不和其他点相向行走。

于是设 f[i] 为强制 $i$ 和 $i-1$ 两个点相向行走，进行一个DP的做。

具体的状态转移看代码可能会更清晰。

代码 ： 

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
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define N 200010
 
int n;
int a[N];
int f[N];
 
void main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
    a[n+1] = a[n];n++;
    f[2] = (a[2] - a[1]) >> 1;
    f[3] = (a[3] - a[1]) >> 1;
    for(int i = 4;i <= n;i++)
        f[i] = min(max(f[i-2],(a[i] - a[i-3]) >> 1) , max(f[i-3] , (a[i] - a[i-4]) >> 1));
    printf("%d",f[n]);
    return;
}
 
}
 
signed main()
{
    Pozhu :: main();
    return 0;
}

9.22

A

导出子图

或许算是状压DP

发现连边长度最多12

于是维护一个16进制的13位数组

每个数表示对应位置的连通块

最后一个数对应当前位置

显然这个数组可以压成一个龙龙类型的数

于是开一个map记录一下方案数，讨论几个情况就能实现转移了，挺简单的。

代码用了结构化绑定来遍历map，可读性大概有点保证

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
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define N 60
const int mod = 998244353;
typedef long long ll;
const ll inf = 1ll << 4 * 12;
 
int n,m;
ll ans;
int cod[15];
int mp[N][N];
map<ll,ll> f[2];
 
ll code();
void arcode(ll );
 
void main()
{
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i = 1;i <= m;i++)
    {
        scanf("%d%d",&x,&y);
        mp[x][y] = 1;
        mp[y][x] = 1;
    }
    f[0][0] = 1;
    int w = 1;
    for(int i = 1;i <= n;i++,w ^= 1)
    {
        f[w].clear();
        for(auto [sta,res] : f[w^1])
        {
            if(sta == inf)
            {
                ans = (ans + res) % mod;
                continue;// "?"
            }
            arcode(sta);
            int j;
            for(j = 2;j <= 13;j++)
                if(cod[j] == cod[1]) break;
            if(cod[1] && j == 14) continue;
            for(int j = 1;j < 13;j++)
                cod[j] = cod[j + 1];cod[13] = 0;
            (f[w][code()] += res) %= mod;
            for(int j = 1;j <= 13;j++)
            if(mp[i][i-j] && cod[13-j])
            {
                int now = cod[13 - j];
                for(int k = 1;k < 13;k++)
                if(cod[k] == now) cod[k] = 14;
            }
            cod[13] = 14;
            (f[w][code()] += res) %= mod;
        }
    }
    w ^= 1;
    for(auto [sta,res] : f[w])
    {
        if(!sta) continue;
        arcode(sta);
        for(int i = 1;i <= 13;i++)
        if(cod[i] > 1) goto nxt;
        ans = (ans + res) % mod;
        nxt:;
    }
    printf("%lld",ans);
    return;
}
 
void arcode(ll x)
{
    for(int i = 13;i >= 1;i--)
    cod[i] = x & 15,x >>= 4;
}
 
ll code()
{
    ll ans = 0,cnt = 0,tmp[15] = {};
    for(int i = 1;i <= 14;i++) tmp[i] = -1;
    for(int i = 1;i <= 13;i++)
    {
        if(tmp[cod[i]] == -1) tmp[cod[i]] = ++cnt;
        ans = (ans << 4) | tmp[cod[i]];
    }
    return ans;
}
 
}
 
signed main()
{
    Pozhu :: main();
    return 0;
}

B

毒瘤数据范围分治题。

zerc赛时推出了 $k > 40$ 的做法，快去%他。

我大概是写不明白，写的很好的是 这篇 。

C

你一个长度 $A+B$ 的整数序列 $(x_1, x_2,…, x_{A+B})$ ，其中包含 $A$ 个 $1$ 和 $B$ 个 $2$。

Snuke有一个集合 $s$ ，最初是空的。它要进行 $A+B$ 次操作。第 $i$ 个操作如下所示。

如果 $x_i =1$ : 选择一个整数 $v(1≤v≤A)$ ，并将其加到 $s$ 中。在这里，$v$ 必须不是之前的操作中选择过的整数。

如果 $x_i =2$ : 从 $s$ 中删除值最大的元素。输入确保在这个操作之前 $s$ 不是空的。

输出 $s$ 的最终状态有多少种可能，答案对 $998244353$ 取模。

显然在第 $i$ 次插入时插入 $i$ 可以使最终获得的集合最大。

然后容易证明所有比这个小的方案都是可以得到的。

所以写一个DP来转移就好，比较简单就不再解释了

代码 ： 

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
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define N 60
const int mod = 998244353;
typedef long long ll;
const ll inf = 1ll << 4 * 12;
 
int n,m;
ll ans;
int cod[15];
int mp[N][N];
map<ll,ll> f[2];
 
ll code();
void arcode(ll );
 
void main()
{
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i = 1;i <= m;i++)
    {
        scanf("%d%d",&x,&y);
        mp[x][y] = 1;
        mp[y][x] = 1;
    }
    f[0][0] = 1;
    int w = 1;
    for(int i = 1;i <= n;i++,w ^= 1)
    {
        f[w].clear();
        for(auto [sta,res] : f[w^1])
        {
            if(sta == inf)
            {
                ans = (ans + res) % mod;
                continue;// "?"
            }
            arcode(sta);
            int j;
            for(j = 2;j <= 13;j++)
                if(cod[j] == cod[1]) break;
            if(cod[1] && j == 14) continue;
            for(int j = 1;j < 13;j++)
                cod[j] = cod[j + 1];cod[13] = 0;
            (f[w][code()] += res) %= mod;
            for(int j = 1;j <= 13;j++)
            if(mp[i][i-j] && cod[13-j])
            {
                int now = cod[13 - j];
                for(int k = 1;k < 13;k++)
                if(cod[k] == now) cod[k] = 14;
            }
            cod[13] = 14;
            (f[w][code()] += res) %= mod;
        }
    }
    w ^= 1;
    for(auto [sta,res] : f[w])
    {
        if(!sta) continue;
        arcode(sta);
        for(int i = 1;i <= 13;i++)
        if(cod[i] > 1) goto nxt;
        ans = (ans + res) % mod;
        nxt:;
    }
    printf("%lld",ans);
    return;
}
 
void arcode(ll x)
{
    for(int i = 13;i >= 1;i--)
    cod[i] = x & 15,x >>= 4;
}
 
ll code()
{
    ll ans = 0,cnt = 0,tmp[15] = {};
    for(int i = 1;i <= 14;i++) tmp[i] = -1;
    for(int i = 1;i <= 13;i++)
    {
        if(tmp[cod[i]] == -1) tmp[cod[i]] = ++cnt;
        ans = (ans << 4) | tmp[cod[i]];
    }
    return ans;
}
 
}
 
signed main()
{
    Pozhu :: main();
    return 0;
}

9.23

挂分的好日子

A

归并，一个看起来很暴力的平衡树做法实际上是正解 ：

考虑每次归并操作的实质 ： 把另一个序列中比当前序列第一个数小的所有数插入结果，然后重复，直到两个序列都为空。

所以用平衡树维护，这样每次查找，分裂和合并都能做到 $\log$ ，然后总共就是 $n \log n$ ，实现的话选择 FHQTreap 可以方便地维护对应的分裂和合并操作。

B

你有一个序列 $\{1,2,3,\cdots,n\}$，你可以对它进行以下操作 $m$ 次：

删除任意一个数，将它加到这个序列的开头或末尾。
最后你需要得到序列 $\{a_i\}$ ，这里 $a_i$ 是个 $1\sim n$ 的排列。求合法的方案数模 $998244353$ 。

两种操作方案相同当且仅当每次操作都选择了相同的元素，移动到了相同的方向。

$2 \le n,m \le 3000$

发现对于每一个数只有对他的最后一次操作是有效操作，其他操作都是在凑步数。

于是是一个组合寄数。

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
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define N 3010
typedef long long ll;
const int mod = 998244353;
 
int n,m;
int a[N],len[N];
ll fac[N],invfac[N];
ll f[N][N];
 
ll C(ll ,ll );
ll ksm(ll ,ll );
 
void main()
{
    cin >> n >> m;
    fac[0] = 1;
    for(int i = 1;i <= n;i++) fac[i] = fac[i-1] * i % mod;
    invfac[n] = ksm(fac[n],mod-2);
    for(int i = n;i;i--) invfac[i-1] = invfac[i] * i % mod;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    f[m][0] = 1;
    for(int i = m-1;~i;i--)
    for(int j = 0;j <= n;j++)
    {
        f[i][j] = 2 * f[i + 1][j] * j % mod;
        if(j) f[i][j] = (f[i][j] + f[i + 1][j - 1]) % mod;
    }
    ll ans = 0;
    for(int i = 0;i <= n;i++)
    ans = (ans + C(n,i) * f[0][n]) % mod;
    for(int i = 1;i <= n;i++)
    {
        ans = (ans + C(n-1,i-1) * f[0][n-1]) % mod;
        for(int j = i + 1;j <= n;j++)
        {
            if(a[j] < a[j-1]) break;
            ans = (ans + C(n - (j - i + 1),i-1) * f[0][n - (j - i + 1)]) % mod;
        }
    }
    cout << ans;
}
 
ll C(ll n,ll m)
{
    if(n < m) return 0;
    if(n < 0 || m < 0) return 0;
    return fac[n] * invfac[n - m] % mod * invfac[m] % mod;
}
 
ll ksm(ll a,ll b)
{
    ll ans = 1;
    for(;b;b>>=1,a = a * a % mod) if(b & 1) ans = ans * a % mod;
    return ans;
}
 
}
 
signed main()
{
    Pozhu :: main();
    return 0;
}

C

给你一个长为 nn 的序列 $(a_1,a_2,\cdots,a_n)$ 。
一种“成功”的子序列 $a_{p_1},a_{p_2},\cdots,a_{p_m}$ 满足下面两个条件：

  • 这个子序列的长度为 $K$（输入给出）即 $m=K$

  • 在原序列中没有连续 $D$（本题 $D=2$ ）个元素同时在子序列中，不存在 $p_i+1=p_{i+1}$

定义一个“成功”子序列的权值为 $\sum a_{p_i}$ ，求出所有“成功”子序列的权值和 $\bmod 998244353$

$2 \le N \le 3 times 10^5$

暴力是很好想的 $n^2$ DP，我的实现有 40 pts应该算是比较高

虽然DP数组开pair大概不是好习惯……但不这样写的话我想不到怎么转移了。

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
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
typedef unsigned long long ll;
typedef pair<ll,ll> pii;
const ll mod = 998244353;
#define N 300010
#define fir first
#define sec second
int n,k,d;
int a[N];
pii dp[2][N][2];
 
void main()
{
    scanf("%d%d%d",&n,&k,&d);
    for(int i = 1;i <= n;i++) 
        scanf("%d",&a[i]);
    int w = 1;
    for(int i = 1;i <= n;i++,w ^= 1)
    {
        dp[w][1][1] = pii(a[i],1);
        dp[w][1][0] = pii((dp[w ^ 1][1][0].fir + dp[w ^ 1][1][1].fir) % mod,(dp[w ^ 1][1][0].sec + dp[w ^ 1][1][1].sec) % mod);
        for(int j = 2;j <= k;j++)
        {
            dp[w][j][1] = pii((dp[w ^ 1][j-1][0].fir + a[i] * dp[w ^ 1][j-1][0].sec % mod) % mod,dp[w ^ 1][j-1][0].sec);
            dp[w][j][0] = pii((dp[w ^ 1][j][1].fir + dp[w ^ 1][j][0].fir) % mod,(dp[w ^ 1][j][1].sec + dp[w ^ 1][j][0].sec) % mod);
        }
    }
    w ^= 1;
    cout << (dp[w][k][0].fir + dp[w][k][1].fir) % mod;
}

}

signed main()
{
    Pozhu :: main();
    return 0;
}

考虑正解，发现是组合寄数 ：

定义 ring(n,k) 表示在长为 $n$ 的 环 内取 $k$ 个数的合法方案数。
定义 line(n,k) 表示在长为 $n$ 的 线 内取 $k$ 个数的合法方案数。

由组合数学知识与插板法可知 ： $line(n,k) = \binom{n-k+1}{k} $ 。

然后用这个可以推出环的方案数就是 ：

加号左边表示不取第一个元素，此时删去第一个元素从剩下部分里选 $k$ 个。
加号右边表示取第一个元素，此时删去第一个，第二个和最后一个元素从剩下 $n-3$ 个元素中选取 $k-1$ 个。

所以经过 $O(n)$ 预处理之后上述两个函数都可以 $O(1)$ 求得。

定义 $c_i$ 表示在所有方案中 $i$ 出现了多少次。容易发现在环上我们有 ：

(可以看作每次取到 $i$ 的期望乘以方案数)

对于序列和环的不同我们发现它只多出来了第一项和最后一项可以同时选的情况。

进行一个考虑就可以递归了。

单层递归的复杂度为 $O(1)$ ，递归 $n$ 层，所以总共是 $O(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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
typedef long long ll;   
const ll mod = 998244353;
#define N 300010
 
int n,k,d;
ll mp[N];
ll a[N],ans;
ll fac[N],invfac[N];
 
ll C(ll ,ll );
ll f(int ,int );
ll F(int ,int );
ll ksm(ll ,ll );
 
void main()
{
    cin >> n >> k >> d;
    fac[0] = 1;
    for(int i = 1;i <= n;i++) fac[i] = fac[i-1] * i % mod;
    invfac[n] = ksm(fac[n],mod-2);
    for(int i = n;i;i--) invfac[i-1] = invfac[i] * i % mod;
    for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
    ll sum0 = 0,sum1 = f(n,k),ad1 = 0,ad2 = 0;
    for(int i = 1;i <= n;i++)
    {
        if(i > (n + 1) >> 1) ans = (ans + mp[n - i + 1] * a[i]) % mod;
        else if(i & 1)
        {
            sum1 = (sum1 - f(n - 4 * ad1,k - 2 * ad1) + mod) % mod;
            sum1 = (sum1 + F(n - 4 * ad1,k - 2 * ad1)) % mod;
            ad1++;
            sum1 = (sum1 + f(n - 4 * ad1,k - 2 * ad1)) % mod;
            mp[i] = sum1;
            ans = (ans + sum1 * a[i]) % mod;
        }
        else
        {
            sum0 = (sum0 + F(n - 4 * ad2,k - 2 * ad2)) % mod;
            ++ad2;
            mp[i] = sum0;
            ans = (ans + sum0 * a[i]) % mod;
        }
    }
    cout << ans;
    return;
}
 
ll F(int n,int k)
{
    return n <= 3 ? k == 1 : f(n - 3,k - 1);
}
 
ll f(int n,int k)
{
    return C(n - k + 1,k);
}
 
ll C(ll n,ll m)
{
    if(n < m) return 0;
    if(n < 0 || m < 0) return 0;
    return fac[n] * invfac[n - m] % mod * invfac[m] % mod;
}
 
ll ksm(ll a,ll b)
{
    ll ans = 1;
    for(;b;b>>=1,a = a * a % mod) if(b & 1) ans = ans * a % mod;
    return ans;
}
 
}
 
signed main()
{
    Pozhu :: main();
    return 0;
}