【BNU】40719 Arithmetic Progressions【分块+FFT】

2024-09-05 14:18

本文主要是介绍【BNU】40719 Arithmetic Progressions【分块+FFT】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

传送门:【BNU】40719 Arithmetic Progressions

题目分析:

用分块+FFT强行AC了这题……
之前一直TLE……然后改了好久把姿势改的优美点了……终于过了……

大概思路是:我们考虑分块,假设每一块的大小为S,一共分了B块然后我们分两种情况讨论:
1.第二个数在第i块,第一个数在(1~i-1)块内,第三个数在(i+1~B)块内。
2.至少两个数在同一块内。

对于第一种情况,我们可以用 FFT 实现,每块的复杂度为 O(MlogM) M 为数的大小,这题大概M=216

对于第二种情况,我们可以 O((NS)2) 的复杂度内实现。

具体实现就不多说了,知道大体该往哪个方向思考就好了。

总复杂度: O(SMlogM+N2S)

我写的常数大的不行啊= =不知道正解到底是怎么样,反正比较无脑的就是这样暴力……

my  code:

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std ;typedef long long LL ;#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )const int MAXN = 100005 ;
const int SQR = 330 ;
const double pi = acos ( -1.0 ) ;struct Complex {double r , i ;Complex ( double r = 0 , double i = 0 ) : r ( r ) , i ( i ) {}Complex operator + ( const Complex& t ) const {return Complex ( r + t.r , i + t.i ) ;}Complex operator - ( const Complex& t ) const {return Complex ( r - t.r , i - t.i ) ;}Complex operator * ( const Complex& t ) const {return Complex ( r * t.r - i * t.i , r * t.i + i * t.r ) ;}
} ;int n ;
Complex x1[MAXN << 2] ;
Complex x2[MAXN << 2] ;
int cnt[MAXN] ;
int a[MAXN] ;
int in[MAXN] , L[MAXN] ;void FFT ( Complex y[] , int n , int rev ) {for ( int i = 1 , j , k , t ; i < n ; ++ i ) {for ( j = 0 , k = n >> 1 , t = i ; k ; k >>= 1 , t >>= 1 ) {j = j << 1 | t & 1 ;}if ( i < j ) swap ( y[i] , y[j] ) ;}for ( int s = 2 , ds = 1 , k , i ; s <= n ; ds = s , s <<= 1 ) {Complex wn ( cos ( rev * 2 * pi / s ) , sin ( rev * 2 * pi / s ) ) , t , w ;for ( k = 0 , w = 1 ; k < ds ; ++ k , w = w * wn ) {for ( i = k ; i < n ; i += s ) {y[i + ds] = y[i] - ( t = w * y[i + ds] ) ;y[i] = y[i] + t ;}}}if ( rev < 0 ) {for ( int i = 0 ; i < n ; ++ i ) {y[i].r /= n ;}}
}void solve () {LL ans = 0 ;int N = 1 << 16 ;int sqr = n / 50 + 1 ;clr ( cnt , 0 ) ;clr ( L , 0 ) ;clr ( in , 0 ) ;for ( int i = 0 ; i < n ; ++ i ) {scanf ( "%d" , &a[i] ) ;++ cnt[a[i]] ;}for ( int l = 0 ; l < n ; l += sqr ) {int r = min ( n , l + sqr ) ;for ( int i = l ; i < r ; ++ i ) {++ in[a[i]] ;}for ( int i = 0 ; i < N ; ++ i ) {x1[i] = Complex ( L[i] , 0 ) ;}for ( int i = 0 ; i < N ; ++ i ) {x2[i] = Complex ( cnt[i] - in[i] - L[i] , 0 ) ;}FFT ( x1 , N , 1 ) ;FFT ( x2 , N , 1 ) ;for ( int i = 0 ; i < N ; ++ i ) {x1[i] = x1[i] * x2[i] ;}FFT ( x1 , N , -1 ) ;for ( int i = l ; i < r ; ++ i ) {if ( a[i] * 2 < N ) ans += ( LL ) ( x1[a[i] << 1].r + 0.5 ) ;}for ( int i = l ; i < r ; ++ i ) {-- in[a[i]] ;}for ( int i = l ; i < r ; ++ i ) {for ( int j = l ; j <= i ; ++ j ) {++ in[a[j]] ;}for ( int j = i + 1 ; j < r ; ++ j ) {in[a[j]] ++ ;int x = a[i] * 2 - a[j] ;int y = a[j] * 2 - a[i] ;if ( x >= 0 ) ans += L[x] ;if ( y >= 0 ) ans += cnt[y] - in[y] - L[y] ;}for ( int j = l ; j < r ; ++ j ) {-- in[a[j]] ;}}for ( int i = l ; i < r ; ++ i ) {++ L[a[i]] ;}}printf ( "%lld\n" , ans ) ;
}int main () {while ( ~scanf ( "%d" , &n ) ) solve () ;return 0 ;
}

这篇关于【BNU】40719 Arithmetic Progressions【分块+FFT】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1139196

