[BZOJ 3811]玛里苟斯(线性基)尽量理解的题解
文章目錄
- title
- solution
- code
title
魔法之龍瑪里茍斯最近在為加基森拍賣師的削弱而感到傷心,于是他想了一道數學題。
S 是一個可重集合,S={a1,a2,…,an}。
等概率隨機取 S 的一個子集 A={ai1,…,aim}。
計算出 A 中所有元素異或和,記為 x, 求 x^k 的期望。
Input
第一行兩個正整數 n, k。
以下 n 行每行一個整數,表示 ai。
Output
如果結果是整數,直接輸出。如果結果是小數(顯然這個小數是有限的),輸出精確值(末尾不加多余的 0)。
Sample Input
4 2 0 1 2 3
Sample Output
3.5
Hint
限制與約定
1≤n≤100000,1≤k≤5,ai≥0。最終答案小于 2^63 。k=1,2,3,4,5 各自占用 20% 的數據
solution
期望=概率*答案值(我一直是這么計算期望這一類題目的)
直接走正解,廢話不多說,因為我也不會引入
考慮k=1k=1k=1的情況
我們把答案值ansansans分解成二進制
如果第iii位上為111,那么這個iii就會對答案造成1<<i1<<i1<<i,即2i2^i2i的貢獻
那么我們怎么如何確定第iii位是不是111呢?
很簡單,看aaa數組里面有多少個數二進制第iii位為111
假設有xxx個,可以知道在這xxx個里面選擇的個數的奇偶性會影響最后iii位是否為111
選擇了奇數個,異或后就是111,否則就是000
而剩下的n?xn-xn?x個數不管選不選,都不會對iii這一位造成影響,因為這一位上面它們都是000
那么在xxx里面選擇個數的奇偶性的概率又分別是多少呢?這里給出一個結論
奇偶性的概率一樣,都是12\frac{1}{2}21?
我盡力感性證明一下
舉個栗子2,6,102,6,102,6,10,二進制分別為0010,0110,10100010,0110,10100010,0110,1010
就只看從右往左數的第二位(i=1,2ii=1,2^ii=1,2i),都是111對吧?!咀⒁鈴淖笸业谝晃婚_始分別是20,21...2^0,2^1...20,21...】
接著分類討論
如果只選000個,有111種情況
如果只選111個,有333種情況
如果只選222個,有333種情況
如果只選333個,有111種情況
選偶數個的情況總數=>=>=>選000個+++選222個:1+3=41+3=41+3=4
選奇數個的情況總數=>=>=>選111個+++選333個:1+3=41+3=41+3=4
驚奇的一樣!!
別急,再煮個栗子12,20,22,1312,20,22,1312,20,22,13,二進制分別是01100,10100,10110,0110101100,10100,10110,0110101100,10100,10110,01101,這一次就只看從左往右數的第三位(i=2,2ii=2,2^ii=2,2i)
如果只選000個,有111種情況
如果只選111個,有444種情況
如果只選222個,有666種情況
如果只選333個,有444種情況
如果只選444個,有111種情況
選偶數個的情況總數=>=>=>選000個+++選222個+++選444個:1+6+1=81+6+1=81+6+1=8
選奇數個的情況總數=>=>=>選111個+++選333個:4+4=84+4=84+4=8
驚奇的又一樣!!
而且仔細看這堆數字可以自然地聯想到楊輝三角!!(其實是因為上面的情況可以看成組合數)
如果還是覺得很巧,不太有說服性,或者沒想通的,我們再另辟蹊徑
把這種奇偶選擇操作看成按燈泡開關,上圖!
已經盡力了總結一下,只要有數能負責iii位,就會有一半的概率產生1<<i1<<i1<<i的貢獻
k=2k=2k=2的情況,最高位肯定小于333333,i<33i<33i<33
設f[s][i]f[s][i]f[s][i]表示當選取情況為sss的時候,iii這一位是1/01/01/0,貢獻就是f[s][i]2=∑if[s][i]?∑jf[s][j]=∑i∑jf[s][i]?f[s][j]f[s][i]^2=\sum_if[s][i]*\sum_jf[s][j]=\sum_i\sum_jf[s][i]*f[s][j]f[s][i]2=i∑?f[s][i]?j∑?f[s][j]=i∑?j∑?f[s][i]?f[s][j]
只有i=1,j=1i=1,j=1i=1,j=1才會產生上面的貢獻,即為1<<(i+j)=2i+j1<<(i+j)=2^{i+j}1<<(i+j)=2i+j
接著我們來分類討論,注意i,j表示二進制下的第i位,第j位為1/0
①:i=0∣∣j=0i=0||j=0i=0∣∣j=0
意思就是i,ji,ji,j至少有一個是沒有任何數可以負責的,就是沒有任何一個數的二進制在那一位上面為111
貢獻自然是000
②:i=1&&j=1i=1\&\&j=1i=1&&j=1
結合k=1k=1k=1的情況下,我們知道選完數后要保證iii這一位上的值為111才能對答案產生影響嘛
這個概率是12\frac{1}{2}21?,jjj同理,那么要讓i,ji,ji,j同時為111,概率就是12?12=14\frac{1}{2}*\frac{1}{2}=\frac{1}{4}21??21?=41?
但,BUT,However,unfortunately,unluckily
情況不止步于此,我們忽略掉了可能存在一些數二進制i,ji,ji,j位都為111
這樣的話如果選擇它,就會同步影響i,ji,ji,j,所以我們要重新再分類討論
結合k=1k=1k=1按燈泡開關的思想,直接上圖
其實k>=3k>=3k>=3的情況是最簡單的,氧化鈣!!
因為答案保證<263<2^{63}<263,考慮第iii位會產生貢獻,那么它對答案的影響就是(2i)k(2^i)^k(2i)k,除掉kkk
可以得到i<22i<22i<22,比iii位更大的位置上一定都是000
很容易想嘛,假設i=22i=22i=22這位有111就會產生(1<<22)k(1<<22)^k(1<<22)k,最小的k=3k=3k=3也會炸掉2632^{63}263答案范圍
所以我們就直接暴力枚舉每一個數選與不選,生成子集AAA,然后去算期望
注意只考慮線性基里面的每一個數,因為線性基可以異或出原數組的每一個數,自然也可以異或出原數組的異或和
記線性基的個數為mmm
一共有2m2^m2m種情況,每一種情況都是12m\frac{1}{2^m}2m1?
用mod=1<<mmod=1<<mmod=1<<m將期望拆開算,不然會炸unsignedlonglongunsigned\ long\ longunsigned?long?long
code
#include <cstdio> #define int unsigned long long #define MAXN 100005 int n, k, ans, cnt, r; int a[MAXN], f[65], s[65]; bool vis[65];int read() {int x = 0; char s = getchar();while( s < '0' || s > '9' ) s = getchar();while( '0' <= s && s <= '9' )x = ( x << 1 ) + ( x << 3 ) + ( s - '0' ), s = getchar();return x; }void solve1() { for( int i = 1;i <= n;i ++ ) ans |= a[i];if( ans & 1 ) printf( "%llu.5", ans >> 1 );else printf( "%llu", ans >> 1 ); }bool check( int i, int j ) {if( ! vis[i] || ! vis[j] ) return 0;for( int t = 1;t <= n;t ++ ) {if( ( a[t] & ( 1ll << i ) ) && ! ( a[t] & ( 1ll << j ) ) )return 0;if( ( a[t] & ( 1ll << j ) ) && ! ( a[t] & ( 1ll << i ) ) )return 0;}return 1; }void solve2() {for( int i = 0;i < 33;i ++ )for( int j = 1;j <= n;j ++ )if( a[j] & ( 1ll << i ) ) { vis[i] = 1; break; }for( int i = 0;i < 33;i ++ )for(int j = i;j < 33;j ++ )if( vis[i] && vis[j] ) ans += ( 1ll << ( i + j ) );for( int i = 0;i < 33;i ++ )for( int j = i + 1;j < 33;j ++ )if( check( i, j ) ) ans += ( 1ll << ( i + j ) );if( ans & 1 ) printf( "%llu.5", ans >> 1 );else printf( "%llu", ans >> 1 ); }void calc( int val ) {int mod = 1ll << cnt;int D = 0, R = 1;for( int i = 1;i <= k;i ++ )D = D * val, R = R * val, D += R / mod, R %= mod;ans += D, r += R, ans += r / mod, r %= mod; }void dfs( int x, int val ) {if( x > cnt ) { calc( val ); return; }dfs( x + 1, val ); dfs( x + 1, val ^ s[x] ); }void solve3() {for( int i = 1;i <= n;i ++ ) {int val = a[i];for( int j = 21;~ j;j -- )if( ( 1ll << j ) & val )if( f[j] ) val ^= f[j];else { f[j] = val; break; }}for( int i = 0;i <= 21;i ++ )if( f[i] ) s[++ cnt] = f[i];dfs( 1, 0 );if( r ) printf( "%llu.5", ans );else printf( "%llu", ans ); }signed main() {n = read(); k = read();for( int i = 1;i <= n;i ++ )a[i] = read();if( k == 1 ) solve1();else if( k == 2 ) solve2();else solve3();return 0; }總結
以上是生活随笔為你收集整理的[BZOJ 3811]玛里苟斯(线性基)尽量理解的题解的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 科普计算机软硬件知识,科普显卡基础知识
- 下一篇: 如何清空windows的系统剪贴板