P2150 [NOI2015] 寿司晚宴 & P8292 [省选联考 2022] 卡牌

xyzfrozen Lv5
  2023-10-14 22:05:39 2023-10-14 22:05:39 创建   2023-10-14 23:29:51 2023-10-14 23:29:51 更新      2.3k 字  11 分钟  

典中典题

核心为，先观察出值域较小的情况，然后根号分治分开处理两侧，选择一遍进行状压，另一边用其它算法处理

当 $n \leq 30$ 时，直接考虑状压因子，预处理每个数含有哪些因子

设 $f_{S,T}$ 为当 $G$，$W$ 选择质因子集合为 $S$，$T$ 时的方案数，枚举每个数进行转移

当值域变大，考虑根号分治， $23 \times 23 \gt 500$ ，即 每个数最多含有一个 $\gt 23$ 的质因子

直接状压前 $8$ 个质因子（$pr_8=19$)，然后考虑每个数一定属于至多一个 $pr \geq 23$ 的质因子集合，比如 $46$，它就属于 $23$ 这个集合，枚举每个 $\geq 23$ 的质因子集合进行转移

具体就是还是预处理每个数含有的 $\leq 19$ 的质因子集合，设 $g_{0/1,S,T}$ 表示 $G,W$ 两人选择的 $\leq 19$ 的质因子集合为 $S,T$，当前这个大因数给 $G/W$ 的方案数
$$
g_{0,S\cup v_i,T} \gets g_{0,S,T} &[v_i \land T=0]\
g_{1,S,T\cup v_i} \gets g_{1,S,T} &[v_i \land S=0]
$$
当然还要保证 $S \land T=0$

对于只含有 $\leq 19$ 质因子的数挑出来先单独转移

对于 $\geq 23$ 质因子的，先给 $g$ 赋值成 $f$，然后 $f_{S,T} \gets g_{0,S,T}+g_{1,S,T}-f_{S,T}$

减去是因为 $S,T$ 都不要含该质因子的数算重了

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
#include<bits/stdc++.h>
#define int long long
#define pt putchar(' ')
#define nl puts("")
#define pi pair<int,int>
#define pb push_back
#define go(it) for(auto &it:as[x])
using namespace std;

const int N=510,M=(1<<8)+10;
int n,p,ans;
int f[M][M],g[2][M][M],v[N];
set<int> s;
vector<int> P[N];
const int pr[]={2,3,5,7,11,13,17,19};

int fr(){
    int x=0,flag=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') flag=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    return x*flag;
}
void fw(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) fw(x/10);
    putchar(x%10+'0');
}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void mod(int &x,int y){if((x+=y)>=p) x-=p;}

void solve(vector<int> a)
{
    memcpy(g[0],f,sizeof g[0]);
    memcpy(g[1],f,sizeof g[1]);
    for(auto &i:a)
    {
        for(int S=(1<<8)-1;~S;S--)
            for(int T=(1<<8)-1;~T;T--)
            {
                if(S&T) continue;
                if(!(v[i]&T)) mod(g[0][v[i]|S][T],g[0][S][T]);
                if(!(v[i]&S)) mod(g[1][S][v[i]|T],g[1][S][T]);
            }
    }
    for(int S=(1<<8)-1;~S;S--)
        for(int T=(1<<8)-1;~T;T--)
            if(!(S&T)) f[S][T]=(g[0][S][T]+g[1][S][T]-f[S][T]+p)%p;
}

signed main()
{
    n=fr(),p=fr();
    for(int i=2;i<=n;i++)
    {
        int x=i;
        for(int j=0;j<8;j++)
            if(!(x%pr[j]))
            {
                v[i]|=(1<<j);
                while(!(x%pr[j])) x/=pr[j];
            }
        P[x].pb(i);
        s.insert(x);
    }
    
    f[0][0]=1;
    for(auto v:P[1]) //只含有 <19 质因子的数集合
    {
        vector<int> a(1,v);
        solve(a);
    }
    for(auto i:s) //大质因子集合转移
        if(i!=1) solve(P[i]);
    for(int S=0;S<=(1<<8)-1;S++)
        for(int T=0;T<=(1<<8)-1;T++)
            if(!(S&T)) mod(ans,f[S][T]);
    fw(ans);
    return 0;
}

