fork download
  1. #ifndef SET_POWER_SERIES
  2. #define SET_POWER_SERIES
  3.  
  4. // The class SubsetFunction<T> represents a function on the subsets of
  5. // {0, 1, ..., N-1} with values in T. A subset is represented by its bitmask.
  6. // The following operations are supported:
  7. // xor_convolution
  8. // and_convolution
  9. // or_convolution
  10. // subset_convolution
  11. // complement
  12. // exp
  13. // log
  14. //
  15. // Only the high-level API (that is SubsetFunction) shall be used.
  16. // With respect to copy and assignment, the class SubsetFunction behaves like
  17. // a vector.
  18. //
  19. // Internally, all operations are implemented directly on arrays (and, whenever
  20. // possible, in place). There are no memory leaks.
  21. // Operating directly on arrays simplifies the implementation (since often one
  22. // has to treat a subarray as an array and with vectors this is not possible).
  23.  
  24. // TODO: Maybe use some global arrays as temporary memory for subset_convolution and
  25. // inverse_subset_convolution (to avoid many allocations).
  26.  
  27. // TODO: Remove iostream.
  28.  
  29. // TODO: Remove main() and test.
  30. // TODO: Add comments.
  31.  
  32. #include <iostream>
  33.  
  34. #include <vector>
  35. #include <cassert>
  36. #include <cstring>
  37. #include <algorithm>
  38. using namespace std;
  39.  
  40. // All functions in internal operate on pointers and are, therefore, a bit
  41. // uncomfortable to use for the end-user.
  42. // It is much better to use the fancier APIs offered by the class SubsetFunction.
  43. namespace internal {
  44.  
  45. template<typename T>
  46. void clear(int N, T* A) { fill(A, A+(1<<N), 0); }
  47.  
  48. // In place xor-transform. See xor_convolution to understand its importance.
  49. // A'[x] = TODO.
  50. // Complexity: O(N*2^N).
  51. template<typename T>
  52. void xor_transform(int N, T* A, bool inverse = false) {
  53. for (int len = 1; 2 * len <= (1<<N); len *= 2) {
  54. for (int x = 0; x < (1<<N); x += 2 * len) {
  55. for (int y = 0; y < len; y++) {
  56. T u = A[x + y];
  57. T v = A[x + y + len];
  58. A[x + y] = u + v;
  59. A[x + y + len] = u - v;
  60. }
  61. }
  62. }
  63. if (inverse) for (int i = 0; i < (1<<N); i++) A[i] /= (1<<N);
  64. }
  65.  
  66. // In place and-transform. See and_convolution to understand its importance.
  67. // A'[x] = \sum_{x\subseteq y} A[y].
  68. // Complexity: O(N*2^N).
  69. template<typename T>
  70. void and_transform(int N, T* A, bool inverse = false) {
  71. for (int len = 1; 2 * len <= (1<<N); len *= 2) {
  72. for (int x = 0; x < (1<<N); x += 2 * len) {
  73. for (int y = 0; y < len; y++) {
  74. if (inverse) A[x+y] -= A[x+y+len];
  75. else A[x+y] += A[x+y+len];
  76. }
  77. }
  78. }
  79. }
  80.  
  81. // In place or-transform. See or_convolution to understand its importance.
  82. // A'[x] = \sum_{y\subseteq x} A[y].
  83. // Complexity: O(N*2^N).
  84. template<typename T>
  85. void or_transform(int N, T* A, bool inverse = false) {
  86. for (int len = 1; 2 * len <= (1<<N); len *= 2) {
  87. for (int x = 0; x < (1<<N); x += 2 * len) {
  88. for (int y = 0; y < len; y++) {
  89. if (inverse) A[x+y+len] -= A[x+y];
  90. else A[x+y+len] += A[x+y];
  91. }
  92. }
  93. }
  94. }
  95.  
  96. // C[x] = \sum_{y&z = 0, y|z = x} A[y]*B[z].
  97. // Complexity: O(N²*2^N).
  98. template<typename T>
  99. void subset_convolution(int N, const T* A, const T* B, T* C) {
  100. T** A_popcnt = new T*[N+1];
  101. T** B_popcnt = new T*[N+1];
  102. T* tmp = new T[1<<N];
  103. for (int i = 0; i <= N; i++) {
  104. A_popcnt[i] = new T[1<<N];
  105. B_popcnt[i] = new T[1<<N];
  106. clear(N, A_popcnt[i]);
  107. clear(N, B_popcnt[i]);
  108. }
  109. for (int x = 0; x < (1<<N); x++) {
  110. int q = __builtin_popcount(x);
  111. A_popcnt[q][x] = A[x];
  112. B_popcnt[q][x] = B[x];
  113. }
  114. for (int i = 0; i <= N; i++) {
  115. or_transform(N, A_popcnt[i]);
  116. or_transform(N, B_popcnt[i]);
  117. }
  118. for (int l = 0; l <= N; l++) {
  119. clear(N, tmp);
  120. for (int i = 0; i <= l; i++) {
  121. int j = l-i;
  122. for (int x = 0; x < (1<<N); x++)
  123. tmp[x] += A_popcnt[i][x]*B_popcnt[j][x];
  124. }
  125. or_transform(N, tmp, true);
  126. for (int x = 0; x < (1<<N); x++)
  127. if (__builtin_popcount(x) == l) C[x] = tmp[x];
  128. }
  129. for (int i = 0; i <= N; i++) {
  130. delete[] A_popcnt[i];
  131. delete[] B_popcnt[i];
  132. }
  133. delete[] A_popcnt;
  134. delete[] B_popcnt;
  135. delete[] tmp;
  136. }
  137.  
  138. // B = exp(A).
  139. //
  140. // For x != 0, it holds
  141. // B[x] = \sum_{0 < y_1 < y_2 < ... < y_k: y_i disjoint, y_1|y_2|...|y_k = x}
  142. // A[y_1]*A[y_2]*...*A[y_k].
  143. // The value B[0] is (arbitrarily) set to 1.
  144. //
  145. // The value of A[0] is disregarded.
  146. template<typename T>
  147. void exp(int N, const T* A, T* B) {
  148. B[0] = 1;
  149. for (int n = 0; n < N; n++)
  150. subset_convolution(n, A + (1<<n), B, B + (1<<n));
  151. }
  152.  
  153. // subset_convolution(A, C) = B.
  154. //
  155. // ACHTUNG: The value A[0] must be invertible.
  156. template<typename T>
  157. void inverse_subset_convolution(int N, const T* A, const T* B, T* C) {
  158. T inv = 1/A[0];
  159.  
  160. T** A_popcnt = new T*[N+1];
  161. T** C_popcnt = new T*[N+1];
  162. for (int i = 0; i <= N; i++) {
  163. A_popcnt[i] = new T[1<<N];
  164. C_popcnt[i] = new T[1<<N];
  165. clear(N, A_popcnt[i]);
  166. clear(N, C_popcnt[i]);
  167. }
  168. for (int x = 0; x < (1<<N); x++) {
  169. int q = __builtin_popcount(x);
  170. A_popcnt[q][x] = A[x];
  171. }
  172. for (int i = 0; i <= N; i++) or_transform(N, A_popcnt[i]);
  173.  
  174. for (int l = 0; l <= N; l++) {
  175. for (int i = 0; i <= l; i++) {
  176. int j = l-i;
  177. for (int x = 0; x < (1<<N); x++)
  178. C_popcnt[l][x] += A_popcnt[i][x]*C_popcnt[j][x];
  179. }
  180. or_transform(N, C_popcnt[l], true);
  181. for (int x = 0; x < (1<<N); x++) {
  182. int q = __builtin_popcount(x);
  183. if (q != l) C_popcnt[l][x] = 0;
  184. else {
  185. C_popcnt[l][x] = (B[x] - C_popcnt[l][x])*inv;
  186. C[x] = C_popcnt[l][x];
  187. }
  188. }
  189. or_transform(N, C_popcnt[l]);
  190. }
  191.  
  192. for (int i = 0; i <= N; i++) {
  193. delete[] A_popcnt[i];
  194. delete[] C_popcnt[i];
  195. }
  196. delete[] A_popcnt;
  197. delete[] C_popcnt;
  198. }
  199.  
  200. // exp(B) = A.
  201. // The value of B[0] is (arbitrarily) set to 0.
  202. //
  203. // ACHTUNG: It must hold A[0] = 1.
  204. template<typename T>
  205. void log(int N, const T* A, T* B) {
  206. assert(A[0] == 1);
  207. B[0] = 0;
  208. for (int n = 0; n < N; n++)
  209. inverse_subset_convolution(n, A, A+(1<<n), B+(1<<n));
  210. }
  211.  
  212. // A'[x] = A[complement of x]
  213. template<typename T>
  214. void complement(int N, T* A) {
  215. int pot = 1<<(N-1);
  216. for (int x = 0; x < pot; x++) swap(A[x], A[x|pot]);
  217. }
  218.  
  219.  
  220. // C[x] = \sum_{y^z = x} A[y]B[z]
  221. // Complexity: O(N2^N).
  222. template<typename T>
  223. void xor_convolution(int N, const T* A, const T* B, T* C) {
  224. T* B2 = new T[1<<N];
  225. for (int x = 0; x < (1<<N); x++) C[x] = A[x], B2[x] = B[x];
  226. walsh_hadamard_transform(N, C);
  227. walsh_hadamard_transform(N, B2);
  228. for (int x = 0; x < (1<<N); x++) C[x] *= B2[x];
  229. walsh_hadamard_transform(N, C, true);
  230. delete[] B2;
  231. }
  232.  
  233. // C[x] = \sum_{y&z = x} A[y]B[z]
  234. // Complexity: O(N2^N).
  235. template<typename T>
  236. void and_convolution(int N, const T* A, const T* B, T* C) {
  237. T* B2 = new T[1<<N];
  238. for (int x = 0; x < (1<<N); x++) C[x] = A[x], B2[x] = B[x];
  239. and_transform(N, C);
  240. and_transform(N, B2);
  241. for (int x = 0; x < (1<<N); x++) C[x] *= B2[x];
  242. and_transform(N, C, true);
  243. delete[] B2;
  244. }
  245.  
  246. // C[x] = \sum_{y|z = x} A[y]B[z]
  247. // Complexity: O(N2^N).
  248. template<typename T>
  249. void or_convolution(int N, const T* A, const T* B, T* C) {
  250. T* B2 = new T[1<<N];
  251. for (int x = 0; x < (1<<N); x++) C[x] = A[x], B2[x] = B[x];
  252. or_transform(N, C);
  253. or_transform(N, B2);
  254. for (int x = 0; x < (1<<N); x++) C[x] *= B2[x];
  255. or_transform(N, C, true);
  256. delete[] B2;
  257. }
  258.  
  259. }; // namespace internal
  260.  
  261. template<typename T>
  262. struct SubsetFunction {
  263. int N;
  264. T* arr;
  265. SubsetFunction(int N): N(N) {
  266. arr = new T[1<<N];
  267. clear();
  268. }
  269. ~SubsetFunction() { delete[] arr; }
  270. SubsetFunction(const SubsetFunction& other) {
  271. N = other.N;
  272. arr = new T[1<<N];
  273. for (int x = 0; x < (1<<N); x++) arr[x] = other[x];
  274. }
  275. SubsetFunction& operator=(const SubsetFunction& other) {
  276. if (this != &other) {
  277. if (N != other.N) {
  278. N = other.N;
  279. delete[] arr;
  280. arr = new T[1<<N];
  281. }
  282. for (int x = 0; x < (1<<N); x++) arr[x] = other[x];
  283. }
  284. return *this;
  285. }
  286. T& operator[](int index) { return arr[index]; }
  287. const T& operator[](int index) const { return arr[index]; }
  288. void clear() { internal::clear(N, arr); }
  289. };
  290.  
  291. #define CONVOLUTION_DEF(OP) \
  292. template<typename T> \
  293. SubsetFunction<T> OP##_convolution(const SubsetFunction<T>& A, \
  294.   const SubsetFunction<T>& B) { \
  295.   assert(A.N == B.N); \
  296.   SubsetFunction<T> C(A.N); \
  297.   internal::OP##_convolution(A.N, A.arr, B.arr, C.arr); \
  298.   return C; \
  299. }
  300.  
  301. CONVOLUTION_DEF(xor) // Complexity O(N2^N).
  302. CONVOLUTION_DEF(and) // Complexity O(N2^N).
  303. CONVOLUTION_DEF(or) // Complexity O(N2^N).
  304. CONVOLUTION_DEF(subset) // Complexity O(N²2^N).
  305. CONVOLUTION_DEF(inverse_subset) // Complexity O(N²2^N).
  306.  
  307. #define UNARY_OPERATOR_DEF(OP) \
  308. template<typename T> \
  309. SubsetFunction<T> OP(const SubsetFunction<T>& A) { \
  310.   SubsetFunction<T> B(A.N); \
  311.   internal::OP(A.N, A.arr, B.arr); \
  312.   return B; \
  313. }
  314.  
  315. UNARY_OPERATOR_DEF(complement) // Complexity O(N).
  316. UNARY_OPERATOR_DEF(exp) // Complexity O(N²2^N).
  317. UNARY_OPERATOR_DEF(log) // Complexity O(N2^N).
  318.  
  319. // #include "../arithmetic_lib.cpp"
  320. typedef unsigned long long int ULL;
  321. typedef long long int LL;
  322.  
  323.  
  324. // Computes the inverse of n modulo m.
  325. // Precondition: n >= 0, m > 0 and gcd(n, m) == 1.
  326. // The returned value satisfies 0 <= x < m (Inverse(0, 1) = 0).
  327. // ACHTUNG: It must hold max(m, n) < 2**31 to avoid integer overflow.
  328. LL Inverse(LL n, LL m) {
  329. n %= m;
  330. if (n <= 1) return n; // Handles properly (n = 0, m = 1).
  331. return m - ((m * Inverse(m, n) - 1) / n);
  332. }
  333.  
  334. // Fast exponentiation modulo mod. Returns x**e modulo mod.
  335. // Assumptions: 0 <= x < mod
  336. // mod < 2**31.
  337. // 0 <= e < 2**63
  338. LL pow(LL x, LL e, LL mod) {
  339. LL res = 1;
  340. for (; e >= 1; e >>= 1) {
  341. if (e & 1) res = res * x % mod;
  342. x = x * x % mod;
  343. }
  344. return res;
  345. }
  346.  
  347. // Struct that computes x % mod faster than usual, if mod is always the same.
  348. // It gives a x1.8 speed up over the % operator (with mod ~ 1e9 and x large).
  349. // It is an implementation of the Barrett reduction, see
  350. // https://e...content-available-to-author-only...a.org/wiki/Barrett_reduction .
  351. // If fast_mod is an instance of the class, then fast_mod(x) will return
  352. // x % mod. There are no restrictions on the values of mod and x, provided
  353. // that they fit in an unsigned long long (and mod != 0).
  354. //
  355. // ACHTUNG: The integer type __uint128_t must be available.
  356. struct FastMod {
  357. ULL mod;
  358. ULL inv;
  359. FastMod(ULL mod) : mod(mod), inv(-1ULL / mod) {}
  360. ULL operator()(ULL x) {
  361. ULL q = (ULL)((__uint128_t(inv) * x) >> 64);
  362. ULL r = x - q * mod;
  363. return r - mod * (r >= mod);
  364. }
  365. };
  366.  
  367. // Class for integers modulo mod.
  368. // It supports all expected operations: +, -, *, /, pow, ==, < and >.
  369. // It is as fast as it can be.
  370. // The modulo mod shall be set through set_mod().
  371. //
  372. // Assumptions: mod < (1<<30).
  373. // ACHTUNG: The integer type __uint128_t must be available.
  374. //
  375. // Remark: To handle larger moduli (up to 1<<62), one has to:
  376. // 1. replace int in the definitions of mod, n.
  377. // 2. The parameter of fast_mod must be __uint128_t, so it must be
  378. // changed in the definition of fast_mod and in the definition of
  379. // the operators * and *=.
  380. // 3. fast_mod must be a naive modulo operation, no barrett reduction.
  381. // 4. In Inverse, __int128_t shall be used.
  382. struct ModularInteger {
  383. static int mod;
  384. static __uint128_t inv_mod; // Necessary for fast_mod.
  385. int n; // 0 <= n < mod at all times
  386. static void set_mod(int _mod) {
  387. mod = _mod;
  388. inv_mod = -1ULL / mod;
  389. }
  390. ModularInteger(): n(0) {}
  391. ModularInteger(LL _n): n(_n % mod) {
  392. n += (n<0)*mod;
  393. }
  394. LL get() const { return n; }
  395. static int fast_mod(ULL x) { // Barrett reduction.
  396. ULL q = (inv_mod * x) >> 64;
  397. int m = x - q * mod;
  398. m -= mod * (m >= mod);
  399. return m;
  400. }
  401.  
  402. ModularInteger operator-() const { return n?mod-n:0; }
  403. };
  404. int ModularInteger::mod;
  405. __uint128_t ModularInteger::inv_mod;
  406.  
  407. ModularInteger operator +(const ModularInteger& A, const ModularInteger& B) {
  408. ModularInteger C;
  409. C.n = A.n + B.n;
  410. C.n -= (C.n >= ModularInteger::mod)*ModularInteger::mod;
  411. return C;
  412. }
  413.  
  414. void operator +=(ModularInteger& A, const ModularInteger& B) {
  415. A.n += B.n;
  416. A.n -= (A.n >= ModularInteger::mod)*ModularInteger::mod;
  417. }
  418.  
  419. ModularInteger operator -(const ModularInteger& A, const ModularInteger& B) {
  420. ModularInteger C;
  421. C.n = A.n - B.n;
  422. C.n += (C.n < 0)*ModularInteger::mod;
  423. return C;
  424. }
  425.  
  426. void operator -=(ModularInteger& A, const ModularInteger& B) {
  427. A.n -= B.n;
  428. A.n += (A.n < 0)*ModularInteger::mod;
  429. }
  430.  
  431. ModularInteger operator *(const ModularInteger& A, const ModularInteger& B) {
  432. ModularInteger C;
  433. C.n = ModularInteger::fast_mod(((ULL)A.n) * B.n);
  434. return C;
  435. }
  436.  
  437. void operator *=(ModularInteger& A, const ModularInteger& B) {
  438. A.n = ModularInteger::fast_mod(((ULL)A.n) * B.n);
  439. }
  440.  
  441. // Assumption: gcd(B, mod) = 1.
  442. ModularInteger operator /(const ModularInteger& A, const ModularInteger& B) {
  443. return A * Inverse(B.n, ModularInteger::mod);
  444. }
  445.  
  446. // Assumption: gcd(B, mod) = 1.
  447. void operator/=(ModularInteger& A, const ModularInteger& B) {
  448. A *= Inverse(B.n, ModularInteger::mod);
  449. }
  450.  
  451. ModularInteger power(ModularInteger A, ULL e) {
  452. ModularInteger res = 1;
  453. for (; e >= 1; e >>= 1) {
  454. if (e & 1) res *= A;
  455. A *= A;
  456. }
  457. return res;
  458. }
  459.  
  460. bool operator ==(const ModularInteger& A, const ModularInteger& B) {
  461. return A.n == B.n;
  462. }
  463. bool operator !=(const ModularInteger& A, const ModularInteger& B) {
  464. return A.n != B.n;
  465. }
  466. bool operator <(const ModularInteger& A, const ModularInteger& B) {
  467. return A.n < B.n;
  468. }
  469. bool operator >(const ModularInteger& A, const ModularInteger& B) {
  470. return A.n > B.n;
  471. }
  472. bool operator <=(const ModularInteger& A, const ModularInteger& B) {
  473. return A.n <= B.n;
  474. }
  475. bool operator >=(const ModularInteger& A, const ModularInteger& B) {
  476. return A.n >= B.n;
  477. }
  478.  
  479. ostream& operator <<(ostream& out, const ModularInteger& A) {
  480. out << A.n;
  481. return out;
  482. }
  483.  
  484. istream& operator >>(istream& in, ModularInteger& A) {
  485. LL a;
  486. in >> a;
  487. A = ModularInteger(a);
  488. return in;
  489. }
  490.  
  491. typedef ModularInteger mint;
  492.  
  493.  
  494. template<typename T>
  495. SubsetFunction<T> slow_subset_convolution(const SubsetFunction<T>& A,
  496. const SubsetFunction<T>& B) {
  497. int N = A.N;
  498. SubsetFunction<T> C(N);
  499. for (int x = 0; x < (1<<N); x++) for (int y = 0; y < (1<<N); y++) {
  500. if (x&y) continue;
  501. C[x|y] += A[x] * B[y];
  502. }
  503. return C;
  504. }
  505.  
  506.  
  507. template<typename T>
  508. SubsetFunction<T> slow_or_convolution(const SubsetFunction<T>& A,
  509. const SubsetFunction<T>& B) {
  510. int N = A.N;
  511. SubsetFunction<T> C(N);
  512. for (int x = 0; x < (1<<N); x++) for (int y = 0; y < (1<<N); y++) {
  513. C[x|y] += A[x] * B[y];
  514. }
  515. return C;
  516. }
  517.  
  518. #include<bits/stdc++.h>
  519.  
  520. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  521. inline int rnd(int l,int r)
  522. {return uniform_int_distribution<int>(l,r)(rng);}
  523.  
  524. SubsetFunction<mint> POW(SubsetFunction<mint> A,int k,const int N){
  525. SubsetFunction<mint> ans(N);
  526. ans[0]=1;
  527. while(k){
  528. if(k&1){
  529. ans=subset_convolution(ans,A);
  530. }
  531. A=subset_convolution(A,A);
  532. k/=2;
  533. }
  534. return ans;
  535. }
  536.  
  537. SubsetFunction<mint> expKlogPow(SubsetFunction<mint> A,int k,const int N){
  538. A = log(A);
  539. for (int x = 0; x < (1<<N); x++)
  540. A[x] *= k;
  541. A = exp(A);
  542. return A;
  543. }
  544.  
  545. bool checkEqual(SubsetFunction<mint> A,SubsetFunction<mint> B,const int N){
  546. for (int x = 0; x < (1<<N); x++){
  547. if(A[x]!=B[x])
  548. return false;
  549. // cerr<<A[x]<<" "<<B[x]<<endl;
  550. }
  551. return true;
  552. }
  553.  
  554. int main() {
  555. mint::set_mod(998244353);
  556.  
  557. const int N = 10, K = 100;
  558. SubsetFunction<mint> A(N);
  559. for (int x = 0; x < (1<<N); x++) {
  560. A[x] = rnd(0,1e4);
  561. }
  562. A[0]=1;
  563.  
  564. auto AKPow = POW(A,K,N);
  565. auto AexpPow = expKlogPow(A,K,N);
  566. assert(checkEqual(AKPow,AexpPow,N));
  567. cout<<"Proof BY AC"<<endl;
  568. // GENERAL TESTING
  569.  
  570. // int N = 2;
  571. // SubsetFunction<mint> A(N);
  572. // for (int x = 0; x < (1<<N); x++) A[x] = rand() % 4;
  573.  
  574. // SubsetFunction<mint> B(N);
  575. // for (int x = 0; x < (1<<N); x++) B[x] = rand() % 4;
  576.  
  577. // SubsetFunction<mint> C = subset_convolution(A, B);
  578.  
  579. // auto C2 = slow_subset_convolution(A, B);
  580.  
  581. // auto B2 = inverse_subset_convolution(A, C);
  582.  
  583. // for (int x = 0; x < (1<<N); x++) assert(C[x] == C2[x]);
  584. // for (int x = 0; x < (1<<N); x++) assert(B[x] == B2[x]);
  585.  
  586. // auto E = exp(A);
  587. // auto L = log(E);
  588. // for (int x = 1; x < (1<<N); x++) assert(L[x] == A[x]);
  589. // assert(L[0] == 0);
  590.  
  591. // auto D = or_convolution(A, B);
  592. // auto D2 = slow_or_convolution(A, B);
  593. // for (int x = 0; x < (1<<N); x++) cout << A[x] << " ";
  594. // cout << endl;
  595. // for (int x = 0; x < (1<<N); x++) cout << B[x] << " ";
  596. // cout << endl;
  597. // for (int x = 0; x < (1<<N); x++) cout << D[x] << " ";
  598. // cout << endl;
  599. // for (int x = 0; x < (1<<N); x++) cout << D2[x] << " ";
  600. // cout << endl;
  601. // for (int x = 0; x < (1<<N); x++) assert(D[x] == D2[x]);
  602.  
  603. // internal::or_transform(N, D2.arr);
  604. // internal::or_transform(N, A.arr);
  605. // internal::or_transform(N, B.arr);
  606. // cout << endl;
  607. // for (int x = 0; x < (1<<N); x++) cout << A[x] << " ";
  608. // cout << endl;
  609. // for (int x = 0; x < (1<<N); x++) cout << B[x] << " ";
  610. // cout << endl;
  611. // for (int x = 0; x < (1<<N); x++) cout << D2[x] << " ";
  612. // cout << endl;
  613.  
  614. // YOSUPO subset convolution
  615. // int N;
  616. // cin >> N;
  617. // SubsetFunction<mint> A(N), B(N);
  618. // for (int i = 0; i < (1<<N); i++) cin >> A[i];
  619. // for (int i = 0; i < (1<<N); i++) cin >> B[i];
  620. // auto C = subset_convolution(A, B);
  621. // for (int i = 0; i < (1<<N); i++) cout << C[i] << " ";
  622. // cout << "\n";
  623. }
  624.  
  625.  
  626. #endif // SET_POWER_SERIES
  627.  
  628.  
Success #stdin #stdout 0.01s 5460KB
stdin
Standard input is empty
stdout
Proof BY AC