题解 P2714 【四元组统计】

command_block · 2020-03-28 12:10:15 · 题解

题意 : 给出n个数a_{1...n},统计有多少个四元组满足gcd(a_i,a_j,a_k,a_l)=1

多组数据,T\leq 100,n,a_i\leq 10^4

类似的问题 : 给出若干个[0,2^n)内的数,对m=[0,2^n)求选取k元组and起来为m的方案数.

开个桶记录出现次数,设为F[n].

先跑高维前缀和,然后F[n]就变成了“是n的超集的个数”

我们令F[n]=\dbinom{F[n]}{k},即“且起来是是n的超集的k元组个数”

然后跑高维差分,即可得到“且起来是是n的k元组个数”。

这道题告诉我们,对于按位取\min/\max的运算,其转移是个DAG,这类变换除了线性性之外往往还有其他优秀性质。

回到本题,其实gcd就是质因数向量上的\min.

先做一个约数前缀和,然后就变为了点值,每个点值变成\dbinom{num}{4},然后跑一个约数差分即可。

这样甚至能得到\gcd为每个数的答案,我们最后只需取出F[1]即可。

容易发现,改成k元组同样能做。

复杂度可以用P5495 Dirichlet 前缀和做到O(Tn\log\log n)

代码很好写 :

#include<algorithm>
#include<cstdio>
#define MaxN 20050000
#define ll long long
using namespace std;
inline int read(){
  register int X=0;
  register char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
ll F[MaxN];
int p[MaxN/12],tn;
void solve()
{
  int m,n=1;
  if (scanf("%d",&m)==EOF)exit(0);
  for(int i=1,t;i<=m;i++){
    F[t=read()]++;
    n=max(n,t);
  }
  for(int i=1;p[i]<=n;i++)
    for(int j=n/p[i];j;j--)
      F[j]+=F[j*p[i]];
  for(int i=1;i<=n;i++)F[i]=(F[i]-3)*(F[i]-2)*(F[i]-1)*F[i]/24;
  for(int i=1;p[i]<=n;i++)
    for(int j=1;j*p[i]<=n;j++)
      F[j]-=F[j*p[i]];
  printf("%lld\n",F[1]);
  for(int i=1;i<=n;i++)F[i]=0;
}
bool e[MaxN];
int main()
{
  for(int i=2;i*i<=10000;i++)
    if (!e[i])
      for (int j=i*i;j<=10000;j+=i)
        e[j]=1;
  for(int i=2;i<=10000;i++)
    if (!e[i])p[++tn]=i;
  p[++tn]=10001;
  while(1)solve();
  return 0;
}

似乎利用\mu函数非零值较少写暴力也可以跑得很快……

题解 P2714 【四元组统计 】

题解 P2714 【四元组统计】