差别

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

--- 2020-2021:teams:wangzai_milk:weekly5 [2020/06/05 14:42]
infinity37 创建
+++ 2020-2021:teams:wangzai_milk:weekly5 [2020/07/01 13:00] (当前版本)
zars19 [Zars19]
@@ 行 5: / 行 5: @@
 ===== _wzx27 =====
+==== 1.补题 ====
+补了一下之前比赛的题
+[[http://acm.hdu.edu.cn/showproblem.php?pid=6589|HDU6589 Sequence]]
+把数列 $a_i$ 写成其生成函数的形式 $f(x)=\sum a_ix^i$，每个操作 $k$ 相当于 $f(x)\cdot \sum x^{ik}$，由交换律知顺序不重要，所以可以统计每种操作的次数 $m_i$，最后有
+$$f(x)\cdot (\sum x^{i})^{m_1} \cdot (\sum x^{2i})^{m_2} \cdot (\sum x^{3i})^{m_3}$$
+其中$(\sum x^{ki})^m = \sum {i+m-1 \choose m-1}x^{ik}$
+另外模数刚好是998244353，做三次NTT即可
+<hidden>
+<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 = 2e6+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,lim,l,r[maxn],cnt[maxn];
+ll A[maxn],B[maxn],fac[maxn],inv[maxn];
+int c[5];
+void NTT(ll a[],int type)
+{
+    rep(i,1,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;
+    }
+}
+ll Comb(ll a,ll b) {return a<b?0:fac[a]*inv[b]%M*inv[a-b]%M;}
+void init()
+{
+    fac[0] = 1;
+    rep(i,1,2000000) fac[i]=fac[i-1]*i%M;
+    inv[2000000] = qpow(fac[2000000],M-2);
+    per(i,2000000-1,0) inv[i]=inv[i+1]*(i+1)%M;
+}
+int main()
+{
+    fastio();
+    int _;
+    init();
+    for(cin>>_;_;_--){
+        cin>>n>>m;
+        memset(A,0,sizeof(A));
+        memset(B,0,sizeof(B));
+        rep(i,0,n-1) cin>>A[i];
+        lim=1,l=0;
+        while(lim<=2*n) lim<<=1,l++;
+        rep(i,0,lim-1) r[i] = (r[i>>1]>>1) | ((i&1)<<(l-1));
+        cnt[1]=cnt[2]=cnt[3]=0;
+        while(m--) {int x;cin>>x;cnt[x]++;}
+        rep(i,1,3)if(cnt[i]){
+            memset(B,0,sizeof(B));
+            for(int j=0;j*i<n;j++) B[i*j] = Comb(cnt[i]+j-1,j);
+            NTT(A,1);NTT(B,1);
+            rep(i,0,lim) A[i] = A[i]*B[i]%M;
+            NTT(A,-1);
+            rep(i,n+1,lim) A[i]=0;
+        }
+        ll ans = 0;
+        rep(i,0,n-1) ans ^= ((i+1)*A[i]);
+        cout<<ans<<endl;
+    }
+    return 0;
+}
+</code>
+</hidden>
+==== 2.整数分拆 ====
+生成函数的基本应用，求 $x1+x2+x3\cdots x^k=n$ 的非负整数解的个数。
+=== 2.1 有序分拆 ===
+把每个数写成生成函数 $(1+x+x^2+\cdots)$ 的形式
+那么分拆数就等于 $(1+x+x^2+\cdots)^k$ 的 $n$ 次项前面的系数${n+k-1 \choose k-1}$
+这个证明可以通过$(1+x+x^2+\cdots)^k=\frac 1{(1-x)^k}$的逐项求导证明
+=== 2.2 无序分拆 ===
+无序的分拆容易想到朴素 $O(n^2)$ 的$\text{dp}$
+记 $P(n)$ 为 $n$ 的无序拆分数如果用生成函数来做就是
+$$\sum_{i=1}^\infty P(i)x^i=(1+x+x^2+\cdots)(1+x^2+x^4+\cdots)\cdots=\prod_{i=0}^\infty \frac 1{1-x^i}$$
+结合五边形数定理 $\prod_{i=0}^\infty (1-x^i)=1+\sum_{i=1}^\infty (-1)^i(x^{\frac {i(3i-1)}2}+x^{\frac {i(3i+1)}2})$ 得到：
+$$(1+P(1)x+P(2)x^2+\cdots)(1-x-x^2+x^5+\cdots)=1$$
+比较两边的系数得到 $P(n)-P(n-1)-P(n-2)+P(n-5)=0$，即$P(n)-P(n-1)-P(n-2)+P(n-5)+P(n-7)-\cdots = 0$
+这样就得到了 $P(n)=\sum_{i=1}(-1)^i(P(n-\frac {i(3i-1)}2)+P(n-\frac {i(3i+1)}2))$
+[[http://acm.hdu.edu.cn/showproblem.php?pid=4651|HDU4651]]
+模板题
+<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 = 2e5+5;
+const ll M = 1e9+7;
+inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
+ll f1[maxn],f2[maxn],P[maxn];
+void init()
+{
+    int n = 1e5;
+    for(int i=1;;i++){
+        f1[i] = (3*i*i-i)>>1;
+        if(f1[i]>n) break;
+        f2[i] = (3*i*i+i)>>1;
+        if(f2[i]>n) break;
+    }
+    P[0] = 1;
+    rep(i,1,n){
+        for(int j=1;;j++){
+            if(f1[j]<=i) P[i] += (j&1)?P[i-f1[j]] : -P[i-f1[j]];
+            else break;
+            if(f2[j]<=i) P[i] += (j&1)?P[i-f2[j]] : -P[i-f2[j]];
+            else break;
+        }
+        P[i] = (P[i]%M+M)%M;
+    }
+}
+int main()
+{
+    fastio();
+    init();
+    int _,n;
+    for(cin>>_;_;_--){
+        cin>>n;cout<<P[n]<<endl;
+    }
+    return 0;
+}
+</code>
+</hidden>
+[[http://acm.hdu.edu.cn/showproblem.php?pid=4658|HDU4658]]
+拆分时每个数的使用次数要小于 $k$。
+把生成函数改一下：
+$$(1+x+x^2+\cdots+x^{k-1})(1+x^2+x^4+\cdots+x^{2(k-1)})\cdots=\prod_{i=1}^\infty \frac {1-x^{ik}}{1-x^i}=\phi(x^k)\sum_{i=0}^\infty P(n)x^i$$
+<hidden>
+<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 = 2e5+5;
+const ll M = 1e9+7;
+inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
+ll f1[maxn],f2[maxn],P[maxn];
+void init()
+{
+    int n = 1e5;
+    for(int i=1;;i++){
+        f1[i] = (3*i*i-i)>>1;
+        if(f1[i]>n) break;
+        f2[i] = (3*i*i+i)>>1;
+        if(f2[i]>n) break;
+    }
+    P[0] = 1;
+    rep(i,1,n){
+        for(int j=1;;j++){
+            if(f1[j]<=i) P[i] += (j&1)?P[i-f1[j]] : -P[i-f1[j]];
+            else break;
+            if(f2[j]<=i) P[i] += (j&1)?P[i-f2[j]] : -P[i-f2[j]];
+            else break;
+        }
+        P[i] = (P[i]%M+M)%M;
+    }
+}
+ll solve(int n,int k)
+{
+    ll ans = P[n];
+    for(int i=1;;i++){
+        ll a = (ll)k*(3*i*i-i)>>1;
+        if(a>n) break;
+        ll t = P[n-a];
+        ll b = (ll)k*(3*i*i+i)>>1;
+        if(b<=n) t = (t+P[n-b])%M;
+        if(i&1) ans = (ans-t+M)%M;
+        else ans = (ans+t)%M;
+    }
+    return ans;
+}
+int main()
+{
+    fastio();
+    init();
+    int _,n,k;
+    for(cin>>_;_;_--){
+        cin>>n>>k;cout<<solve(n,k)<<endl;
+    }
+    return 0;
+}
+</code>
+</hidden>
 ===== Infinity37 =====
 在搞期末考试，完全摸了
 ===== Zars19 =====
+不好意思摸了摸了，我马上补555
+楼上上好强…
+==== 比赛 ====
+[[Educational Codeforces Round 83 (Rated for Div. 2)]]
 ===== 本周推荐 =====
-先放一个本周要写的wiki：[[树链剖分]]
-、[[https://www.luogu.com.cn/problem/P2227|P2227 洗牌机]]
-置换群的分数幂（开方）运算，有助于加深对置换群的一些性质的了解

CVBB ACM Team

用户工具

站点工具

差别

页面工具