首页 > 代码库 > 2016 Multi-University Training Contest 1 H.Shell Necklace
2016 Multi-University Training Contest 1 H.Shell Necklace
Shell Necklace
Time Limit: 16000/8000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 534 Accepted Submission(s): 227
Problem Description
Perhaps the sea‘s definition of a shell is the pearl. However, in my view, a shell necklace with n beautiful shells contains the most sincere feeling for my best lover Arrietty, but even that is not enough.
Suppose the shell necklace is a sequence of shells (not a chain end to end). Considering i continuous shells in the shell necklace, I know that there exist different schemes to decorate the i shells together with one declaration of love.
I want to decorate all the shells with some declarations of love and decorate each shell just one time. As a problem, I want to know the total number of schemes.
Suppose the shell necklace is a sequence of shells (not a chain end to end). Considering i continuous shells in the shell necklace, I know that there exist different schemes to decorate the i shells together with one declaration of love.
I want to decorate all the shells with some declarations of love and decorate each shell just one time. As a problem, I want to know the total number of schemes.
Input
There are multiple test cases(no more than 20 cases and no more than 1 in extreme case), ended by 0.
For each test cases, the first line contains an integer n, meaning the number of shells in this shell necklace, where 1≤n≤105. Following line is a sequence with nnon-negative integer a1,a2,…,an, and ai≤107 meaning the number of schemes to decorate i continuous shells together with a declaration of love.
For each test cases, the first line contains an integer n, meaning the number of shells in this shell necklace, where 1≤n≤105. Following line is a sequence with nnon-negative integer a1,a2,…,an, and ai≤107 meaning the number of schemes to decorate i continuous shells together with a declaration of love.
Output
For each test case, print one line containing the total number of schemes module 313(Three hundred and thirteen implies the march 13th, a special and purposeful day).
Sample Input
31 3 742 2 2 2 0
Sample Output
1454
For the first test case in Sample Input, the Figure 1 provides all schemes about it. The total number of schemes is 1 + 3 + 3 + 7 = 14.
Hint
For the first test case in Sample Input, the Figure 1 provides all schemes about it. The total number of schemes is 1 + 3 + 3 + 7 = 14.
Author
HIT
题意： 一串由n颗珍珠组成的项链，连续的i个珍珠有ci种染色方式。 问n颗珍珠有多少种染色方式？
题解： 显然可知dp方程 f[i] = sigma(f[i - j] * a[j]) 由于n很大，可以考虑分治fft解决。 说说这个分治fft： 如果我们需要计算出l～r的f的值。 假设我们已经计算出（l，mid）的f的值 观察方程 f[i] = sigma(f[j] * a[i - j]) 1 <= j < i = sigma(f[j] * a[i - j]) + sigma(f[k] * a[i - k]) 1<= j <= mid, mid < k < i 所以可以分开计算f[l~mid]对f[mid+1~r]的影响。 具体过程可以看代码。 使用时记得调整一下下标。
1 class Complex { 2 public : 3 double real, image; 4 5 Complex(double real = 0., double image = 0.):real(real), image(image) {} 6 Complex(const Complex &t):real(t.real), image(t.image) {} 7 8 Complex operator +(const Complex &t) const { 9 return Complex(real + t.real, image + t.image); 10 } 11 12 Complex operator -(const Complex &t) const { 13 return Complex(real - t.real, image - t.image); 14 } 15 16 Complex operator *(const Complex &t) const { 17 return Complex(real * t.real - image * t.image, 18 real * t.image + t.real * image); 19 } 20 }; 21 22 const int N = 300010, MOD = 313; 23 const double PI = acos(-1.); 24 25 class FFT { 26 /** 27 * 1. Need define PI 28 * 2. Need define class Complex 29 * 3. tmp is need for fft, so define a N suffice it 30 * 4. dig[30] -> (1 << 30) must bigger than N 31 * */ 32 private : 33 static Complex tmp[N]; 34 static int revNum[N], dig[30]; 35 36 public : 37 static void init(int n) { 38 int len = 0; 39 for(int t = n - 1; t; t >>= 1) ++len; 40 for(int i = 0; i < n; i++) { 41 revNum[i] = 0; 42 for(int j = 0; j < len; j++) dig[j] = 0; 43 for(int idx = 0, t = i; t; t >>= 1) dig[idx++] = t & 1; 44 for(int j = 0; j < len; j++) 45 revNum[i] = (revNum[i] << 1) | dig[j]; 46 } 47 } 48 49 static int rev(int x) { 50 return revNum[x]; 51 } 52 53 static void fft(Complex a[], int n, int flag) { 54 /** 55 * flag = 1 -> DFT 56 * flag = -1 -> IDFT 57 * */ 58 for(int i = 0; i < n; ++i) tmp[i] = a[rev(i)]; 59 for(int i = 0; i < n; ++i) a[i] = tmp[i]; 60 for(int i = 2; i <= n; i <<= 1) { 61 Complex wn(cos(2 * PI / i), flag * sin(2 * PI / i)); 62 for(int k = 0, half = i / 2; k < n; k += i) { 63 Complex w(1., 0.); 64 for(int j = k; j < k + half; ++j) { 65 Complex x = a[j], y = w * a[j + half]; 66 a[j] = x + y, a[j + half] = x - y; 67 w = w * wn; 68 } 69 } 70 } 71 if(flag == -1) { 72 for(int i = 0; i < n; ++i) a[i].real /= n; 73 } 74 } 75 76 static void dft(Complex a[], int n) { 77 fft(a, n, 1); 78 } 79 80 static void idft(Complex a[], int n) { 81 fft(a, n, -1); 82 } 83 }; 84 Complex FFT::tmp[N]; 85 int FFT::revNum[N], FFT::dig[30]; 86 87 int n, arr[N]; 88 int f[N]; 89 Complex A[N], B[N]; 90 91 inline void divideAndConquer(int lef, int rig) { 92 if(lef >= rig) return; 93 int mid = (lef + rig) >> 1; 94 divideAndConquer(lef, mid); 95 96 int m; 97 for(m = 1; m < (rig - lef + 1) * 2; m <<= 1); 98 for(int i = 0; i < m; ++i) A[i] = B[i] = Complex(); 99 for(int i = lef; i <= mid; ++i) A[i - lef] = Complex(f[i]);100 int len = min(n, m - 1);101 for(int i = 0; i < len; ++i) B[i + 1] = Complex(arr[i]);102 FFT::init(m);103 FFT::dft(A, m), FFT::dft(B, m);104 for(int i = 0; i < m; ++i) A[i] = A[i] * B[i];105 FFT::idft(A, m);106 107 for(int i = mid + 1; i <= rig; ++i)108 f[i] = (f[i] + ((ll)(A[i - lef].real + 0.5))) % MOD;109 110 divideAndConquer(mid + 1, rig);111 }112 113 inline void solve() {114 for(int i = 0; i < n; ++i) arr[i] %= MOD;115 for(int i = 0; i <= n; ++i) f[i] = 0;116 f[0] = 1;117 divideAndConquer(0, n);118 119 printf("%d\n", f[n]);120 }121 122 int main() {123 while(scanf("%d", &n) == 1 && n) {124 for(int i = 0; i < n; ++i) scanf("%d", &arr[i]);125 solve();126 }127 return 0;128 }
2016 Multi-University Training Contest 1 H.Shell Necklace
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。