2023牛客暑期多校训练营7 CI「位运算」「根号分治+容斥」

C-Beautiful Sequence_2023牛客暑期多校训练营7 (nowcoder.com)

题意：

给定一个b序列，a序列满足$a[i-1]<=a[i]$且$a[i]\oplus a[i+1]=b[i]$，求字典序第k大的满足条件的a序列，若不存在则输出-1。

思路：

我们对b数组求一个前缀和可以发现：

$pre[1]=0\oplus b[1]=a[1]\oplus a[2]$

$pre[2]=pre[1]\oplus b[2]=a[1]\oplus a[2]\oplus a[2]\oplus a[3]=a[1]\oplus a[3]$

……

依次类推，可以发现$pre[i]=a[1]\oplus a[i+1]$，对于每一组$pre[i]$和$pre[i+1]$，考虑二进制从最高位开始查询，当某一位不同的时候一定是因为$a[i+1]$的这位为1而$a[i]$的这位为0，于是我们可以确定$a[1]$的某一位，遍历完成后会发现可能有一部分位置（sum）的值并未确定，所以所有可能的a序列就有$1<<sum$个，而字典序第k大的就是$a[1]$的取值为第k大的，确定$a[1]$后即可通过b数组求得答案。

AC代码：

#include 
using namespace std;
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
#define int ll
#define pb push_back
#define eb emplace_back
#define m_p make_pair
const int mod = 998244353;
#define mem(a,b) memset(a,b,sizeof a)
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;
const int N = 1e6 + 50;
//__builtin_ctzll(x);后导0的个数
//__builtin_popcount计算二进制中1的个数
ll a[N],b[N],pre[N];
int numa[33];

void work() {
    int n,k;cin>>n>>k;
    pre[0]=0;a[1]=0;
    for(int i=1;i<n;++i){
        cin>>b[i];
        pre[i]=pre[i-1]^b[i];
    }
    for(int i=0;i<=30;++i)numa[i]=-1;

    for(int i=n-1;i>=1;--i){
        for(int j=30;j>=0;--j){
            if(((pre[i]>>j)&1)!=((pre[i-1]>>j)&1)){
                numa[j]=((pre[i-1]>>j)&1);break;
            }
        }
    }

    ll num=0;
    for(int i=0;i<30;++i){
        if(numa[i]==-1)num++;
    }
    if((1<<num)<k){
        cout<<"-1\n";return;
    }
    k--;

    for(int i=30;i>=0;--i){
        if(numa[i]==-1){
            if((k>>num)&1) numa[i]=1;
            else numa[i]=0;
            num--;
        }
    }

    ll x=1;
    for(int i=0;i<=30;++i){
        if(numa[i]==1)a[1]+=x;
        x*=2;
    }
    for(int i=2;i<=n;++i){
        a[i]=a[i-1]^b[i-1];
        if(a[i]<a[i-1]){
            cout<<"-1\n";return;
        }
    }
    for(int i=1;i<=n;++i){
        cout<<a[i]<<" \n"[i==n];
    }
}

signed main() {
    io;
    int t=1;
    cin >> t;
    while (t--) {
        work();
    }
    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
68
69
70
71
72
73
74
75
76
77
78
79

I-We Love Strings_2023牛客暑期多校训练营7 (nowcoder.com)

题意：

给定n个01?字串，其中?可以是0也可以是1，询问有多少个01字串符合至少一个给定的正则串。

思路：

根号分治。

在字串长小于20（$sqrt(400)$）时dfs暴力找，总复杂度不会超过$2^{21}$。

大于20时，容斥：奇加偶减。

AC代码：

#include 
using namespace std;
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
#define int ll
#define pb push_back
#define eb emplace_back
#define m_p make_pair
const int mod = 998244353;
#define mem(a,b) memset(a,b,sizeof a)
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;
const ll N = 405;
//__builtin_ctzll(x);后导0的个数
//__builtin_popcount计算二进制中1的个数
ll ans=0;
vector<string>a[N];
string tmp;
int n;

void small(int now,int len){
    if (now==len+1){
        for(auto x:a[len]){
            bool ok=1;
            for(int j=0;j<len;j++) {
                if(x[j]=='?') continue;
                if(x[j]!=tmp[j]){
                    ok=0;
                    break;
                }
            }
            if (ok) {
                ans++;
                break;
            }
        }
        return ;
    }
    tmp+='0';
    small(now+1,len);
    tmp.pop_back();

    tmp+='1';
    small(now+1,len);
    tmp.pop_back();
}

void big(int len,int size){
    ll m=1<<size;//正则串随意组合的情况数
    for(int i=1;i<m;++i){//枚举所有可能
        int cnt=0,ok=1;
        tmp.clear();
        for(int j=0;j<len;++j)tmp+="?";
        for(int j=0;j<size;++j){//枚举每种正则串的组合方式
            if(i>>j&1){
                cnt++;
                for(int t=0;t<len;++t){//枚举每一位
                    char x=a[len][j][t];
                    if(tmp[t]=='?'){
                        tmp[t]=x;
                    }else if(x!='?'&&tmp[t]!=x){
                        ok=0;break;
                    }
                }
                if(!ok)break;
            }
        }
        if(!ok)continue;
        int p=1;
        for(int j=0;j<len;++j){
            if(tmp[j]=='?')p=p*2%mod;//计算有多少个未确定的字符，每个未确定代表两种可能
        }
        if(cnt&1){
            ans=(ans+p)%mod;
        }
        else ans=(ans-p)%mod;
    }
}

void work() {
    cin>>n;
    for(int i=1;i<=n;++i){
        string s;cin>>s;
        a[s.size()].pb(s);
    }
    for(int i=1;i<N;++i){
        if(!a[i].size()){
            continue;
        }if(i<=20){
            tmp.clear();
            small(1,i);
        }else{
            big(i,a[i].size());
        }
    }
    ans%=mod;
    cout<<ans<<'\n';
}

signed main() {
    io;
    int t=1;
    //cin >> t;
    while (t--) {
        work();
    }
    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
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