Kyooma's Blog

2023牛客多校07

  • ~16.98K 字

题目来自: 2023牛客暑期多校训练营7

Solved Rank A B C D E F G H I J K L M
4 / 13 139 / 1437 - - O - - O Ø - O - Ø Ø O
  • Ø 赛后通过
  • O 在比赛中通过
  • ! 尝试了但是失败了
  • - 没有尝试

C - Beautiful Sequence

DESCRIPTION

给出一个序列 $B$，求字典序第 $k$ 小的序列 $A$ 且满足 $A1 \le A_2 \le … \le A_n$，且 $0 \le A_i < 2^{30}$ ，且 $A_i \oplus A{i + 1} = B_i$。

SOLUTION

可以发现，一旦 $A_1$ 确定了，那么整个序列就固定了，那么考虑去找第 $k$ 小的 $A_1$。

对于 $Bi$ 来说，$A_i \oplus B_i = A{i+1}$ 显然只有最高位的 $1$ 有影响，且 $A_i$ 在 $B_i$ 最高位 $1$ 的位置必须是 $0$ ，且影响不到其他二进制位。那么再记一个前缀和就能得到 $A_i$ 在某位为 $0$ 时 $A_1$ 的值时多少，如果 $A_1$ 还未确定就确定下这一位，如果已经确定过了那么就验证合法性，最后在没确定位置中取第 $k$ 小即可。

CODE
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, Log = 30;

int b[N], cnt[Log + 5], is[Log + 5];

void solve(){
	int n, k;
	cin >> n >> k;
	for(int i = 1; i < n; i++){
		cin >> b[i];
	}
	for(int i = 0; i <= Log; i++){
		cnt[i] = 0;
		is[i] = -1;
	}
	int ok = 1;
	for(int i = 1; i < n; i++){
		for(int j = Log; j >= 0; j--){
			if(b[i] >> j & 1){
				if(is[j] != -1){
					if((is[j] ^ cnt[j]) == 1) ok = 0;
				}else{
					is[j] = cnt[j];
				}
				break;
			}
		}
		for(int j = 0; j < Log; j++){
			if(b[i] >> j & 1){
				cnt[j] ^= 1;
			}
		}
	}
	if(!ok){
		cout << "-1\n";
		return;
	}
	k--;
	int ans = 0;
	for(int i = 0; i < Log; i++){
		if(is[i] == -1){
			is[i] = k & 1;
			k /= 2;
		}
		ans += (1 << i) * is[i];
	}
	if(k){
		cout << "-1\n";
		return;
	}
	cout << ans;
	for(int i = 1; i < n; i++){
		ans ^= b[i];
		cout << " " << ans;
	}
	cout << '\n';
} 

int main(void){
	int T=1;
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--){
		solve();
	} 
}

F - Counting Sequences

DESCRIPTION

给出$n, m, k$，求有多少个序列 $A = (A1, A_2, …, A_n),\ 0 \le A_i < 2^m$，序列 $B = (A_2, A_3, …, A_n, A_1)$，满足 $\sum \limits{i = 1} ^ {n} cnt_1(A_i \oplus B_i) = k$。$cnt_1(x)$ 表示 $x$ 二进制中 $1$ 的个数。

SOLUTION

多项式，队友秒了。

