无限手套 分治 + NTT + 生成函数

2023-10-27 14:30
文章标签 函数 生成 无限 分治 手套 ntt

本文主要是介绍无限手套 分治 + NTT + 生成函数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

无限手套

在这里插入图片描述

solution

∏ k = 0 ∞ a i x i 2 + b i x i + 1 \prod\limits_{k=0}^{∞}a_ix_i^2+b_ix_i+1 k=0∏∞​ai​xi2​+bi​xi​+1
考 虑 生 成 函 数 ： 考虑生成函数： 考虑生成函数：
= > ∑ k = 0 ∞ a i k 2 x k + b i x i x k + x k =>\sum\limits_{k=0}^{∞}a_ik^2x^k+b_ix_ix^k+x^k =>k=0∑∞​ai​k2xk+bi​xi​xk+xk = ∑ k = 0 ∞ a i k 2 x k + ∑ k = 0 ∞ b i x i x k + ∑ k = 0 ∞ x k , ( 三 项 分 别 当 作 A , B , C ) =\sum\limits_{k=0}^{∞}a_ik^2x^k+\sum\limits_{k=0}^{∞}b_ix_ix^k+\sum\limits_{k=0}^{∞}x^k,(三项分别当作A,B,C) =k=0∑∞​ai​k2xk+k=0∑∞​bi​xi​xk+k=0∑∞​xk,(三项分别当作A,B,C)
C = ∑ k = 0 ∞ x k = 1 1 − x C=\sum\limits_{k=0}^{∞}x^k=\frac{1}{1-x} C=k=0∑∞​xk=1−x1​

B = ∑ k = 0 ∞ b i x i x k B=\sum\limits_{k=0}^{∞}b_ix_ix^k B=k=0∑∞​bi​xi​xk
x B = ∑ k = 1 ∞ b i x i x k + 1 ， 两 式 联 立 解 得 ： xB=\sum\limits_{k=1}^{∞}b_ix_ix^{k+1}，两式联立解得： xB=k=1∑∞​bi​xi​xk+1，两式联立解得：
B = b i x ( 1 − x ) 2 B=\frac{b_ix}{(1-x)^2} B=(1−x)2bi​x​

