首页 > 其他分享 >P10171题解

P10171题解

时间:2024-02-18 09:22:22浏览次数:28  
标签:ch int 题解 2024 多项式 P10171

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

相关文章

  • CF1472C Long Jumps题解
    【题目分析】本题有两个方法,方法一:每一个位置可得的分分别求出,打擂找出最大(可得部分分)方法二:从后往前求可得的分数,以避免一些不必要的重复。【设计程序】方法一:#include<bits/stdc++.h>#include<iostream>#include<stdio.h>#include<cstdio>#include<queue>usingnames......
  • CF1196B Odd Sum Segments题解
    【问题分析】本题考了奇数。由此想到以下定律:奇数+偶数=奇数;奇数+奇数=偶数;偶数+偶数=偶数;所以偶数可以忽略不计,只有奇数可以对结果产生影响,所以我们只要注意奇数即可。经过思考可得奇数的个数至少为$k$个且比$k$多的个数为偶数,此时多出的奇数可组成偶数,对结果不产生......
  • P2036 [COCI2008-2009#2] PERKET题解
    【问题分析】分析题目可得此问题为01背包问题因此题数据较小所以可用枚举每一样物品选或不选的方法来写【设计程序】#include<bits/stdc++.h>#include<iostream>#include<stdio.h>#include<cstdio>#include<queue>usingnamespacestd;constintN=10+5;struct......
  • P1162 填涂颜色题解
    【问题分析】分析题目可得此问题为连通块问题因此题枚举被包围的‘0’较难所以可用枚举每一个不被包围的‘0’【设计程序】#include<bits/stdc++.h>#include<iostream>#include<stdio.h>#include<cstdio>#include<queue>usingnamespacestd;constintN=30+5;i......
  • P2249 【深基13.例1】查找题解
    【问题分析】本题有n个数(n>10^6)n很大,查找m个数(m≤10^5),数最大为(10^9)方法一:用顺序查找的话时间复杂度为:O(n*m)会超时,只能得部分分;方法二:用桶排时间复杂度为O(n)+O(m),但是因为数最大为(109)空间复杂度为:O(109);方法三:用二分查找,时间复杂度为:O(m*logn),空间复杂度为O(n)。综合以......
  • P8248 简单数列 题解
    首先,圈重点:$1\len\le500$所有元素在$1\sim4$之间任意连续的连续子串不相同只要输出一种答案即可于是我们可以得到的是:由第一点和第二点可以看出此题可以写搜索解决。由第三点我们可以得到一种剪枝方式,就是如果目前数字放入后会产生相同的连续的连续子串。由第四点......
  • P1380 T型骨牌 题解
    本题每个位置有$5$种可能,据题中$n,m$均小于五,所以可以用搜索直接过。上代码#include<cstdio>usingnamespacestd;boolmp[15][15];intn,m,ans;intdt[4][5][2]={{{-1,-1},{0,-1},{1,-1},{0,0},{0,1}},{{-1,0},{0,0},{1,-1},{1,0},{1,1}},{{0,......
  • P1686 挑战 题解
    本题就是要找到最短的捷径。注意事项:捷径必须是直线。要求捷径最短而非总路程最短。捷径不与原有的路重合既然在同一直线上,则该捷径的起点与终点的横坐标或纵坐标相等。要把横坐标或纵坐标相同的聚在一起只需要排个序即可。捷径最短的话(以横坐标相等举例),只需要以$x$为第......
  • P1541 [NOIP2010 提高组] 乌龟棋题解
    有两种方法,代码注释都很详细了直接上代码一:记忆化搜索#include<bits/stdc++.h>usingnamespacestd;intt[15];intn,m;inta[400];intmp[45][45][45][45];//mp[i][j][k][l]表示1号用i张,2号用j张,3号用k张,4号用l张的情况下,最多能拿多少分intdfs(intstep,intw)//step......
  • TopCoder SRM478C RandomApple 题解
    题意:有\(k\)种苹果和\(n\)个箱子,每个箱子中有一些苹果,先等概率选取\(n\)个箱子组成集合的非空子集,再从选出的苹果中随机选一个,问每种苹果被选中的概率是多少箱子\(i\)有\(a_{i,j}\)个第\(j\)种苹果,第\(i\)个箱子的总苹果数\(siz_i=\sum\limits_{j=1}^ka_{i,j}\),苹果总数\(sum=\su......