\[\text{NOIP模拟赛-2023.11.14} \]
T1 简单的题
给三个数 \(n,G,L\)，要求从 \(1\dots n\) 中选出一个非空子集使 \(\gcd=G\)，\(\operatorname{lcm}=L\)。问方案数。同时有若干询问，给定 \(a_i\)，求在包含 \(a_i\) 的前提下的方案数。
\(n,G,L\leq 10^8\)，\(Q\leq 5000\)
把 \(L\) 所有因数，\(G\) 所有倍数取出来，记为 \(a_1,\dots,a_n\)，\(n\) 的规模 \(\leq 800\)。把它们写作 \(Gd_1,Gd_2,\dots,Gd_n\) 的形式，现在变成从 \(d\) 里面选数，记选出的为 \(x_1,x_2\dots,x_m\)，则 \(\gcd(x_1,\dots ,x_m)=1\)，\(\operatorname{lcm}(x_1,\dots,x_m)=\dfrac{L}{G}\)。分解质因数变成每一位因数的指数 \(\max\) 要与 \(L\) 该位相等，指数的 \(\min\) 为 \(0\)。发现 \(\dfrac{L}{G}\) 最多 \(8\) 个质因数，可以状压
设 \(f_{i,s,t}\) 表示前 \(i\) 位的数的指数 \(\max\) 满足了 \(s\) 集合，指数 \(\min\) 满足了 \(t\) 集合的方案数。枚举 \(i\) 的贡献，则 \(f_{i,s,t}\rightarrow f_{i+1,s',t'}\)。同时 \(i\) 可以不选，\(f_{i,s,t}\rightarrow f_{i+1,s,t}\)。答案即 \(f_{n,S,T}\)
但是现在还要求必须选某个数 \(a_i\)。然后不会了……我的想法是，对于每个询问 \(a_i\)，将 \(i-1\) 和 \(i+1\) 的 \(f_{,s,t}\) 记录下来，枚举超集计算贡献（不会高维前缀和），然后合并，时间复杂度 \(\mathcal{O}(800\times 3^{16})\)，无法通过。后来想要是一个数 \(x\) 它没有任何一位的指数取到 \(0\)，也没有取到 \(\max\)，那它在转移的时候转移系数就是 \(0\)，所以它的答案应该是 \(\dfrac{f_{n,S,T}}{2}\)。估计不满足这样条件的数应该不会很多，所以其它的暴力做感觉能通过 。
UPD：获得 \(80\) 分，正解就是高维前缀和，时间复杂度 \(\mathcal{O}(8\times 2^{16} \times 800)\)
code
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define LL long long
using namespace std;
bool Mbe;
const int N=800,QQ=5010,SS=(1<<8)+10;
const int MOD=998244853;
int n,G,L,des,Q,S,q[QQ],ans[N];
int a[N],d[N],m;
int p[N][10],cnt,legal[N][2];
int f[N][SS][SS],g[N][SS][SS];
map <int,int> desp;
bool isque[N];
void prework()
{
for(int i=1; i*i<=L; i++)
{
if(L%i==0)
{
if(i%G==0 && i<=n)
a[++m]=i;
if(i*i!=L && (L/i)%G==0 && L/i<=n)
a[++m]=L/i;
}
}
sort(a+1,a+1+m);
for(int i=1; i<=m; i++)
d[i]=a[i]/G;
}
void divide(int x,int i)
{
for(int j=2; j*j<=x; j++)
{
if(x%j==0)
{
if(i==0)
desp[j]=++cnt;
int id=desp[j];
while(x%j==0)
p[i][id]++,x/=j;
}
}
if(x>1)
{
if(i==0)
desp[x]=++cnt;
p[i][desp[x]]++;
}
}
void work(int i)
{
for(int j=1; j<=cnt; j++)
{
if(p[i][j]==p[0][j])
legal[i][0]^=(1<<j-1);
if(p[i][j]==0)
legal[i][1]^=(1<<j-1);
}
}
void SOS_DP()
{
for(int i=1; i<=cnt; i++)
for(int s=0; s<=S; s++)
if(!(s&(1<<i-1)))
for(int t=0; t<=S; t++)
for(int j=1; j<=m; j++)
(g[j][s][t]+=g[j][s|(1<<i-1)][t])%=MOD;
for(int i=1; i<=cnt; i++)
for(int t=0; t<=S; t++)
if(!(t&(1<<i-1)))
for(int s=0; s<=S; s++)
for(int j=1; j<=m; j++)
(g[j][s][t]+=g[j][s][t|(1<<i-1)])%=MOD;
}
int solve(int i)
{
int res=0;
for(int s=0; s<=S; s++)
{
for(int t=0; t<=S; t++)
{
int ss=s|legal[i][0],tt=t|legal[i][1];
(res+=1LL*f[i-1][s][t]*g[i+1][S^ss][S^tt]%MOD)%=MOD;
}
}
return res;
}
bool Med;
int main()
{
freopen("easy.in","r",stdin);
freopen("easy.out","w",stdout);
// fprintf(stderr, "%.3lfMB\n",(&Mbe-&Med)/1048576.000);
scanf("%d%d%d%d",&n,&G,&L,&Q);
for(int i=1; i<=Q; i++)
scanf("%d",&q[i]);
if(L%G!=0)
{
for(int i=0; i<=Q; i++)
puts("0");
return 0;
}
prework();
divide(des=L/G,0);
for(int i=1; i<=m; i++)
{
divide(d[i],i);
work(i);
}
for(int i=1; i<=Q; i++)
{
int cur=lower_bound(a+1,a+1+m,q[i])-a;
if(a[cur]!=q[i])
continue;
isque[cur]=1;
}
f[0][0][0]=1; S=(1<<cnt)-1;
for(int i=0; i<m; i++)
{
for(int s=0; s<=S; s++)
{
for(int t=0; t<=S; t++)
{
(f[i+1][s|legal[i+1][0]][t|legal[i+1][1]]+=f[i][s][t])%=MOD;
(f[i+1][s][t]+=f[i][s][t])%=MOD;
}
}
}
g[m+1][0][0]=1;
for(int i=m+1; i>1; i--)
{
for(int s=0; s<=S; s++)
{
for(int t=0; t<=S; t++)
{
(g[i-1][s|legal[i-1][0]][t|legal[i-1][1]]+=g[i][s][t])%=MOD;
(g[i-1][s][t]+=g[i][s][t])%=MOD;
}
}
}
SOS_DP();
for(int i=1; i<=m; i++)
{
if(!isque[i])
continue;
ans[i]=solve(i);
}
printf("%d\n",f[m][S][S]);
for(int i=1; i<=Q; i++)
{
int cur=lower_bound(a+1,a+1+m,q[i])-a;
if(a[cur]!=q[i])
puts("0");
else
printf("%d\n",ans[cur]);
}
return 0;
}