CODE
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef unsigned long long ull;
#define fi first
#define se second
const int N=500010;
const int mod=998244353;
const int G=3;
const int GI=332748118;
ll f[N],g[N],e[N];
ll qm(ll x,ll y){
    ll b=1;
    while(y){
        if(y&1) b=b*x%mod;
        y/=2;
        x=x*x%mod;
    }
    return b;
}
int rev[4*N];
ll A[N],B[N],C[N],D[N];
ll I=499122177;
void ntt(ll *a,int n,int c){
    int i;
    for(i=0;i<=n-1;++i){
        if(i<rev[i]) swap(a[i],a[rev[i]]);
    }
    for(ll p=2;p<=n;p<<=1){
        ll gen;
        if(c==1) gen=qm(G,(mod-1)/p);
        else gen=qm(GI,(mod-1)/p);
        for(ll l=0;l<n;l+=p){
            ll lp=1;
            for(ll k=l;k<l+p/2;++k){
                ll tmp=a[k+p/2];
                a[k+p/2]=(a[k]-tmp*lp%mod+mod)%mod;
                a[k]=(a[k]+tmp*lp%mod)%mod;
                lp=lp*gen%mod;
            }
        }
    }
    if(c==-1){
        for(int i=0;i<n;i++) a[i]=a[i]*qm(n,mod-2)%mod;
    }
}
void calc(ll *a,ll *b,int n){
    int i;
    for(i=0;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)?n>>1:0);
    ntt(a,n,1),ntt(b,n,1);
    for(i=0;i<n;i++) a[i]=a[i]*b[i]%mod;
    ntt(a,n,-1);
}
void Inv(ll *a,ll *b,int n){
    b[0]=qm(a[0],mod-2);
    int i,len,lim;
    for(len=1;len<(n<<1);len<<=1){
        lim=len<<1;
        for(i=0;i<len;i++) A[i]=a[i],B[i]=b[i];
        for(i=0;i<lim;i++) rev[i]=(rev[i>>1]>>1)|((i&1)?lim>>1:0);
        ntt(A,lim,1),ntt(B,lim,1);
        for(i=0;i<lim;i++) b[i]=B[i]*((2-A[i]*B[i]%mod+mod)%mod)%mod;
        ntt(b,lim,-1);
        for(i=len;i<lim;i++) b[i]=0;
    }
    for(i=0;i<len;i++) A[i]=B[i]=0;
    for(i=n;i<len;i++) b[i]=0;
}
void Sqrt(ll *a,ll *b,int n){
    b[0]=1;
    ll *A=C,*B=D,len,lim,i;
    for(len=1;len<(n<<1);len<<=1){
        lim=len<<1;
        for(i=0;i<len;i++) A[i]=a[i];
        Inv(b,B,len);
        for(i=0;i<lim;i++) rev[i]=(rev[i>>1]>>1)|((i&1)?lim>>1:0);
        ntt(A,lim,1),ntt(B,lim,1);
        for(i=0;i<lim;i++) A[i]=A[i]*B[i]%mod;
        ntt(A,lim,-1);
        for(i=0;i<len;i++) b[i]=(b[i]+A[i])*I%mod;
        for(i=len;i<lim;i++) b[i]=0;
    }
    for(i=0;i<len;i++) A[i]=B[i]=0;
    for(i=n;i<len;i++) b[i]=0;
}
void Dao(ll *a,ll *b,int n){
    for(int i=1;i<n;i++) b[i-1]=a[i]*i%mod;
    b[n-1]=0;
}
void Ji(ll *a,ll *b,int n){
    for(int i=1;i<n;i++) b[i]=a[i-1]*qm(i,mod-2)%mod;
    b[0]=0;
}
ll F[N],F1[N],F2[N];
void GetIn(ll *a,ll *b,int n){
    Dao(a,F,n);
    Inv(a,F1,n);
    int len=1;
    while(len<2*n) len<<=1;
    calc(F,F1,len);
    Ji(F,b,n);
    for(int i=0;i<len;i++) F[i]=F1[i]=0;
    for(int i=n;i<len;i++) b[i]=0;
}
void GetExp(ll *a,ll *b,int n){
    if(n==1){
        b[0]=1;
        return;
    }
    GetExp(a,b,n>>1);
    GetIn(b,F2,n);
    for(int i=0;i<n;i++) F2[i]=(a[i]-F2[i]+mod)%mod;
    F2[0]=(F2[0]+1)%mod;
    int len=1;
    while(len<n<<1) len<<=1;
    calc(b,F2,len);
    for(int i=n;i<len;i++) b[i]=F2[i]=0;
}
void solve(){
    ll lp,i,n,m;
    ll x=1;
    ll k=0;
    string s;
    cin>>m>>s>>n;// n,m,k
    for(i=0;i<s.length();i++) k=(k*10+s[i]-'0')%mod;
//    printf("%lld %lld %lld\n",n,m,k);
    for(i=0;i<=min(n,m);i+=2){
    	f[i]=x;
    	x=x*(m-i)%mod*(m-i-1)%mod;
    	x=x*qm(i+1,mod-2)%mod*qm(i+2,mod-2)%mod;
	}
	n++;
//	for(i=0;i<n;i++) printf("%lld ",f[i]);
    GetIn(f,g,n);
    for(i=0;i<n;i++) g[i]=g[i]*k%mod;
    int len=1;
    while(len<=n) len<<=1;
    GetExp(g,e,len);
    printf("%lld\n",e[n-1]*qm(2,k)%mod);
//    for(i=0;i<n;i++) printf("%lld ",e[i]);
}
int main() {
    int T=1;
    //ios::sync_with_stdio(false);
    //cin>>T;
    //init();
    while (T--) {
        solve();
    }
}

G - Cyperation

DESCRIPTION

给一个长度为 $n$ 的环 $a$，对于一组 $i, j$ 满足 $min(j - i, n - i + j) = k$ ，可以将 $a_i$ 和 $a_j$ 同时减去 $1$，问最后能不能变为全 $0$。

SOLUTION

首先如果数组全 $0$ 则答案为 $YES$。

如果 $k > \lfloor \frac{n}{2} \rfloor$ 则无解。