相关文章

【数字信号处理】一文讲清FFT(快速傅里叶变换)

目录 快速傅里叶变换(Fast Fourier Transform,FFT)FFT的背景快速傅里叶变换(Fast Fourier Transform,FFT)DFT的数学表达实际计算重要性和应用频谱泄露、频谱混叠奈奎斯特采样定理参考链接 快速傅里叶变换(Fast Fourier Transform,FFT) FFT的背景 1、为什么要时域→频域频率?50Hz+频率120Hz

Spring Boot实现大文件分块上传

1.分块上传使用场景 大文件加速上传:当文件大小超过100MB时,使用分片上传可实现并行上传多个Part以加快上传速度。 网络环境较差:网络环境较差时,建议使用分片上传。当出现上传失败的时候,您仅需重传失败的Part。 文件大小不确定: 可以在需要上传的文件大小还不确定的情况下开始上传,这种场景在视频监控等行业应用中比较常见。 2.实现原理 实现原理其实很简单,核心就是客户端把大文件

【HDU】5197 DZY Loves Orzing 【FFT启发式合并】

传送门:【HDU】5197 DZY Loves Orzing 题目分析: 首先申明,我不会 dp dp方程= =……这个东西给队友找出来了,然后我就是套这个方程做题的Qrz…… 对于这题,因为 n2 n^2个数互不相同,所以每一列都可以单独考虑。设 dpni dp_ni表示长度为 n n的排列,能恰好看见ii个人的方案数,根据队友的发现, dpni dp_ni就等于 |sni| |s_ni|

【ZOJ】3874 Permutation Graph 【FFT+CDQ分治】

传送门:【ZOJ】3874 Permutation Graph 题目分析: 容易知道一个个连通块内部的标号都是连续的,否则一定会有另一个连通块向这个连通块建边,或者这个连通块向另一个连通块建边。而且从左到右左边的连通块内最大的标号小于右边连通块内最小的标号。 然后我们可以构造dp方程: dp[n]=n!−i!∗dp[n−i] \qquad \qquad dp[n] = n! - i! *

【SPOJ】Triple Sums【FFT】

传送门:【SPOJ】Triple Sums 题目分析: 首先我们不考虑 i<j<k i<j<k这个条件,构造多项式: Y=∑xai \qquad\qquad\qquad Y = \sum x^{a_i} 那么 ai+aj+ak=S ai+aj+ak=S的个数即 xai+aj+ak=S x^{a_i+a_j+a_k=S}的个数,等价于 Y3中xS Y^3中x^S的系数。 然后我们考虑容斥

【BNU】33943 Super Rooks on Chessboard 【FFT】

【BNU】33943 Super Rooks on Chessboard UVA上的题,然而我怎么会蠢到去UVA呢!(其实是百度首先跳出来的是BNU → \to_ → \to) 题目分析: 设 numx numx为 N N个车没有覆盖的行数,numynumy为 N N个车没有覆盖的列数。 首先我们考虑没有主对角线覆盖这一条件时,总共的没有被覆盖的面积就是numx∗numynumx \ast

【HDU】4609 3-idiots 【FFT】

传送门:【HDU】4609 3-idiots 题目分析: 我们考虑两边长度之和为 n n的方案数,设num[x]num[x]为长度为 x x的个数,那么∑nx=1num[n−x]∗num[x]\sum_{x=1}^{n}{num[n-x]*num[x]} 即两边长度之和为 n n的方案数。容易发现这这正是卷积!然后我们就可以愉快的用FFTFFT预处理出所有的两边长度之和为i的方案数。 FFT

【HDU】5213 Lucky 【分块(在线算法)】

传送门:【HDU】5213 Lucky 题目分析: 我来说一下这题的在线做法。 首先我们将区间分成 n√ \sqrt n块,用f[x][y]表示第x块的数和第y块的数相加等于K的对数,这个可以 O(nn√) O(n \sqrt n)的预处理。然后还有g[x][y]表示在第1~x块中有的大小为y的数的个数,这个的复杂度同样 O(nn√) O(n \sqrt n)。 接下来,对于每组询问,我们

【codechef】 Prime Distance On Tree【求树上路经长度为i的路径条数】【点分治+FFT】

传送门:【codechef】 Prime Distance On Tree 点分治+FFT水题……竟然n*n爆int没发现…… 而且NTT TLE,FFT跑的超级快…… my  code: my~~code: #include <bits/stdc++.h>using namespace std ;typedef long long LL ;#define clr( a , x ) m

【51nod】算法马拉松4 F 移数字 【快速求N!%P】【FFT】

传送门:【51nod】算法马拉松4 F 移数字 涉及知识点:多项式求逆,多项式除法,多点插值,阶乘取模。 对于N!%P,复杂度为 O(N−−√log2N−−√) O(\sqrt N \log^2\sqrt N)。 但常数巨大,和暴力算实际复杂度只相差常数= = 这个是可以扩展到组合数取模的~ my  code: my~~code: #include <stdio.h>#includ