差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:wangzai_milk:weekly6 [2020/06/09 11:39]
wzx27
+++ 2020-2021:teams:wangzai_milk:weekly6 [2020/07/01 13:03] (当前版本)
zars19 [Zars19]
@@ 行 1: / 行 1: @@
-====== 2020.06.01-2020.06.07 周报 ======
+====== 2020.06.08-2020.06.14 周报 ======
 ===== 团队训练 =====
+.06.14 [[https://codeforces.com/gym/101611|2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest]] ''prob:6:6:10'' ''rnk:124/?''
+[[20200614比赛记录]]
 ===== _wzx27 =====
 === 1.指数生成函数 ===
-== 1.1 基本计数问题 ==
 常用于解决一类多重集合计数的问题
@@ 行 86: / 行 87: @@
         cout<<setprecision(3)<<ans<<endl;
     }
+    return 0;
+}
+</code>
+</hidden>
+=== 2.生成函数与多项式 ===
+生成函数没那么好求的时候就要用多项式全家桶
+[[https://www.luogu.com.cn/problem/P4389|P4389付公主的背包]]
+$n$ 种无限个物品，每个物品体积为 $v_i$，求恰好装下体积为 $1~m$ 的种数。
+数据范围：$n,m \le 1e5$
+这种题也算是生成函数的经典应用
+首先得到生成函数：$f(x)=\prod _{i=1}^n \frac 1{1-x^{v_i}}$
+两边取对数得
+$$
+\begin{aligned}
+lnf(x) =&\sum_{i=1}^n\sum_{j=0}^\infty \frac {x^{j\cdot v_i}}j \\
+=&\sum_{k=0}^m \sum _{v_i|k} \frac {v_i}k x^k \pmod{x^{m+1}}
+\end{aligned}
+$$
+$O(nlogn)$预处理出 $k$ 的所有因子，然后多项式 $\text{Exp} $求 $e^{lnf(x)}$ 即可。
+<hidden code>
+<code cpp>
+#include<bits/stdc++.h>
+#define ll long long
+#define pii_ pair<int,int>
+#define mp_ make_pair
+#define pb push_back
+#define fi first
+#define se second
+#define rep(i,a,b) for(int i=(a);i<=(b);i++)
+#define per(i,a,b) for(int i=(a);i>=(b);i--)
+#define show1(a) cout<<#a<<" = "<<a<<endl
+#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl
+using namespace std;
+const ll INF = 1LL<<60;
+const int inf = 1<<30;
+const int maxn = 4e5+5;
+const ll M = 998244353;
+inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
+ll qpow(ll a,ll b) {ll s=1;while(b){if(b&1)s=(s*a)%M;a=(a*a)%M;b>>=1;}return s; }
+int n,m,cnt[maxn],r[maxn];
+ll A[maxn],B[maxn],tmp[maxn],t1[maxn],t2[maxn],t3[maxn];
+vector<int> g[maxn];
+void init()
+{
+    int n = 1e5;
+    rep(i,1,n){
+        for(int j=i;j<=n;j+=i) g[j].pb(i);
+    }
+}
+void add(ll &x,ll y)
+{
+    x+=y;if(x<0) x+=M;if(x>M) x-=M;
+}
+void NTT(ll a[],int lim,int type)
+{
+    rep(i,0,lim-1) if(i<r[i]) swap(a[i],a[r[i]]);
+    for(int mid=1;mid<lim;mid<<=1){
+        ll wn = qpow(3,(M-1)/mid/2);
+        if(type==-1) wn = qpow(wn,M-2);
+        for(int R=mid<<1,j=0;j<lim;j+=R){
+            ll w = 1;
+            for(int k=0;k<mid;k++,w=w*wn%M){
+                ll x=a[j+k],y=w*a[j+mid+k]%M;
+                a[j+k] = (x+y)%M;
+                a[j+mid+k] = (x-y+M)%M;
+            }
+        }
+    }
+    if(type==-1){
+        ll inv = qpow(lim,M-2);
+        rep(i,0,lim) a[i]=a[i]*inv%M;
+    }
+}
+void PolyMul(ll a[],ll b[],int n,int m)
+{
+    int lim=1,l=0;
+    while(lim<=n+m) lim<<=1,l++;
+    rep(i,1,lim) r[i] = (r[i>>1]>>1) | ((i&1)<<(l-1));
+    NTT(a,lim,1);NTT(b,lim,1);
+    rep(i,0,lim) a[i] = a[i]*b[i]%M;
+    NTT(a,lim,-1);
+}
+void PolyInv(int n,ll a[],ll b[])
+{
+    if(n==1) {b[0]=qpow(a[0],M-2);return ;}
+    PolyInv((n+1)>>1,a,b);
+    int lim=1,l=0;
+    while(lim<2*n) lim<<=1,l++;
+    rep(i,1,lim-1) r[i] = (r[i>>1]>>1) | ((i&1)<<(l-1));
+    rep(i,0,n-1) tmp[i] = a[i];
+    rep(i,n,lim) tmp[i] = 0;
+    NTT(tmp,lim,1);NTT(b,lim,1);
+    rep(i,0,lim){
+        b[i] = (2-tmp[i]*b[i]%M+M)%M*b[i]%M;
+    }
+    NTT(b,lim,-1);
+    rep(i,n,lim) b[i]=0;
+}
+void PolyDf(int n,ll a[],ll b[])
+{
+    rep(i,0,n) b[i] = a[i+1]*(i+1)%M;
+}
+void PolyItg(int n,ll a[],ll b[])
+{
+    rep(i,1,n) b[i] = a[i-1]*qpow(i,M-2)%M;b[0]=0;
+}
+void PolyLn(int n,ll a[],ll b[])
+{
+    PolyDf(n,a,t1);
+    PolyInv(n,a,t2);
+    PolyMul(t1,t2,n,n);
+    PolyItg(n,t1,b);
+}
+void PolyExp(int n,ll a[],ll b[])
+{
+    if(n==1) {b[0]=1;return ;}
+    PolyExp((n+1)>>1,a,b);
+    int lim=1,l=0;
+    while(lim<2*n) lim<<=1,l++;
+    rep(i,0,lim) t1[i]=t2[i]=0;
+    PolyLn(n,b,t3);
+    rep(i,1,lim) r[i] = (r[i>>1]>>1) | ((i&1)<<(l-1));
+    rep(i,1,n-1) t3[i] = (a[i]-t3[i]+M)%M;
+    t3[0] = (1+a[0]-t3[0]+M)%M;
+    rep(i,n,lim) b[i]=t3[i]=0;
+    NTT(t3,lim,1);NTT(b,lim,1);
+    rep(i,0,lim) b[i] = b[i]*t3[i]%M;
+    NTT(b,lim,-1);
+    rep(i,n,lim) b[i] = 0;
+}
+int main()
+{
+    fastio();
+    init();
+    cin>>n>>m;
+    int x;
+    rep(i,1,n) {cin>>x;cnt[x]++;}
+    rep(i,0,m){
+        ll inv = qpow(i,M-2);
+        for(int x:g[i]) if(cnt[x]) add(A[i],cnt[x]*x%M*inv%M);
+    }
+    PolyExp(m+1,A,B);
+    rep(i,1,m) cout<<B[i]<<endl;
     return 0;
 }
@@ 行 92: / 行 245: @@
 ===== Infinity37 =====
+[[20200614比赛记录#d_decoding_of_varints|D.Decoding of Varints]]
+[[20200614比赛记录#h_hilarious_cooking|H.Hilarious Cooking]]
 ===== Zars19 =====
+==== 题目 ====
+[[20200614比赛记录#C.Carpet]]
 ===== 本周推荐 =====

CVBB ACM Team

用户工具

站点工具

差别

页面工具