二項式反転(学習ノート)
q w q qwq機械室最後の二項式反転を学んだ人
二項式反転はfn＝Σi＝0 n(−1)iとして表すことが知られている× C n i × g i ⟺ g n = ∑ i = 0 n ( − 1 ) i × C n i × f i f_n=\sum_{i=0}^n (-1)^i\times C_n^i\times g_i\Longleftrightarrow g_n=\sum_{i=0}^n(-1)^i\times C_n^i\times f_i fn=i=0∑n(−1)i×Cni×gi⟺gn=i=0∑n(−1)i×Cni×fi
極めて対称な式であり,一般的な表現はfn＝Σi＝0 nCniである.× g i ⟺ g n = ∑ i = 0 n ( − 1 ) n − i × C n i × f i f_n=\sum_{i=0}^n C_n^i\times g_i\Longleftrightarrow g_n=\sum_{i=0}^n(-1)^{n-i}\times C_n^i\times f_i fn=i=0∑nCni×gi⟺gn=i=0∑n(−1)n−i×Cni×fi
ネット上にはたくさんの良い証明書があります.例えば、このブログでは、批判的な証明書がイメージ的だと感じています.私は証明書を書きません(実は証明書を書くのがおっくうです).
ここにはいくつかのやり方とテーマしか書いていません.
もしb l a b l a blabla blablaがちょうどk k k個のb l a b l a blabla blablaがあることを要求するならば、時には計算しにくいことがあって、多くk k個のb l a b l a blabla blablaがあることを求める時とても計算することができて、最も古典的なのは間違いの排出の問題で、間違いの排出の問題はプッシュがあるようで、しかし2項式の反転もすることができます
f i f_とするi fiは適切なシナリオ数を表し、g i g_i giは最大のシナリオ数を表し,g n=Σi=0 nCn i× f i g_n=\sum_{i=0}^n C_n^i\times f_i gn=i=0∑nCni×fi二項式によるfn=Σi=0 n(−1)n−iの反転× C n i × g i f_n=\sum_{i=0}^n(-1)^{n-i}\times C_n^i\times g_i fn=i=0∑n(−1)n−i×Cni×giそしてg i g_i giは一般的に短い時間で簡単に求めることができ、g gでf f fを求めると答えが得られる.
例題:hdu 1465容易でないシリーズの一つ
誤排問題設定f i f_i fiはi i i個のずれがあることを示し、g i g_i giはi i i個までずらすことを表し、g i=i!g_i=i! gi=i!,そして、上の式をセットすればいいです.コードは次のとおりです.
同様に時には少なくともk k個のb l a b l a blabla blablaのがもっと良いことを求めます
f i f_とするi fiは適切なシナリオ数を表し、g i g_i giは少なくともシナリオ数を表し、g k=Σi=k n C i k× f i g_k=\sum_{i=k}^nC_i^k\times f_i gk=i=k∑nCik×fi二項式によるfk=Σi=kn(−1)i−kの反転× C i k × g i f_k=\sum_{i=k}^n(-1)^{i-k}\times C_i^k\times g_i fk=i=k∑n(−1)i−k×Cik×gi
例題:bzoj 3622:もう何も恐れることはありませんまずa>b a>b a>b多k k個が要求されるので、a>b a>b a>bのはn+k 2frac{n+k}{2}2 n+k個(決して問題を間違えないでください
快適に打つためにf i f_i fiは、少なくともi i i個のa>b a>b a>bのシナリオ数を表すが、これは直接計算できないので、d p dpを考慮して、a,b a,b a,bを小さいものから大きいものに並べ替え、f[i][j]f[i][j]f[i][j]f[i][j]f[i][j]が前i個の少なくともj j j個のa>b a>b a>bを表すシナリオ数を、現在のa[i]a[i]a[i]a[i]a[i]a[i]より小さいb bがいくつあるかを算出するだけで、前に使用したものをさらに減らす.式はf[i][j]=f[i−1][j−1]である.× ( c n t [ i ] − j + 1 ) + f [ i − 1 ] [ j ] f[i][j]=f[i-1][j-1]\times (cnt[i]-j+1)+f[i-1][j] f[i][j]=f[i−1][j−1]×(cnt[i]−j+1)+f[i−1][j]
算出後にf[n][i]f[n][i]f[n][i]f[n][i]を上の式に持ち込んで最終的に適切な答えを計算する注意f[n][i]f[n][i]f[n][i]f[n][i]を使うときは× ( n − i ) !\times (n-i)! ×(n−i)!,他の席は勝手に置いてあるので
コードは次のとおりです.
bzoj 2839:集合カウントはまずf i f_を設定するi fiは、i i i個の要素がちょうど交差していることを示し、g i g_i giは少なくとも、g i=C n iを表す× ( 2 2 n − i − 1 ) g_i=C_n^i\times (2^{2^{n-i}}-1) gi=Cni×(22 n−i−1)ここでの意味は,i i i個を必ず選択しなければならないということであり,残りは2 n−i 2^{n−i}2 n−i個の集合を選択しなくてもよいが,いずれも選択しなくてもよい,上式がある.
以上の式を用いて,fk=Σi=kn(−1)i−kを導出した.× C i k × C n i × ( 2 2 n − i − 1 ) f_k=\sum_{i=k}^n(-1)^{i-k}\times C_i^k\times C_n^i\times (2^{2^{n-i}}-1) fk=i=k∑n(−1)i−k×Cik×Cni×(22 n−i−1)O(n)O(n)O(n)計算でよいが、後の2 n−i 2^{2^{n−i}}22 n−iは指数が&VeryThinSpaceできないため、直接高速べき乗できないようだ.m o d pbmod p modpは,2 2 t=(2 t−1)2^{2^t}=(2^{2^{t−1})^2 22 t=(22 t−1)2で逆算する.
コードは次のとおりです.
二項式反転はfn＝Σi＝0 n(−1)iとして表すことが知られている× C n i × g i ⟺ g n = ∑ i = 0 n ( − 1 ) i × C n i × f i f_n=\sum_{i=0}^n (-1)^i\times C_n^i\times g_i\Longleftrightarrow g_n=\sum_{i=0}^n(-1)^i\times C_n^i\times f_i fn=i=0∑n(−1)i×Cni×gi⟺gn=i=0∑n(−1)i×Cni×fi
極めて対称な式であり,一般的な表現はfn＝Σi＝0 nCniである.× g i ⟺ g n = ∑ i = 0 n ( − 1 ) n − i × C n i × f i f_n=\sum_{i=0}^n C_n^i\times g_i\Longleftrightarrow g_n=\sum_{i=0}^n(-1)^{n-i}\times C_n^i\times f_i fn=i=0∑nCni×gi⟺gn=i=0∑n(−1)n−i×Cni×fi
ネット上にはたくさんの良い証明書があります.例えば、このブログでは、批判的な証明書がイメージ的だと感じています.私は証明書を書きません(実は証明書を書くのがおっくうです).
ここにはいくつかのやり方とテーマしか書いていません.
ぴったりと至多の転換
もしb l a b l a blabla blablaがちょうどk k k個のb l a b l a blabla blablaがあることを要求するならば、時には計算しにくいことがあって、多くk k個のb l a b l a blabla blablaがあることを求める時とても計算することができて、最も古典的なのは間違いの排出の問題で、間違いの排出の問題はプッシュがあるようで、しかし2項式の反転もすることができます
f i f_とするi fiは適切なシナリオ数を表し、g i g_i giは最大のシナリオ数を表し,g n=Σi=0 nCn i× f i g_n=\sum_{i=0}^n C_n^i\times f_i gn=i=0∑nCni×fi二項式によるfn=Σi=0 n(−1)n−iの反転× C n i × g i f_n=\sum_{i=0}^n(-1)^{n-i}\times C_n^i\times g_i fn=i=0∑n(−1)n−i×Cni×giそしてg i g_i giは一般的に短い時間で簡単に求めることができ、g gでf f fを求めると答えが得られる.
例題:hdu 1465容易でないシリーズの一つ
誤排問題設定f i f_i fiはi i i個のずれがあることを示し、g i g_i giはi i i個までずらすことを表し、g i=i!g_i=i! gi=i!,そして、上の式をセットすればいいです.コードは次のとおりです.
#include
",f[n]);
}
return 0;
}
適切かつ少なくとも変換
同様に時には少なくともk k個のb l a b l a blabla blablaのがもっと良いことを求めます
f i f_とするi fiは適切なシナリオ数を表し、g i g_i giは少なくともシナリオ数を表し、g k=Σi=k n C i k× f i g_k=\sum_{i=k}^nC_i^k\times f_i gk=i=k∑nCik×fi二項式によるfk=Σi=kn(−1)i−kの反転× C i k × g i f_k=\sum_{i=k}^n(-1)^{i-k}\times C_i^k\times g_i fk=i=k∑n(−1)i−k×Cik×gi
例題:bzoj 3622:もう何も恐れることはありませんまずa>b a>b a>b多k k個が要求されるので、a>b a>b a>bのはn+k 2frac{n+k}{2}2 n+k個(決して問題を間違えないでください
快適に打つためにf i f_i fiは、少なくともi i i個のa>b a>b a>bのシナリオ数を表すが、これは直接計算できないので、d p dpを考慮して、a,b a,b a,bを小さいものから大きいものに並べ替え、f[i][j]f[i][j]f[i][j]f[i][j]f[i][j]が前i個の少なくともj j j個のa>b a>b a>bを表すシナリオ数を、現在のa[i]a[i]a[i]a[i]a[i]a[i]より小さいb bがいくつあるかを算出するだけで、前に使用したものをさらに減らす.式はf[i][j]=f[i−1][j−1]である.× ( c n t [ i ] − j + 1 ) + f [ i − 1 ] [ j ] f[i][j]=f[i-1][j-1]\times (cnt[i]-j+1)+f[i-1][j] f[i][j]=f[i−1][j−1]×(cnt[i]−j+1)+f[i−1][j]
算出後にf[n][i]f[n][i]f[n][i]f[n][i]を上の式に持ち込んで最終的に適切な答えを計算する注意f[n][i]f[n][i]f[n][i]f[n][i]を使うときは× ( n − i ) !\times (n-i)! ×(n−i)!,他の席は勝手に置いてあるので
コードは次のとおりです.
#include
",ans);
return 0;
}
bzoj 2839:集合カウントはまずf i f_を設定するi fiは、i i i個の要素がちょうど交差していることを示し、g i g_i giは少なくとも、g i=C n iを表す× ( 2 2 n − i − 1 ) g_i=C_n^i\times (2^{2^{n-i}}-1) gi=Cni×(22 n−i−1)ここでの意味は,i i i個を必ず選択しなければならないということであり,残りは2 n−i 2^{n−i}2 n−i個の集合を選択しなくてもよいが,いずれも選択しなくてもよい,上式がある.
以上の式を用いて,fk=Σi=kn(−1)i−kを導出した.× C i k × C n i × ( 2 2 n − i − 1 ) f_k=\sum_{i=k}^n(-1)^{i-k}\times C_i^k\times C_n^i\times (2^{2^{n-i}}-1) fk=i=k∑n(−1)i−k×Cik×Cni×(22 n−i−1)O(n)O(n)O(n)計算でよいが、後の2 n−i 2^{2^{n−i}}22 n−iは指数が&VeryThinSpaceできないため、直接高速べき乗できないようだ.m o d pbmod p modpは,2 2 t=(2 t−1)2^{2^t}=(2^{2^{t−1})^2 22 t=(22 t−1)2で逆算する.
コードは次のとおりです.
#include
",(ans+mod)%mod);
return 0;
}