題目鏈接：點擊打開鏈接

思路：

該題暴力當然可以過， ? 如果數據量加大， ?我們還有一種nlogn的算法：FFT

仔細觀察這個復習單詞量的累加方式可以發現， 這是一個卷積， 可以用FFT加速算法。

細節參見代碼：

#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <string> #include <vector> #include <stack> #include <ctime> #include <bitset> #include <cstdlib> #include <cmath> #include <set> #include <list> #include <deque> #include <map> #include <queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; typedef long double ld; const double eps = 1e-6; const double PI = acos(-1); const int mod = 1000000000 + 7; const int INF = 0x3f3f3f3f; // & 0x7FFFFFFF const int seed = 131; const ll INF64 = ll(1e18); const int maxn = 4000 + 10; int T,n,m,b[maxn], a[maxn]; struct Complex {double x, y; // 實部和虛部 x + yiComplex(double _x = 0.0, double _y = 0.0) {x = _x;y = _y;}Complex operator +(const Complex &b) const {return Complex(x + b.x, y + b.y);}Complex operator -(const Complex &b) const {return Complex(x - b.x, y - b.y);}Complex operator *(const Complex &b) const {return Complex(x*b.x-y*b.y, x*b.y+y*b.x);} }; void change(Complex y[], int len) {int i, j, k;for(i = 1, j = len/2; i < len-1; i++) {if(i < j) swap(y[i], y[j]);k = len/2;while(j >= k) { j -= k; k /= 2; }if(j < k) j += k;} } void fft(Complex y[], int len, int on) {change(y, len);for(int h = 2; h <= len; h <<= 1) {Complex wn(cos(-on*2*PI/h), sin(-on*2*PI/h));for(int j = 0; j < len; j += h) {Complex w(1, 0);for(int k = j; k < j + h/2; k++) {Complex u = y[k];Complex t = w*y[k+h/2];y[k] = u + t;y[k+h/2] = u - t;w = w * wn;}}}if(on == -1) {for(int i = 0; i < len; i++) y[i].x /= len;} } Complex x1[maxn], x2[maxn], ans[maxn]; int main() {scanf("%d",&T);while(T--) {scanf("%d", &n);for(int i = 0; i < n; i++) scanf("%d", &a[i]);scanf("%d", &m);int len1 = n, len2 = 0, len = 1;for(int i = 0; i < m; i++) scanf("%d", &b[i]), len2 = max(len2, b[i]);while(len < len1 * 2 || len < len2 * 2) len <<= 1;for(int i = 0; i < len2; i++) x2[i] = Complex(0, 0);for(int i = 0; i < n; i++) x1[i] = Complex(a[i], 0);for(int i = 0; i < m; i++) x2[b[i]-1] = Complex(1, 0);for(int i = len1; i < len; i++) x1[i] = Complex(0, 0);for(int i = len2; i < len; i++) x2[i] = Complex(0, 0);fft(x1, len, 1);fft(x2, len, 1);for(int i = 0; i < len; i++) ans[i] = x1[i] * x2[i];fft(ans, len, -1);for(int i = 0; i < n; i++) ans[i].x += a[i];len = len1 + len2 - 1;int q; scanf("%d", &q);while(q--) {int id;scanf("%d", &id);if(id > len) printf("0\n");else printf("%d\n", (int)round(ans[id-1].x));}}return 0; }

總結

以上是生活随笔為你收集整理的BNUOJ 27935 我爱背单词（FFT）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。