接下来我们把隔 $k$ 距离的数取出来，可以发现这可以构成若干个环，而且在一个环中的一次操作变为了对两个相邻的数同时减去 $1$。

对于每个环，我们设 $xi$ 为操作环上第 $i$ 条边相连的两个数的次数，$y_i$ 表示换上第 $i$ 个数在 $a$ 中的值，那么可以列出一系列形如 $x_i + x{i - 1} = y_i$ 的式子。

对于一个奇数环，我们可以直接解出每个 $x_i$ 的值判断是否都大于等于 $0$。

对于一个偶数环，由于有效方程个数只有 $n - 1$ 个，是有多解存在的，可以考虑把每个 $x_i$ 都写成关于 $x_1$ 的式子，通过 $x_i \ge 0$ 的条件可以不断缩小 $x_1$ 的取值范围，最后判断取值范围是否为空即可。

CODE
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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e6 + 10;
const ll inf = 1e18;

int a[N], vis[N];

bool gao(vector<int> v){
    int n = (int)v.size();
    if(n & 1){
        ll sum = 0, t = 0;
        for(int i = 0; i < n; i++){
            sum += a[v[i]];
            if(~i&1) t += a[v[i]];
        }
        if(sum & 1) return false;
        sum /= 2;
        ll x = t - sum;
        for(int i : v){
            x = a[i] - x;
            if(x < 0) return false;
        }
        return true;
    }
    ll t = 0, s = 0, l = -inf, r = inf;
    for(int i = 0; i < n; i++){
        if(i & 1){
            t += a[v[i]];
            l = max(l, s - t);
        }else{
            s += a[v[i]];
            r = min(r, s - t);
        }
    }
    if(t != s || l > r) return false;
    return true;
}

void solve() {
    int n, k, ok = 1;
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        if(a[i]) ok = 0;
        vis[i] = 0;
    }
    if(ok){
        cout << "YES\n";
        return;
    }
    ok = (k <= (n / 2));
    for(int i = 1; i <= n; i++){
        if(vis[i]) continue;
        int p = i;
        vector<int> v;
        while(!vis[p]){
            vis[p] = 1;
            v.push_back(p);
            p += k;
            if(p > n) p -= n;
        }
        ok &= gao(v);
    }
    if(ok) cout << "YES\n";
    else cout << "NO\n";
}

int main() {
    int T = 1;
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) solve();
    return 0;
}

I - We Love Strings

DESCRIPTION

给出 $n$ 个 $01?$ 串，其中 $?$ 可以替换为 $0$ 或者 $1$，问这些串覆盖了多少个 $01$ 串，串的长度总和以及 $n$ 都是小于等于 $400$。

SOLUTION

首先对每个长度的串分类。

考虑更号分治，如果个数小于等于 $20$ 则容斥，否则说明每个串的长度小于等于 $20$，这个时候就直接枚举每个 $?$ 是 $0$ 还是 $1$。

CODE
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 400 + 5, Log = 30, mod = 998244353, M = 2e6 + 10;

vector<string> v[N];

bool jud(string &a, string b, int p){
	for(int i = 0; i < p; i++){
		if(a[i] != b[i]){
			if(a[i] != '2' && b[i] != '2') return false;
			if(a[i] == '2') a[i] = b[i];
		}
	}
	return true;
}

int ans, vis[M];

void gao(int p){
	sort(v[p].begin(), v[p].end());
	v[p].erase(unique(v[p].begin(), v[p].end()), v[p].end());
	int m = (int)v[p].size();
	if(m <= 20){
		for(int i = 1; i < (1 << m); i++){
			string t(p, '2');
			bool ok = true;
			int cnt = 0;
			for(int j = 0; j < m; j++){
				if(i >> j & 1){
					ok &= jud(t, v[p][j], p);
					cnt++;
				}
			}
			int res = 1;
			if(!ok) res = 0;
			else{
				for(char j : t){
					if(j == '2'){
						res = res * 2;
						if(res >= mod) res -= mod;
					}
				}
			}
			if(cnt & 1){
				ans += res;
				if(ans >= mod) ans -= mod;
			}else{
				ans -= res;
				if(ans < 0) ans += mod;
			}
		}
	}else{
		for(int i = 0; i < (1 << p); i++) vis[i] = 0;
		for(int i = 0; i < m; i++){
			vector<int> vp;
			for(int j = 0; j < p; j++){
				if(v[p][i][j] == '2') vp.push_back(j);
			}
			int rnm = (int)vp.size();
			for(int j = 0; j < (1 << rnm); j++){
				for(int k = 0; k < rnm; k++){
					if(j >> k & 1){
						v[p][i][k] = '1';
					}else{
						v[p][i][k] = '0';
					}
				}
				int res = 0;
				for(char k : v[p][i]){
					res = res * 2 + k - '0';
				}	
				vis[res]++;
				if(vis[res] == 1) ans++;
			}
		}
	}
}