A = ∑ k = 0 ∞ a i k 2 x k A=\sum\limits_{k=0}^{∞}a_ik^2x^k A=k=0∑∞​ai​k2xk
C = ∑ k = 0 ∞ x k = 1 1 − x C=\sum\limits_{k=0}^{∞}x^k=\frac{1}{1-x} C=k=0∑∞​xk=1−x1​
C ′ = ∑ k = 0 ∞ k x k − 1 = 1 ( 1 − x ) 2 C'=\sum\limits_{k=0}^{∞}kx^{k-1}=\frac{1}{(1-x)^2} C′=k=0∑∞​kxk−1=(1−x)21​
x C ′ = ∑ k = 0 ∞ k x k = x ( 1 − x ) 2 xC'=\sum\limits_{k=0}^{∞}kx^{k}=\frac{x}{(1-x)^2} xC′=k=0∑∞​kxk=(1−x)2x​
( x C ′ ) ′ = ∑ k = 0 ∞ k 2 x k − 1 = ( x + 1 ) ( 1 − x ) 3 (xC')'=\sum\limits_{k=0}^{∞}k^2x^{k-1}=\frac{(x+1)}{(1-x)^3} (xC′)′=k=0∑∞​k2xk−1=(1−x)3(x+1)​
x ( x C ′ ) ′ = ∑ k = 0 ∞ k 2 x k = x ( x + 1 ) ( 1 − x ) 3 x(xC')'=\sum\limits_{k=0}^{∞}k^2x^{k}=\frac{x(x+1)}{(1-x)^3} x(xC′)′=k=0∑∞​k2xk=(1−x)3x(x+1)​
A = a i ∗ x ( x C ′ ) ′ = a i x ( x + 1 ) ( 1 − x ) 3 A=a_i*x(xC')'=\frac{a_ix(x+1)}{(1-x)^3} A=ai​∗x(xC′)′=(1−x)3ai​x(x+1)​

因 此 ， 因此， 因此，

∑ k = 0 ∞ a i k 2 x k + b i x i x k + x k \sum\limits_{k=0}^{∞}a_ik^2x^k+b_ix_ix^k+x^k k=0∑∞​ai​k2xk+bi​xi​xk+xk = a i x ( x + 1 ) ( 1 − x ) 3 + b i x ( 1 − x ) 2 + 1 1 − x =\frac{a_ix(x+1)}{(1-x)^3}+\frac{b_ix}{(1-x)^2}+\frac{1}{1-x} =(1−x)3ai​x(x+1)​+(1−x)2bi​x​+1−x1​ = a i x ( x + 1 ) + ( 1 − x ) b i x + ( 1 − x ) 2 ( 1 − x ) 3 =\frac{a_ix(x+1)+(1-x)b_ix+(1-x)^2}{(1-x)^3} =(1−x)3ai​x(x+1)+(1−x)bi​x+(1−x)2​ = 1 + ( a i + b i − 2 ) x + ( a i − b i + 1 ) x 2 ( 1 − x ) 3 =\frac{1+(a_i+b_i-2)x+(a_i-b_i+1)x^2}{(1-x)^3} =(1−x)31+(ai​+bi​−2)x+(ai​−bi​+1)x2​

A n s w e r = ∏ i = 1 m 1 + ( a i + b i − 2 ) x + ( a i − b i + 1 ) x 2 ( 1 − x ) 3 Answer=\prod\limits_{i=1}^{m} \frac{1+(a_i+b_i-2)x+(a_i-b_i+1)x^2}{(1-x)^3} Answer=i=1∏m​(1−x)31+(ai​+bi​−2)x+(ai​−bi​+1)x2​ = ∏ i = 1 m 1 + ( a i + b i − 2 ) x + ( a i − b i + 1 ) x 2 ( 1 − x ) 3 m = \frac{\prod\limits_{i=1}^{m}1+(a_i+b_i-2)x+(a_i-b_i+1)x^2}{(1-x)^{3m}} =(1−x)3mi=1∏m​1+(ai​+bi​−2)x+(ai​−bi​+1)x2​

1 ( 1 − x ) n = ∑ i = 0 ∞ C n + i − 1 i x i \frac1{(1-x)^{n}}=\sum\limits_{i=0}^{∞}C_{n+i-1}^{i}{x^{i}} (1−x)n1​=i=0∑∞​Cn+i−1i​xi

A n s w e r = ∏ i = 1 m ( 1 + ( a i + b i − 2 ) x + ( a i − b i + 1 ) x 2 ) ∗ ∑ i = 0 ∞ C 3 m + i − 1 i x i Answer=\prod\limits_{i=1}^{m}(1+(a_i+b_i-2)x+(a_i-b_i+1)x^2)*\sum\limits_{i=0}^{∞}C_{3m+i-1}^{i}{x^{i}} Answer=i=1∏m​(1+(ai​+bi​−2)x+(ai​−bi​+1)x2)∗i=0∑∞​C3m+i−1i​xi

由于这个式子的复杂度会达到 O ( m n l o g n < 2 e 8 ) , m < 1 e 3 , n < 1 e 4 , l o g n < 20 O(mnlogn<2e8),m<1e3,n<1e4,logn<20 O(mnlogn<2e8),m<1e3,n<1e4,logn<20,因此需要运用分治。

code

/*SiberianSquirrel*//*CuteKiloFish*/
#include <bits/stdc++.h>
using namespace std;
#define gcd(a,b) __gcd(a,b)
#define Polynomial vector<ll>
#define Inv(x) quick_pow(x, mod - 2)
#define DEBUG(x, y) cout << x << ": " << y << '\n';
using ld = long double;
using ll = long long;
using ull = unsigned long long;
const ll mod = 998244353, mod_g = 3, img = 86583718;
//const ll mod = 1004535809, mod_g = 3;
const int N = int(1e5 + 10);
template<typename T> inline T read() {T x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }return x * f;
}
template<typename T> inline T print(T x) {if(x < 0) { putchar('-'); x =- x; }if(x > 9) print(x / 10);putchar(x % 10 + '0');
}void print(Polynomial &a, int len){for(int i = 0; i < len; ++ i)cout << a[i] << ' ';cout << '\n';
}
void exgcd(int a,int b,int &x,int &y){if(!b) {x = 1; y = 0;return;}exgcd(b, a % b, y, x);y -= x * (a / b);
}
int quick_pow(int ans, int p, int res = 1) {for(; p; p >>= 1, ans = 1ll * ans * ans % mod)if(p & 1) res = 1ll * res * ans % mod;return res % mod;
}Polynomial R;
//二进制向上取整，为方便NTT变换准备。
inline int Binary_Rounding(const int &n) {int len = 1; while(len < n) len <<= 1;return len;
}
//预处理R数组，准备变换，在每次NTT之前理论都要调用此函数。
inline int Prepare_Transformation(int n){int L = 0, len;for(len = 1; len < n; len <<= 1) L++;R.clear(); R.resize(len);for(int i = 0; i < len; ++ i)R[i] = (R[i>>1]>>1)|((i&1)<<(L-1));return len;
}
void NTT(Polynomial &a, int f){int n = a.size();for(int i = 0; i < n; ++ i)if(i < R[i])swap(a[i], a[R[i]]);for(int i = 1; i < n; i <<= 1)for(int j = 0, gn = quick_pow(mod_g,(mod - 1) / (i<<1)); j < n; j += (i<<1))for(int k = 0, g = 1, x, y; k < i; ++ k, g = 1ll * g * gn % mod)x = a[j + k], y = 1ll * g * a[i + j + k] % mod,a[j + k] = (x + y) % mod, a[i + j + k] = (x - y + mod) % mod;if(f == -1){reverse(a.begin() + 1, a.end());int inv = Inv(n);for(int i = 0; i < n; ++ i) a[i] = 1ll * a[i] * inv % mod;}
}inline Polynomial operator +(const Polynomial &a, const int &b){int sizea = a.size(); Polynomial ret = a; ret.resize(sizea);for(int i = 0; i < sizea; ++ i)ret[i] = (1ll * a[i] + b + mod) % mod;return ret;
}
inline Polynomial operator -(const Polynomial &a, const int &b){int sizea = a.size(); Polynomial ret = a; ret.resize(sizea);for(int i = 0; i < sizea; ++ i)ret[i] = (1ll * a[i] - b + mod) % mod;return ret;
}
inline Polynomial operator *(const Polynomial &a, const int &b){int sizea = a.size(); Polynomial ret = a; ret.resize(sizea);for(int i = 0; i < sizea; ++ i) ret[i] = (1ll * a[i] * b % mod + mod) % mod;return ret;
}
inline Polynomial operator +(const Polynomial &a, const Polynomial &b){int sizea = a.size(), sizeb = b.size(), size = max(sizea, sizeb);Polynomial ret = a; ret.resize(size);for(int i = 0; i < sizeb; ++ i) ret[i] = (1ll * ret[i] + b[i]) % mod;return ret;
}
inline Polynomial operator -(const Polynomial &a, const Polynomial &b){int sizea = a.size(), sizeb = b.size(), size = max(sizea, sizeb);Polynomial ret = a; ret.resize(size);for(int i = 0; i < sizeb; ++ i) ret[i] = (1ll * ret[i] - b[i] + mod) % mod;return ret;
}
inline Polynomial Inverse(const Polynomial &a){Polynomial ret, inv_a;ret.resize(1);ret[0] = Inv(a[0]); int ed = a.size();for(int len = 2; len <= ed; len <<= 1){int n = Prepare_Transformation(len << 1);inv_a = a; inv_a.resize(n); ret.resize(n);for(int i = len; i < n; ++ i) inv_a[i] = 0;NTT(inv_a, 1); NTT(ret, 1);for(int i = 0; i < n; ++ i)ret[i] = 1ll * (2ll - 1ll * inv_a[i] * ret[i] % mod + mod) % mod * ret[i] % mod;NTT(ret, -1);for(int i = len; i < n; ++ i) ret[i] = 0;}ret.resize(ed);return ret;
}
inline Polynomial operator *(const Polynomial &a, const Polynomial &b){Polynomial lsa = a, lsb = b, ret;int n = lsa.size(), m = lsb.size();n = Prepare_Transformation(n + m);lsa.resize(n); lsb.resize(n); ret.resize(n);NTT(lsa,1); NTT(lsb,1);for(int i = 0; i < n; ++ i) ret[i] = 1ll * lsa[i] * lsb[i] % mod;NTT(ret,-1);return ret;
}
inline Polynomial operator /(const Polynomial &a, const Polynomial &b){Polynomial ret = a, ls = b;reverse(ret.begin(), ret.end());reverse(ls.begin(), ls.end());ls.resize(Binary_Rounding(a.size() + b.size()));ls = Inverse(ls);ls.resize(a.size() + b.size());ret = ret * ls; ret.resize(a.size() - b.size() + 1);reverse(ret.begin(), ret.end());return ret;
}
inline Polynomial operator %(const Polynomial &a, const Polynomial &b){Polynomial ret = a / b;ret = ret * b; ret.resize(a.size() + b.size());ret = a - ret; ret.resize(a.size() + b.size());return ret;
}
inline Polynomial Derivation(const Polynomial &a){int size = a.size(); Polynomial ret; ret.resize(size);for(int i = 1; i < size; ++ i) ret[i - 1] = 1ll * i * a[i] % mod;ret[size - 1] = 0;return ret;
}
inline Polynomial Integral(const Polynomial &a){int size = a.size(); Polynomial ret; ret.resize(size);for(int i = 1; i < size; ++ i) ret[i] = 1ll * Inv(i) * a[i - 1] % mod;ret[0] = 0;return ret;
}
inline Polynomial Composition_Inverse(const Polynomial &a){int n = a.size();Polynomial ret, Cinv = a, Pow;Cinv.resize(n); ret.resize(n); Pow.resize(n); Pow[0] = 1;for(int i = 0; i < n - 1; ++ i) Cinv[i] = Cinv[i + 1]; Cinv[n - 1] = 0;Cinv = Inverse(Cinv);for(int i = 1; i < n; ++ i){Pow = Pow * Cinv; Pow.resize(n);ret[i] = 1ll * Pow[i - 1] * Inv(i) % mod;}return ret;
}
inline Polynomial Logarithmic(const Polynomial &a){Polynomial ln_a = Derivation(a) * Inverse(a);ln_a.resize(a.size());return Integral(ln_a);
}
inline Polynomial Exponential(const Polynomial &a, int Constant = 1){Polynomial ret, D; int ed = a.size();ret.resize(1); ret[0] = Constant;for(int len = 2; len <= ed; len <<= 1){D = Logarithmic(ret); D.resize(len);D[0] = (1ll * a[0] + 1ll - D[0] + mod) % mod;for(int i = 1; i < len; ++i) D[i] = (1ll * a[i] - D[i] + mod) % mod;int n = Prepare_Transformation(len<<1);ret.resize(n); D.resize(n);NTT(ret, 1); NTT(D,1);for(int i = 0; i < n; ++ i) ret[i] = 1ll * ret[i] * D[i] % mod;NTT(ret, -1);for(int i = len; i < (len<<1); ++ i) ret[i] = D[i] = 0;}ret.resize(ed);return ret;
}ll fac[int(6e5 + 10)] = {1}, ifac[int(6e5 + 10)] = {1};
ll C(int n, int m) {if(m == 0 || n == m) return 1;if(n < m) return 0;return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}//Polynomial ans(3);
Polynomial a(1010), b(1010);Polynomial DAC_NTT(int l, int r) {if (l == r) {Polynomial res;ll A = 1;ll B = (a[l] + b[l] - 2) % mod; while(B < 0) B += mod;ll C = (a[l] - b[l] + 1) % mod; while(C < 0) C += mod;res.push_back(A); res.push_back(B); res.push_back(C);return res;}int mid = l + r >> 1;return DAC_NTT(l, mid) * DAC_NTT(mid + 1, r);
}inline void solve() {for(int i = 1; i <= int(6e5); ++ i) fac[i] = 1ll * fac[i - 1] * i % mod, ifac[i] = Inv(fac[i]);int m; cin >> m;Polynomial res(50010);for(int i = 0; i <= 50000; ++ i) {res[i] = C(3 * m + i - 1, i);}
//     Polynomial ans;for(int i = 1; i <= m; ++ i) {cin >> a[i] >> b[i];
//         ll A = 1;
//         ll B = (a[i] + b[i] - 2) % mod; while(B < 0) B += mod;
//         ll C = (a[i] - b[i] + 1) % mod; while(C < 0) C += mod;
//         if(i == 1) {
//             ans.push_back(A), ans.push_back(B), ans.push_back(C);
//         } else {
//             Polynomial temp;
//             temp.push_back(A), temp.push_back(B), temp.push_back(C);
//             ans = ans * temp;
//         }}Polynomial ans = DAC_NTT(1, m);ans = ans * res;int q; cin >> q; while(q --) {int n; cin >> n;cout << ans[n] << '\n';}
}signed main() {ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#ifdef ACM_LOCALfreopen("input", "r", stdin);
//    freopen("output", "w", stdout);signed test_index_for_debug = 1;char acm_local_for_debug = 0;do {if (acm_local_for_debug == '$') exit(0);if (test_index_for_debug > 20)throw runtime_error("Check the stdin!!!");auto start_clock_for_debug = clock();solve();auto end_clock_for_debug = clock();cout << "Test " << test_index_for_debug << " successful" << endl;cerr << "Test " << test_index_for_debug++ << " Run Time: "<< double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;cout << "--------------------------------------------------" << endl;} while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
#elsesolve();
#endifreturn 0;
}

这篇关于无限手套 分治 + NTT + 生成函数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/286255。

相关文章

MySQL count()聚合函数详解

MySQL count()聚合函数详解

《MySQLcount()聚合函数详解》MySQL中的COUNT()函数,它是SQL中最常用的聚合函数之一,用于计算表中符合特定条件的行数,本文给大家介绍MySQLcount()聚合函数,感兴趣的朋... 目录核心功能语法形式重要特性与行为如何选择使用哪种形式？总结深入剖析一下 mysql 中的 COUNT
阅读更多...
MySQL 中 ROW_NUMBER() 函数最佳实践

MySQL 中 ROW_NUMBER() 函数最佳实践

《MySQL中ROW_NUMBER()函数最佳实践》MySQL中ROW_NUMBER()函数,作为窗口函数为每行分配唯一连续序号,区别于RANK()和DENSE_RANK(),特别适合分页、去重... 目录mysql 中 ROW_NUMBER() 函数详解一、基础语法二、核心特点三、典型应用场景1. 数据分
阅读更多...
MySQL数据库的内嵌函数和联合查询实例代码

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面：本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN
阅读更多...
Python get()函数用法案例详解

Python get()函数用法案例详解

《Pythonget()函数用法案例详解》在Python中,get()是字典（dict）类型的内置方法,用于安全地获取字典中指定键对应的值,它的核心作用是避免因访问不存在的键而引发KeyError错... 目录简介基本语法一、用法二、案例：安全访问未知键三、案例：配置参数默认值简介python是一种高级编
阅读更多...
python 常见数学公式函数使用详解(最新推荐)

python 常见数学公式函数使用详解(最新推荐)

《python常见数学公式函数使用详解(最新推荐)》文章介绍了Python的数学计算工具,涵盖内置函数、math/cmath标准库及numpy/scipy/sympy第三方库,支持从基础算术到复杂数... 目录python 数学公式与函数大全1. 基本数学运算1.1 算术运算1.2 分数与小数2. 数学函数
阅读更多...
Python中help()和dir()函数的使用

Python中help()和dir()函数的使用

《Python中help()和dir()函数的使用》我们经常需要查看某个对象（如模块、类、函数等）的属性和方法,Python提供了两个内置函数help()和dir(),它们可以帮助我们快速了解代... 目录1. 引言2. help() 函数2.1 作用2.2 使用方法2.3 示例(1) 查看内置函数的帮助(
阅读更多...
C++ 函数 strftime 和时间格式示例详解

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五
阅读更多...
Python实现自动化Word文档样式复制与内容生成

Python实现自动化Word文档样式复制与内容生成

《Python实现自动化Word文档样式复制与内容生成》在办公自动化领域,高效处理Word文档的样式和内容复制是一个常见需求,本文将展示如何利用Python的python-docx库实现... 目录一、为什么需要自动化 Word 文档处理二、核心功能实现：样式与表格的深度复制1. 表格复制（含样式与内容）2
阅读更多...
Python中bisect_left 函数实现高效插入与有序列表管理

Python中bisect_left 函数实现高效插入与有序列表管理

《Python中bisect_left函数实现高效插入与有序列表管理》Python的bisect_left函数通过二分查找高效定位有序列表插入位置,与bisect_right的区别在于处理重复元素时... 目录一、bisect_left 基本介绍1.1 函数定义1.2 核心功能二、bisect_left 与
阅读更多...
java中BigDecimal里面的subtract函数介绍及实现方法

java中BigDecimal里面的subtract函数介绍及实现方法

《java中BigDecimal里面的subtract函数介绍及实现方法》在Java中实现减法操作需要根据数据类型选择不同方法,主要分为数值型减法和字符串减法两种场景,本文给大家介绍java中BigD... 目录Java中BigDecimal里面的subtract函数的意思？一、数值型减法（高精度计算）1.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2