ZeroJudge h386 - Apples and Bananas 解題心得( 題目 )
解題概念:FFT(Fast Fourier Transform)
**這題本來是CSES題目，但是因為時限很緊，除C、C++之外的大部分語言都會被卡常，還好ZJ上有放寬時限的版本。
解題方法:這題如果硬做，是O(N^2)，顯然不好，那我們可以試著把它換成多項式的題目嗎?
如果我們把令ax^b代表b重量的水果有a個，那我們把蘋果和香蕉分開做，得到兩個多項式，你會發現乘起來的結果，次方x的係數y其實就是代表總和重量x的組合有y個!
然而，把它當成多項式來做時間複雜度並沒有變好，還是O(N^2)......。
這裡就換FFT派上用場了(建議不會的讀者可以試著學看看，連結，先備知識:虛/複數平面、多項式基本常識)，利用FFT可在O(NlogN)的時間內得到兩個多項式的乘積，藉此這題可以降到O(NlogN)。
Java參考程式碼(有更好意見可留言於下方，謝謝!):
//Author:En Chi Tsung(欉恩祁)
//Date:2022/03/15
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class zjh386 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static int ret,rd;
public static long floor;
public static final int N=1<<19,P=19;
public static Complex[] w=new Complex[N];
public static void main(String[] args) throws Exception{
final int k=readint();
final int n=readint();
final int m=readint();
int[] apple=new int[N];
int[] banana=new int[N];
Complex[] a=new Complex[N];
Complex[] b=new Complex[N];
Complex[] c=new Complex[N];
double d;
final double e=(2*Math.PI/N);
for(int i=0;i<n;i++) {
apple[readint()]++;
}
for(int i=0;i<m;i++) {
banana[readint()]++;
}
for(int i=0;i<N;i++) {
a[i]=new Complex(apple[i],0);
b[i]=new Complex(banana[i],0);
d=e*i;
w[i]=new Complex(Math.cos(d),Math.sin(d));
}
FFT(a);
FFT(b);
for(int i=0;i<N;i++) {
c[i]=multiply(a[i],b[i]);
d=-e*i;
w[i]=new Complex(Math.cos(d),Math.sin(d));
}
FFT(c);
for(int i=2;i<=(k<<1);i++) {
bw.write(round(c[i].r/N)+" ");
}
bw.write("\n");
bw.flush();
}
public static void FFT(Complex[] in) {
Complex o;
int u,y;
for(int i=0;i<N;i++) {
u=0;
for(int j=0;j<P;j++) {
y=(1<<j);
if((y&i)==y) {
u|=(1<<(P-1-j));
}
}
if(i<u) {
o=in[i];//swap
in[i]=in[u];
in[u]=o;
}
}
for(int i=1;i<N;i<<=1) {
for(int j=0;j<N;j+=(i<<1)) {
for(int k=j;k<i+j;k++) {
o=multiply(in[i+k],w[(int)((long)(k-j)*N/i>>1)]);
in[i+k]=minus(in[k],o);
in[k]=plus(in[k],o);
}
}
}
}
public static Complex plus(Complex a,Complex b) {
return new Complex(a.r+b.r,a.i+b.i);
}
public static Complex minus(Complex a,Complex b) {
return new Complex(a.r-b.r,a.i-b.i);
}
public static Complex multiply(Complex a,Complex b) {
return new Complex(a.r*b.r-a.i*b.i,a.i*b.r+a.r*b.i);
}
public static long round(double x) {
floor=(long)x;
if(x-floor>0.5) {
return floor+1;
}
return floor;
}
public static int readint() throws Exception{
ret=0;
rd=br.read();
while(rd>47&&rd<58) {
ret*=10;
ret+=(rd&15);
rd=br.read();
}
return ret;
}
}
class Complex{
double r,i;
Complex(double real,double imag){
r=real;
i=imag;
}
}
文章標籤
全站熱搜
