fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define pii pair<int, int>
  6. #define all(c) ((c).begin()), ((c).end())
  7. #define sz(x) ((int)(x).size())
  8.  
  9. #ifdef LOCAL
  10. #include <print.h>
  11. #else
  12. #define trace(...)
  13. #endif
  14.  
  15. #include <atcoder/convolution>
  16. using namespace atcoder;
  17. using mint = modint998244353;
  18. using poly = vector<mint>;
  19.  
  20. poly operator + (const poly & A, const poly & B){
  21.     int n = max(A.size(), B.size());
  22.     poly ret(n);
  23.     for(int i = 0; i < n; i++){
  24.         ret[i] = (i < (int)A.size() ? A[i]  : 0) + (i < (int)B.size() ? B[i] : 0);
  25.     }
  26.     return ret;
  27. }
  28.  
  29. poly operator * (const poly & A, const poly & B){
  30.     return convolution(A, B);
  31. }
  32.  
  33. poly inverse(const poly & A, int s){
  34.     assert(A[0] != mint(0));
  35.     poly X = {1 / A[0]};
  36.     while((int)X.size() < s){
  37.         poly temp(A.begin(), A.begin() + min(A.size(), 2 * X.size()));
  38.         poly nx = X * X * temp;
  39.         X.resize(2 * X.size());
  40.         for(int i = 0; i < X.size(); i++){
  41.             X[i] = 2 * X[i] - nx[i];
  42.         }
  43.     }
  44.     X.resize(s);
  45.     return X;
  46. }
  47.  
  48. int main(){
  49. 	ios_base::sync_with_stdio(false); 
  50. 	cin.tie(NULL); // Remove in interactive problems
  51. 	int n; cin >> n;
  52. 	vector<int> A(n), B(n), C(n);
  53. 	for(int i = 0; i < n; i++) cin >> A[i];
  54. 	for(int i = 0; i < n; i++) cin >> B[i];
  55. 	for(int i = 0; i < n; i++) cin >> C[i];
  56.  
  57. 	function<pair<poly, poly>(int, int)> getT = [&](int L, int R){
  58. 		if(L == R){
  59. 			return make_pair(poly({C[L]}), poly({1, -A[L]}));
  60. 		}
  61. 		int mid = (L + R) >> 1;
  62. 		pair<poly, poly> P = getT(L, mid), Q = getT(mid + 1, R);
  63. 		return make_pair(P.first * Q.second + Q.first * P.second, P.second * Q.second);
  64. 	};
  65. 	vector<mint> ans(n);
  66. 	function<poly(poly, int, int)> recurse = [&](poly T, int L, int R){
  67. 		if(L == R){
  68. 			ans[L] = T[0] * B[L] + T[1];
  69. 			return poly({B[L], 1});
  70. 		}
  71. 		int mid = (L + R) >> 1;
  72. 		int OFFSET = mid - L + 2;
  73. 		poly X(T.begin(), T.begin() + OFFSET);
  74. 		poly temp = recurse(X, L, mid);
  75. 		poly P(OFFSET + 1);
  76. 		for(int i = 0; i < OFFSET; i++) P[OFFSET - i] = temp[i];
  77. 		T = T * P;
  78. 		poly Q(T.begin() + OFFSET, T.begin() + OFFSET + R - mid + 1);
  79. 		return recurse(Q, mid + 1, R) * temp;
  80. 	};
  81.  
  82. 	pair<poly, poly> X = getT(0, n - 1);
  83. 	poly T = X.first * inverse(X.second, n + 1);
  84. 	T.resize(n + 1);
  85. 	recurse(T, 0, n - 1);
  86. 	for(int i = 0; i < n; i++){
  87. 		cout << ans[i].val() << " ";
  88. 	}
  89. 	cout << endl;
  90.  
  91. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:15:10: fatal error: atcoder/convolution: No such file or directory
 #include <atcoder/convolution>
          ^~~~~~~~~~~~~~~~~~~~~
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/rLXwy2
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!