P8292 [省选联考 2022] 卡牌

若整数 $b$ 除以非零整数 $a$，商为整数，且余数为零，$b$ 为被除数，$a$ 为除数，即 $a \mid b$，读作“ $a$ 整除 $b$ ”或“$b$ 能被 $a$ 整除”。$a$ 叫做 $b$ 的约数（或因数），$b$ 叫做 $a$ 的倍数。整除属于除尽的一种特殊情况

一个类似的题

首先一个显然的想法，根据给定的质数给卡牌划分下集合

$x \in S_i$ 当且仅当 $p_i \mid x$

$S_i$ 为质数集合 $p_i$ 为询问中第 $i$ 个质数

如果每个质数集合都没有重复的数，那么 $ans=\prod;(2^{|S_i|}-1)$

考虑容斥，类似 $devu;and;flower$ 一样定义状态，直接状压质因子集合

设 $f_S$ 为不含与 $S$ 有公共因子的卡牌个数，贡献为 $2^{f_S}$

可以搞个桶 $rec$，$rec_i$ 表示卡牌为 $i$ 的数的个数

然后直接枚举状态和值域，位运算判断有没有公共因子即可

预处理 $0 \to (1<<13)-1$ 的所有状态的 $f$

根据每次询问的质数进行子集转移，直接大力容斥即可

这样就得到了 $s_i \leq 30$ 的 $25$ 分做法，$O(2{c}|S_i|+T2cm)$，此时 $c=13$

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
const int N=1e6+10,V=2e3+10,Q=998244353;
int n,m,cnt;
int w[N],pr[N],v[N],pos[N],own[N];
int f[1<<16],rec[N],p[N]={1};
vector<int> now;

void init()
{
    for(int i=2;i<=2020;i++)
    {
        if(!v[i]) pr[++cnt]=i,v[i]=i,pos[i]=cnt;
        for(int j=1;pr[j]<=2020/i;j++)
        {
            v[i*pr[j]]=pr[j];
            if(!(i%pr[j])) break;
        }
    }
    
    for(int i=1;i<=2000;i++)
    {
        int x=i;
        while(x>1)
        {
            own[i]|=(1<<(pos[v[x]]-1));
            x/=v[x];
        }
    }
    
    for(int i=0;i<=(1<<13)-1;i++)
        for(int j=1;j<=2000;j++)	
            f[i]=(f[i]+(!(own[j]&i))*rec[j])%Q;
}

int solve()
{
    int st=0,ans=0;
    for(auto it:now) st|=(1<<(pos[it]-1));
    
    for(int i=0;i<=(1<<13)-1;i++)
    {
        if((i|st)!=st) continue; //子集转移
        int cnt=0;
        for(int j=0;j<13;j++)
            if((i>>j)&1) cnt++;
        
        cnt=(cnt&1)?-1ll:1ll;
        ans=(ans+p[f[i]]*cnt%Q)%Q;
    }
    return (ans%Q+Q)%Q;
}

signed main()
{    
    n=fr();
    for(int i=1;i<=n;i++) rec[fr()]++;
    for(int i=1;i<N;i++) p[i]=(p[i-1]<<1)%Q;
    init();
    m=fr();
    for(int i=1;i<=m;i++)
    {
        int tot=fr();
        now.clear();
        while(tot--) now.pb(fr());
        sort(now.begin(),now.end());
        now.erase(unique(now.begin(),now.end()),now.end());
        fw(solve()),nl;
    }
    return 0;
}

考虑 $s_i \gt 30$ 的做法，根号分治，其最大质因子如果大于等于 $43$ 必然只有一个，因为$43 \cdot 47 \gt 2000$

那么重新定义状态

$f_{i,j}$ 与前 $13$ 个质数组合无公共因子，且最大因子为 $j,(j>=43)$ 的卡牌个数

