P2150 [NOI2015] 寿司晚宴 & P8292 [省选联考 2022] 卡牌
典中典题
核心为,先观察出值域较小的情况,然后根号分治分开处理两侧,选择一遍进行状压,另一边用其它算法处理
当 时,直接考虑状压因子,预处理每个数含有哪些因子
设 为当 , 选择质因子集合为 , 时的方案数,枚举每个数进行转移
当值域变大,考虑根号分治, ,即 每个数最多含有一个 的质因子
直接状压前 个质因子( ),然后考虑每个数一定属于至多一个 的质因子集合,比如 ,它就属于 这个集合,枚举每个 的质因子集合进行转移
具体就是还是预处理每个数含有的 的质因子集合,设 表示 两人选择的 的质因子集合为 ,当前这个大因数给 的方案数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 ]) { 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; if (maxn[j]>=43 ) sum[i][pos[maxn[j]]]+=(!(own[j]&i))*rec[j]; } } int solve () { int st=0 ,ans=0 ; for (auto it:now) if (it<=41 ) st|=(1 <<(pos[it]-1 )); 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) 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 ; }