网站的电子手册用什么做的,枣阳网站开发公司哪家好,嘉兴网站建设与管理专业,互联网装修服务平台题目链接#xff1a;洛谷 题目大意#xff1a;现在有$n$个物品#xff0c;每种物品体积为$v_i$#xff0c;对任意$s\in [1,m]$#xff0c;求背包恰好装$s$体积的方案数#xff08;完全背包问题#xff09;。 数据范围#xff1a;$n,m\leq 10^5$ 这道题#xff0c;看到…题目链接洛谷 题目大意现在有$n$个物品每种物品体积为$v_i$对任意$s\in [1,m]$求背包恰好装$s$体积的方案数完全背包问题。 数据范围$n,m\leq 10^5$ 这道题看到数据范围就知道是生成函数。$$Ans\prod_{i1}^n\frac{1}{1-x^{v_i}}$$ 但是这个式子直接乘会tle我们考虑进行优化。 看见这个连乘的式子应该是要上$\ln$. $$Ans\exp(\sum_{i1}^n\ln(\frac{1}{1-x^{v_i}}))$$ 接下来的问题就是如何快速计算$\ln(\frac{1}{1-x^{v_i}})$。 $$\ln(f(x))\int ff^{-1}dx$$ 所以$$\ln(\frac{1}{1-x^v})\int\sum_{i1}^{\infty}vix^{vi-1}*(1-x^v)dx$$$$\int(\sum_{i1}^{\infty}vix^{vi-1}-\sum_{i2}^{\infty}v(i-1)x^{vi-1})dx$$$$\int(\sum_{i1}^{\infty}vx^{vi-1})dx$$$$\sum_{i1}^{\infty}\frac{1}{i}x^{vi}$$ 然后就可以直接代公式了。 1 #includecstdio2 #includealgorithm3 #define Rint register int4 using namespace std;5 typedef long long LL;6 const int N 400003, P 998244353, G 3, Gi 332748118;7 int n, m, cnt[N], A[N];8 inline int kasumi(int a, int b){9 int res 1;10 while(b){11 if(b 1) res (LL) res * a % P;12 a (LL) a * a % P;13 b 1;14 }15 return res;16 }17 int R[N];18 inline void NTT(int *A, int limit, int type){19 for(Rint i 1;i limit;i )20 if(i R[i]) swap(A[i], A[R[i]]);21 for(Rint mid 1;mid limit;mid 1){22 int Wn kasumi(type 1 ? G : Gi, (P - 1) / (mid 1));23 for(Rint j 0;j limit;j mid 1){24 int w 1;25 for(Rint k 0;k mid;k , w (LL) w * Wn % P){26 int x A[j k], y (LL) w * A[j k mid] % P;27 A[j k] (x y) % P;28 A[j k mid] (x - y P) % P;29 }30 }31 }32 if(type -1){33 int inv kasumi(limit, P - 2);34 for(Rint i 0;i limit;i )35 A[i] (LL) A[i] * inv % P;36 }37 }38 int ans[N];39 inline void poly_inv(int *A, int deg){40 static int tmp[N];41 if(deg 1){42 ans[0] kasumi(A[0], P - 2);43 return;44 }45 poly_inv(A, (deg 1) 1);46 int limit 1, L -1;47 while(limit (deg 1)){limit 1; L ;}48 for(Rint i 1;i limit;i )49 R[i] (R[i 1] 1) | ((i 1) L);50 for(Rint i 0;i deg;i ) tmp[i] A[i];51 for(Rint i deg;i limit;i ) tmp[i] 0;52 NTT(tmp, limit, 1); NTT(ans, limit, 1);53 for(Rint i 0;i limit;i )54 ans[i] (2 - (LL) tmp[i] * ans[i] % P P) % P * ans[i] % P;55 NTT(ans, limit, -1);56 for(Rint i deg;i limit;i ) ans[i] 0;57 }58 int Ln[N];59 inline void get_Ln(int *A, int deg){60 static int tmp[N];61 poly_inv(A, deg);62 for(Rint i 1;i deg;i )63 tmp[i - 1] (LL) i * A[i] % P;64 tmp[deg - 1] 0;65 int limit 1, L -1;66 while(limit (deg 1)){limit 1; L ;}67 for(Rint i 1;i limit;i )68 R[i] (R[i 1] 1) | ((i 1) L);69 NTT(ans, limit, 1); NTT(tmp, limit, 1);70 for(Rint i 0;i limit;i ) Ln[i] (LL) ans[i] * tmp[i] % P;71 NTT(Ln, limit, -1);72 for(Rint i deg 1;i limit;i ) Ln[i] 0;73 for(Rint i deg;i;i --) Ln[i] (LL) Ln[i - 1] * kasumi(i, P - 2) % P;74 for(Rint i 0;i limit;i ) tmp[i] ans[i] 0;75 Ln[0] 0;76 }77 int Exp[N];78 inline void get_Exp(int *A, int deg){79 if(deg 1){80 Exp[0] 1;81 return;82 }83 get_Exp(A, (deg 1) 1);84 get_Ln(Exp, deg);85 for(Rint i 0;i deg;i ) Ln[i] (A[i] (i 0) - Ln[i] P) % P;86 int limit 1, L -1;87 while(limit (deg 1)){limit 1; L ;}88 for(Rint i 1;i limit;i )89 R[i] (R[i 1] 1) | ((i 1) L);90 NTT(Exp, limit, 1); NTT(Ln, limit, 1);91 for(Rint i 0;i limit;i ) Exp[i] (LL) Exp[i] * Ln[i] % P;92 NTT(Exp, limit, -1);93 for(Rint i deg;i limit;i ) Exp[i] 0;94 for(Rint i 0;i limit;i ) Ln[i] ans[i] 0;95 }96 int main(){97 scanf(%d%d, n, m);98 for(Rint i 1;i n;i ){99 int x;
100 scanf(%d, x);
101 cnt[x];
102 }
103 for(Rint i 1;i m;i ){
104 if(!cnt[i]) continue;
105 for(Rint j i;j m;j i)
106 A[j] (A[j] (LL) cnt[i] * kasumi(j / i, P - 2) % P) % P;
107 }
108 get_Exp(A, m 1);
109 for(Rint i 1;i m;i )
110 printf(%d\n, Exp[i]);
111 } luogu4389 转载于:https://www.cnblogs.com/AThousandMoons/p/10524935.html
