題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè) n * n 的 01 矩陣，求滿秩的概率

題目分析：首先公式是：

稍微解釋一下吧，將 n * n 的矩陣視為 n 個(gè)長(zhǎng)度為 n 的向量，對(duì)于每一個(gè)長(zhǎng)度為 n 的向量，都有 2^n 種情況，因?yàn)橐?n 個(gè)向量線性獨(dú)立，所以我們依次討論：

對(duì)于第一個(gè)向量來(lái)說(shuō)，只需要至少有一個(gè)位置為 1 即可，即全部為 0 的情況不滿足條件，此時(shí)滿足條件的情況為

對(duì)于第二個(gè)向量來(lái)說(shuō)，需要滿足的條件是，不能全部為 0 ，且不能被第一個(gè)向量所表示，此時(shí)滿足條件的情況為

對(duì)于第三個(gè)向量來(lái)說(shuō)，同樣不能為 0 ，不能被第一個(gè)向量所表示，不能被第二個(gè)向量所表示，不能被第一個(gè)向量和第二個(gè)向量所表示，此時(shí)滿足條件的情況為

對(duì)于第四個(gè)向量來(lái)說(shuō)，不能被前面向量表示的集合為 { ? , { 1 } , { 2 } , { 3 } , { 1 , 2 } , { 1 , 3 } , { 2 , 3 } , { 1 , 2 , 3 } } ，共八種情況，所以此時(shí)滿足條件的情況為

......

對(duì)于第 n 個(gè)向量來(lái)說(shuō)，不能被前面 n - 1 個(gè)向量單獨(dú)或混合表示，此時(shí)滿足條件的情況為

然后下一步就是將其轉(zhuǎn)換為遞推式，根據(jù)

實(shí)現(xiàn)的話遞推 2 的逆元就好了，在 mod 為 1e9+7 時(shí)，2 的逆元為 500000004

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e7+100;const int mod=1e9+7;LL f[N],inv=500000004,ans[N];void init() {ans[1]=f[1]=500000004;LL _2=4,inv_2=inv*inv%mod;for(int i=2;i<N;i++){f[i]=f[i-1]*(_2-1)%mod*inv_2%mod;_2=_2*2%mod;inv_2=inv_2*inv%mod;ans[i]=ans[i-1]^f[i];} }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);init();int w;cin>>w;while(w--){int n;scanf("%d",&n);printf("%lld\n",ans[n]);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的牛客多校6 - Binary Vector(组合数学+推公式)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。