福永网站建设公司有没有,yy直播是免费的吗,wordpress 相关帖子,wordpress 评论 作者正题
题目链接:https://www.luogu.com.cn/problem/P8292 题目大意
有nnn张卡牌#xff0c;第iii张上的数字是sis_isi。mmm次询问给出cic_ici个质数#xff0c;要求选择一些卡使得这些卡的乘积是这些质数的倍数#xff0c;求方案数。 1≤n≤106,1≤si≤2000,1≤m≤1500…正题
题目链接:https://www.luogu.com.cn/problem/P8292 题目大意
有nnn张卡牌第iii张上的数字是sis_isi。mmm次询问给出cic_ici个质数要求选择一些卡使得这些卡的乘积是这些质数的倍数求方案数。
1≤n≤106,1≤si≤2000,1≤m≤1500,∑i1mci≤180001\leq n\leq 10^6,1\leq s_i\leq 2000,1\leq m\leq 1500,\sum_{i1}^m c_i\leq 180001≤n≤106,1≤si≤2000,1≤m≤1500,∑i1mci≤18000 解题思路
对于一个数字xxx来说大于x\sqrt xx的质因子只会有一个也就是对于大于所有的si\sqrt s_isi的质数ppp它们的倍数之间不会产生重复可以分开计数。
而小于si\sqrt s_isi的质数个数只有141414个我们可以考虑状压。
处理出gsg_sgs表示在集合sss中的质数都不选择即没有这些数的倍数时的数字个数然后再预处理出一个fi,sf_{i,s}fi,s表示质数iii的倍数中集合sss中的质数都不选择时的数字个数。
那么对于一个询问我们先处理出小于等于s\sqrt ss的质数被加进去的状态SSS然后对于大于s\sqrt ss的每个质数ppp那么答案就是
∑T⊆S(2gT×∑p(1−12fp,T))(−1)∣T∣\sum_{T\sube S}\left(2^{g_T}\times \sum_{p}\left(1-\frac{1}{2^{f_{p,T}}}\right)\right)(-1)^{|T|}T⊆S∑(2gT×p∑(1−2fp,T1))(−1)∣T∣
然后求和就可以了 code
#includecstdio
#includecstring
#includealgorithm
#includevector
#includecctype
#define ll long long
using namespace std;
const ll N2100,M1e610,L14,P998244353;
ll n,m,cnt,pri[320],pw[M],iw[M],ct[1L];
ll w[N],f[1L][320],g[1L],q[N*10],v[N];
vectorll r;bool usd[N];
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-f;cgetchar();}while(isdigit(c)){x(x1)(x3)c-48;cgetchar();}return x*f;
}
void Prime(){for(ll i2;iN;i){if(!v[i])pri[cnt]i,cnt,v[i]cnt-1;for(ll j0;jcnti*pri[j]N;j){v[i*pri[j]]1;if(i%pri[j]0)break;}}return;
}
signed main()
{Prime();nread();pw[0]iw[0]1;for(ll i1;in;i)pw[i]pw[i-1]*2ll%P;for(ll i1;in;i)iw[i]iw[i-1]*(P1)/2ll%P;for(ll i1,x;in;i)xread(),w[x];ll MS(1L);for(ll s1;sMS;s)ct[s]ct[s-(s-s)]1;for(ll s0;sMS;s){r.clear();memset(usd,0,sizeof(usd));for(ll i0;iL;i)if((si)1){for(ll jpri[i];j2000;jpri[i])usd[j]1;}for(ll i1;i2000;i)if(!usd[i])g[s]w[i],r.push_back(i);g[s]pw[g[s]];for(ll iL;icnt;i){f[s][i]0;for(ll j0;r[j]*pri[i]2000;j)f[s][i]w[r[j]*pri[i]];ll kf[s][i];f[s][i]iw[k]*(pw[k]-1)%P;}}mread();while(m--){ll kread();ll t0,tot0,ans0;for(ll i1,x;ik;i){xread();if(v[x]L)t|1v[x];else q[tot]v[x];}sort(q1,q1tot);totunique(q1,q1tot)-q-1;for(ll st;s0;s(s-1)t){ll k(ct[s]1)?(P-g[s]):g[s];for(ll i1;itot;i)kk*f[s][q[i]]%P;(ansk)%P;if(!s)break;}printf(%lld\n,(ansP)%P);}return 0;
}
