給定N，M，K，數組a[N][M],b[N]，定義c[i]=∑j=0n?1a[j][b[ij mod N]] 求第K大的c[i]
Data Constraint
題解
原式中有乘積的形式，非常的不優美，考慮去掉乘法。 注意到所有的N都是質數，所以我們可以用原根來轉化，除了等于0的情況，都可以設i=gx,j=gy于是原式可以表示成： c[x]=∑y=1n?1a[y][b[(x+y) mod (N?1)]] 考慮枚舉某一列來計算貢獻，設當前計算第i列，那么 c[x]=∑y=1n?1a[y][i]×[b[x+y]==i] 然后翻轉一下： c[x]=∑y=1n?1a[?y][i]×[b[x+y]==i] 這就是一個標準的卷積形式了。FFT解決。
時間復雜度：O(nlogn)
SRC
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>using namespace std ;#define N 250000 + 10#define M 600000 + 10typedef long long ll ;const double pi = acos(-1) , eps = 0.5 ;struct Z { double x , y ; Z ( double X = 0 , double Y = 0 ) { x = X , y = Y ; }} A[M] , B[M] , tmp[M] , tW[M] ;int Ta1[11] = { 5 , 127 , 509 , 2039 , 8191 , 32749 , 65521 , 131071 , 249989 , 249973 , 249971 } ;int Ta2[11] = { 2 , 3 , 2 , 7 , 17 , 2 , 17 , 3 , 2 , 5 , 6 } ;ll a[N][6] , b[N] , c[N] ;int rev[M] , P[N] ;int n , m , k , G , len ;Z Operator + ( Z a , Z b ) { return Z( a.x + b.x , a.y + b.y ) ; }Z operator - ( Z a , Z b ) { return Z( a.x - b.x , a.y - b.y ) ; }Z operator * ( Z a , Z b ) { return Z( a.x * b.x - a.y * b.y , a.x * b.y + a.y * b.x ) ; }bool cmp( ll a , ll b ) { return a > b ; }int Read() { int ret = 0 ; char ch = getchar() ; while ( ch < '0' || ch > '9' ) ch = getchar() ; while ( ch >= '0' && ch <= '9' ) { ret = ret * 10 + ch - '0' ; ch = getchar() ; } return ret ;}void PRe() { for (int i = 0 ; i < 11 ; i ++ ) if ( n == Ta1[i] ) { G = Ta2[i] ; break ; } P[0] = 1 ; for (int i = 1 ; i <= n ; i ++ ) P[i] = P[i-1] * G % n ; for ( len = 1 ; len < n + n ; len *= 2 ) ; for (int i = 0 ; i < len ; i ++ ) { tW[i] = Z( cos( i * 2 * pi / len ) , sin( i * 2 * pi / len ) ) ; int tp = 0 ; for (int x = i , k = 1 ; k < len ; k <<= 1 , x >>= 1 ) tp = (tp << 1) + (x & 1) ; rev[i] = tp ; }}void DFT( Z *a , int sig ) { for (int i = 0 ; i < len ; i ++ ) tmp[rev[i]] = a[i] ; for (int m = 2 ; m <= len ; m <<= 1 ) { int half = m / 2 ; for (int i = 0 ; i < half ; i ++ ) { Z W = tW[(sig*i*(len/m)+len)%len] ; for (int j = i ; j < len ; j += m ) { Z u = tmp[j] ; Z v = tmp[j+half] * W ; tmp[j] = u + v ; tmp[j+half] = u - v ; } } } for (int i = 0 ; i < len ; i ++ ) a[i] = tmp[i] ;}void FFT( Z *A , Z *B ) { DFT( A , 1 ) , DFT( B , 1 ) ; for (int i = 0 ; i < len ; i ++ ) A[i] = A[i] * B[i] ; DFT( A , -1 ) ; for (int i = 0 ; i < len ; i ++ ) A[i].x = A[i].x / len ;}int main() { freopen( "b.in" , "r" , stdin ) ; freopen( "b.out" , "w" , stdout ) ; n = Read() , m = Read() , k = Read() ; for (int j = 0 ; j < m ; j ++ ) { for (int i = 0 ; i < n ; i ++ ) { a[i][j] = Read() ; } } for (int i = 0 ; i < n ; i ++ ) b[i] = Read() ; Pre() ; for (int i = 0 ; i < m ; i ++ ) { for (int j = 0 ; j < len ; j ++ ) A[j] = B[j] = Z( 0 , 0 ) ; for (int j = 0 ; j < n - 1 ; j ++ ) { A[n-1-j] = Z( a[P[j]][i] , 0 ) ; B[j] = b[P[j]] == i ? Z( 1 , 0 ) : Z( 0 , 0 ) ; } FFT( A , B ) ; for (int j = 0 ; j < len ; j ++ ) c[P[j%(n-1)]] += (int)(A[j].x + eps) ; } for (int i = 1 ; i < n ; i ++ ) c[0] += a[i][b[0]] ; for (int i = 0 ; i < n ; i ++ ) c[i] += a[0][b[0]] ; sort( c , c + n , cmp ) ; printf( "%lld/n" , c[k-1] ) ; return 0 ;}
