P10171 [DTCPC 2024] 取模
题解
不会多项式导致的,赛后秒过。
一个显然的结论:如果原序列有相等的数答案为 \(0\),其次大于 \(4\times 10^5\) 的 \(k\) 均符合要求。问题在于小于 \(4\times 10^5\) 的答案。
赛时想了很多奇妙的算法,诸如根号分治、线段树维护余数等等。其实不用这么麻烦,考虑两个数在模 \(k\) 意义下相等,等价于这两个数的差是 \(k\) 的倍数,而本题值域较小,如果我们求出了两两之间的差,可以用 \(\sum\lfloor\dfrac{V}{i}\rfloor\approx V\log V\) 的复杂度完成本题。
问题在于求差,因为值域较小,可以将 \(a\) 序列转化成一个长为 \(V\) 的多项式,每一项系数为 \(0/1\),然后答案即为 \(ans_k=\sum\limits_{i-j=k}a_ia_j\),将多项式反转后与原多项式做多项式卷积即可。
代码:
/*
* @Author: operator_
* @Date: 2024-02-18 08:36:29
* @Last Modified by: operator_
* @Last Modified time: 2024-02-18 09:17:33
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int rd() {
int s=0,m=0;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
#define cp complex<double>
const double pi=acos(-1);
int rv[4000005];
void init(int k) {
for(int i=0;i<(1<<k);i++)
rv[i]=(rv[i>>1]>>1)|((i&1)<<(k-1));
}
void fft(cp a[],int n,int fl) {
for(int i=0;i<n;i++)
if(i<rv[i]) swap(a[i],a[rv[i]]);
for(int i=1;i<n;i*=2) {
cp wi=exp(cp(0,fl*pi/i));
for(int j=0;j<n;j+=i*2) {
cp w(1,0);
for(int k=j;k<i+j;k++,w*=wi) {
cp x=a[k],y=w*a[k+i];
a[k]=x+y,a[k+i]=x-y;
}
}
}
if(fl==-1) for(int i=0;i<n;i++) a[i]/=n;
}
const int N=400000;
int n,l,r,x[50005],mp[400005],ans[4000005],sum;
cp a[4000005],b[4000005];
signed main() {
cin>>n>>l>>r;
for(int i=1;i<=n;i++) mp[x[i]=rd()]++;
for(int i=1;i<=N;i++)
if(mp[i]>1) return puts("0"),0;
for(int i=1;i<=N;i++) if(mp[i])
a[i-1]=1,b[N-i]=1;
int k=0,m=1;while(m<=N*2) k++,m*=2;
init(k);fft(a,m,1);fft(b,m,1);
for(int i=0;i<m;i++) a[i]=a[i]*b[i];
fft(a,m,-1);
for(int i=1;i<=N;i++) ans[i]=(int)(a[i+N-1].real()+0.5);
sum=max(0ll,r-N);
for(int i=l;i<=min(r,N);i++) {
int fl=1;
for(int j=0;i*j<=N;j++)
if(ans[i*j]) {fl=0;break;}
if(fl) sum++;
}
cout<<sum;
return 0;
}
第一次发数学题解,如有错误欢迎指正!
标签:ch,int,题解,2024,多项式,P10171 From: https://www.cnblogs.com/operator-/p/18018771