此时我们分开处理，前 $13$ 个质数还是容斥，但是如果 $c_i$ 有大因子，我们就强制必须覆盖大因子（这些不能容斥，必须覆盖）

还是和之前一样处理 $f_i$，但是在枚举值域的时候，判断下如果当前枚举的卡牌数最大质因子 $\geq 43$ 就记录下即覆盖了前 $13$ 个质因子，又覆盖了大质因子数的个数

就比如 $94$ 即覆盖了 $2$，也覆盖了 $47$

然后后面分开计算直接枚举询问中的大质因子，前 $13$ 质因子自由组合且不含 大因子 $j$ 的方案，后面的大因子就是任选方案

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
const int N=1e6+10,Q=998244353;
int n,m,cnt;
int w[N],pr[N],v[N],pos[N],own[N],sum[(1<<13)+5][310],maxn[N];
int f[(1<<13)+5],rec[N],p[N];
vector<int> now;

void init()
{
    for(int i=2;i<=2020;i++)
    {
        if(!v[i]) pr[++cnt]=i,v[i]=i,pos[i]=cnt;
        for(int j=1;pr[j]<=2020/i;j++)
        {
            v[i*pr[j]]=pr[j];
            if(!(i%pr[j])) break;
        }
    }
    
    for(int i=1;i<=2000;i++)
    {
        int x=i,mx=0;
        while(x>1)
        {
            mx=max(mx,v[x]);
            if(v[x]<=41) own[i]|=(1<<(pos[v[x]]-1));
            //含有的质因子的二进制串表示
            x/=v[x];
        }
        maxn[i]=mx;
    }
    
    for(int i=0;i<=(1<<13)-1;i++)
        for(int j=1;j<=2000;j++)	
            {
                f[i]=(f[i]+(!(own[j]&i))*rec[j])%Q;
                //只要&出来有1 就说明只要有一个重复因子
                if(maxn[j]>=43) sum[i][pos[maxn[j]]]+=(!(own[j]&i))*rec[j];
                //满足和组合i无公共因子 且最大质因子>=43 强选这个因子
            }
}

int solve()
{
    int st=0,ans=0;
    for(auto it:now)
        if(it<=41) st|=(1<<(pos[it]-1));
    //f[i][j] 与前13个质数组合无公共因子，且最大因子为 j(j>=43) 的个数
    for(int i=0;i<=(1<<13)-1;i++)
    {
        if((i|st)!=st) continue;
        //从当前情况的子集转移
        int cnt=0,val1=f[i],val2=1;
        for(int j=0;j<13;j++) cnt+=((i>>j)&1);
        for(auto it:now) //sum[i][pos[it]] 显然就不合法了 后面的大因子当然就随便选了，但是必须覆盖
            if(it>=43) val1-=sum[i][pos[it]],val2=(val2*(p[sum[i][pos[it]]]-1))%Q;
        cnt=(cnt&1)?-1ll:1ll;
        ans=(ans+p[val1]*val2*cnt%Q)%Q;
    }
    return (ans%Q+Q)%Q;
}

signed main()
{    
    n=fr();p[0]=1;
    for(int i=1;i<=n;i++) rec[fr()]++;
    for(int i=1;i<N;i++) p[i]=(p[i-1]<<1ll)%Q;
    init();
    
    m=fr();
    for(int i=1;i<=m;i++)
    {
        int tot=fr();
        now.clear();
        while(tot--) now.pb(fr());
        sort(now.begin(),now.end());
        now.erase(unique(now.begin(),now.end()),now.end());
        fw(solve()),nl;
    }
    return 0;
}
  • 标题: P2150 [NOI2015] 寿司晚宴 & P8292 [省选联考 2022] 卡牌
  • 作者: xyzfrozen
  • 创建于 : 2023-10-14 22:05:39
  • 更新于 : 2023-10-14 23:29:51
  • 链接: https://xyzfrozen.github.io/undefined/P2150-NOI2015-寿司晚宴 & P8292 [省选联考 2022] 卡牌/P2150-NOI2015-寿司晚宴/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
 评论
此页目录
P2150 [NOI2015] 寿司晚宴 & P8292 [省选联考 2022] 卡牌