差别

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

--- 2020-2021:teams:wangzai_milk:weekly5 [2020/06/07 00:02]
zars19 [Zars19]
+++ 2020-2021:teams:wangzai_milk:weekly5 [2020/07/01 13:00] (当前版本)
zars19 [Zars19]
@@ 行 5: / 行 5: @@
 ===== _wzx27 =====
+==== 1.补题 ====
 补了一下之前比赛的题
@@ 行 13: / 行 14: @@
 $$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 {n+i-1 \choose i}x^{ik}$
+其中$(\sum x^{ki})^m = \sum {i+m-1 \choose m-1}x^{ik}$
 另外模数刚好是998244353，做三次NTT即可
-<hidden code>
+<hidden>
 <code cpp>
 #include<bits/stdc++.h>
@@ 行 97: / 行 98: @@
     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)]]
 ===== 本周推荐 =====

CVBB ACM Team

用户工具

站点工具

差别

页面工具