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

xyzfrozen Lv5

典中典题

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

时,直接考虑状压因子,预处理每个数含有哪些因子

为当 选择质因子集合为 时的方案数,枚举每个数进行转移

当值域变大,考虑根号分治, ,即 每个数最多含有一个 的质因子

直接状压前 个质因子(),然后考虑每个数一定属于至多一个 的质因子集合,比如 ,它就属于 这个集合,枚举每个 的质因子集合进行转移

具体就是还是预处理每个数含有的 的质因子集合,设 表示 两人选择的 的质因子集合为 ,当前这个大因数给 的方案数
Misplaced & 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]
当然还要保证

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

对于 质因子的,先给 赋值成 ,然后

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

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] 卡牌

若整数 除以非零整数 ,商为整数,且余数为零, 为被除数, 为除数,即 ,读作“ 整除 ”或“ 能被 整除”。 叫做 的约数(或因数), 叫做 的倍数。整除属于除尽的一种特殊情况

一个类似的题

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

当且仅当

为质数集合 为询问中第 个质数

如果每个质数集合都没有重复的数,那么

考虑容斥,类似 一样定义状态,直接状压质因子集合

为不含与 有公共因子的卡牌个数,贡献为

可以搞个桶 表示卡牌为 的数的个数

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

预处理 的所有状态的

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

这样就得到了 分做法,,此时

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;
}

考虑 的做法,根号分治,其最大质因子如果大于等于 必然只有一个,因为

那么重新定义状态

与前 个质数组合无公共因子,且最大因子为 的卡牌个数

此时我们分开处理,前 个质数还是容斥,但是如果 有大因子,我们就强制必须覆盖大因子(这些不能容斥,必须覆盖)

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

就比如 即覆盖了 ,也覆盖了

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

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
  • 更新于 : 2025-06-18 18:13:46
  • 链接: https://xyzfrozen.github.io/undefined/P2150-NOI2015-寿司晚宴 & P8292 [省选联考 2022] 卡牌/P2150-NOI2015-寿司晚宴/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
P2150 [NOI2015] 寿司晚宴 & P8292 [省选联考 2022] 卡牌