void solve(){
	int n, mx = 0;
	cin >> n;
	string s;
	for(int i = 0; i < n; i++){
		cin >> s;
		int m = (int)s.size();
		for(char &j : s){
			if(j == '?') j = '2';
		}
		mx = max(mx, m);
		v[m].push_back(s);
	}
	for(int i = 1; i <= mx; i++){
		if(v[i].empty()) continue;
		gao(i);
	}
	cout << ans << '\n';
} 

int main(void){
	int T=1;
	ios::sync_with_stdio(false);
//	cin>>T;
	while(T--){
		solve();
	} 
}
/*
5
??
?101
0001
0000
0001
*/

K - Set

DESCRIPTION

TBD

SOLUTION

TBD

CODE
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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int Log = 32, mod = 998244353;

void add(int &x, int y){
    x += y;
    if(x >= mod) x -= mod;
}

void solve() {
    int n, ans = 0;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    for(int i = 0; i < Log; i++){
        array<int, 2> f = {}, g = {};
        // fi 表示异或和为i的最小值的和
        // gi 表示异或和为i的最小值 \times 长度的和
        for(int j = 0; j < n; j++){
            int x = a[j] >> i & 1;
            array tf = f, tg = g;//1
            int aj = a[j] % mod;
            add(ans, (1ll << i) * aj % mod * (0ll + tg[x ^ 1] + tf[x ^ 1] + a[j] * x) % mod);
            if(x){// x=1
                add(tf[1], (f[0] + aj) % mod);
                add(tf[0], f[1]);
                add(tg[1], (0ll + f[0] + aj + g[0]) % mod);
                add(tg[0], (g[1] + f[1]) % mod);
            }else{// x=0
                add(tf[1], f[1]);
                add(tf[0], (f[0] + aj) % mod);
                add(tg[1], (f[1] + g[1]) % mod);
                add(tg[0], (0ll + g[0] + f[0] + aj) % mod);
            }
            f = tf, g = tg;
        }
    }
    cout << ans;
}

int main() {
    int T = 1;
    ios::sync_with_stdio(false);
    // cin >> T;
    while (T--) solve();
    return 0;
}

L - Misaka Mikoto’s Dynamic KMP Problem

DESCRIPTION

诈骗题

SOLUTION

kmp

CODE
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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e6 + 10, Log = 20, inf = 0x3f3f3f3f;

int nxt[N];
int a[N], b[N];

int kmp(int n, int m){
    int res = 0;
    nxt[0] = -1;
    for(int j = -1, i = 0; i < n;){
        if(j == -1 || a[j] == a[i]){
            i++;j++;
            nxt[i] = j;
        }else{
            j = nxt[j];
        }
    }
    //i 模式串  j 匹配串
    for(int i = 0, j = 0; j < m; ){
        if(i == -1 || a[i] == b[j]){
            i++;j++;
        }else i = nxt[i];
        if(i == n - 1) res++;
    }
    return res;
}

void solve() {
    int n, m, bi, p;
    cin >> n >> m >> bi >> p;
    for(int i = 0; i < n; i++) cin >> a[i];
    int z = 0, ans = 0, fi = 1;
    for(int i = 1, op; i <= m; i++){
        cin >> op;
        if(op == 1){
            int x, c;
            cin >> x >> c;
            x = (x ^ z) % n + 1;
            c = c ^ z;
            a[x - 1] = c;
        }else{
            fi = 1ll * fi * bi % p;
            int tn;
            cin >> tn;
            for(int j = 0; j < tn; j++){
                cin >> b[j];
                b[j] ^= z;
            }
            if(n > tn){
                z = 0;
                continue;
            }
            z = 1ll * kmp(n, tn) * nxt[n] % p;
            // dbg(z, nxt[n]);
            ans += 1ll * z * fi % p;
            if(ans >= p) ans -= p;
        }
    }
    cout << ans;
}

int main() {
    int T = 1;
    ios::sync_with_stdio(false);
    // cin >> T;
    while (T--) solve();
    return 0;
}

M - Writing Books

DESCRIPTION

签到题

SOLUTION

队友秒了

CODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
	ll n,i,j,x=1,y;
	ll ans=0,v=1,cnt=0;
	cin>>n;
	while(v<=n){
		v*=10;
		ans+=1ll*x*(min(v-1,n)-cnt);
		cnt=v-1;
		x++;
	}
//	ans--;
//	ans+=max(0,)
	printf("%lld\n",ans);
} 
int main(void){
	int T=1;
	cin>>T;
	while(T--){
		solve();
	} 
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可