简要题意
多重背包但是乘法
思路
暴力就直接跑背包
考虑乘法能否变为加法,可以找到模数的原根,将每个数映射一下,这样乘法就变成了加法,可以直接\(\text{bitset}\)优化,但是暴力这样做还是过不了
于是我们考虑二进制分组优化背包,这样复杂度貌似就对了?
code
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
using namespace std;
#define N 200005
int mod,n,op,x,ans,g;
int id[N],vis[N];
bitset<N> f;
int chk(int g){
for(int i=1,num=g;i<mod;i++,num=1ll*num*g%mod){
if(num==1&&i!=mod-1) return 0;
if(num!=1&&i==mod-1) return 0;
}
return 1;
}
void gt_g(){
for(g=1;g<mod;g++){
if(chk(g)) break;
}
for(int i=0,num=1;i<mod-1;i++,num=1ll*num*g%mod) id[num]=i;
}
void upd(int x){
f=f|(f<<x)|(f>>(mod-1-x));
}
int main(){
freopen("dance.in","r",stdin);
freopen("dance.out","w",stdout);
scanf("%d%d",&mod,&n);
gt_g();f[id[1]]=1;
for(int i=1;i<=n;i++){
scanf("%d%d",&op,&x);
if(!x) ans=1;
if(op) vis[x]++;
else f[id[x]]=1;
}
for(int i=1;i<mod;i++){
int cnt=vis[i],num=i;
for(int t=1;cnt>=t;t=t*2,num=1ll*num*num%mod){
cnt-=t;upd(id[num]);
}
if(cnt){
num=1;
while(cnt) num=1ll*num*i%mod,cnt--;
upd(id[num]);
}
}
for(int i=0;i<mod-1;i++) ans+=f[i];
printf("%d\n",ans);
return 0;
}
标签:cnt,1.15,int,题解,T2,num,乘法,id,mod
From: https://www.cnblogs.com/hubingshan/p/17966443