沉默是金

時間限制:?1 Sec??內存限制:?128 MB

題目描述

終于活成了自己最討厭的模樣。

小希遇到了一個序列，他現在可以在序列中可以有重復地取k個數組成一個新的序列。該序列有以下幾個性質：

1、長度為k；

2、序列中的數字滿足相鄰兩個數字異或后的二進制數字中1的個數是3的倍數。

一共有多少個滿足條件的序列？

輸入

有多組測試樣例。

第一行兩個數n，k代表給定序列的長度和待取序列的長度。

接下來一行n個數字，代表給定序列。

輸出

每個答案一行，輸出滿足條件的序列的個數。答案模1000000007

樣例輸入

5 2 15 1 2 4 8 10 1 44 65 23 44 100 19 19 23 19 40 10 2 93 93 85 48 44 98 93 100 98 98 10 100 22 0 41 63 22 41 17 22 15 42 10 1000000000 454240622 216977025 454240622 509843007 509843007 26552516 488949284 708817573 453191950 447767457

樣例輸出

13 10 52 205668186 108319885

題意：

給定序列，從序列中選擇k(1≤k≤1e18)個數（可以重復選擇），使得得到的排列滿足xi與xi+1異或的二進制表示中1的個數是3的倍數。問長度為k的滿足條件的 序列有多少種？

分析：

首先每個元素自己構成一個長度為1的滿足條件的序列。?
其次我們可以預處理出滿足條件的vi,vj，就可以得到一個橫縱為n的01矩陣。此時我們得到了以vi開頭，vj結尾的長度為2的序列個數。?
接下來我們發現，兩個矩陣相乘，矩陣c為新得到的矩陣，此時矩陣a=b,c[i][j]=a[i][1]?b[1][j]+a[i][2]?b[2][j]+...+a[i][n]?b[n][j]，我們得到的即為以ai開頭，aj結尾的長度為3的序列個數！?
接下來用矩陣c更新矩陣a，再與最初的01矩陣，即b相乘，得到的又為開頭元素為ai，結尾元素為aj的長度為4的序列個數！?
依次乘k?1次即得到結果，這部分可以用矩陣快速冪進行優化。?
?

#include<bits/stdc++.h> using namespace std; const int maxn=101; const int mod=1000000007; struct node {int l;//行int r;//列long long a[maxn][maxn]; };node init(node a)//初始化矩陣 {for(int i=1;i<=a.r;i++)for(int j=1;j<=a.l;j++)a.a[i][j]=0;return a; }node mul(node a,node b)//矩陣乘法 {node c;c.l=a.l;c.r=b.r;for(int i=1;i<=c.l;i++)for(int j=1;j<=c.r;j++){c.a[i][j]=0;for(int k=1;k<=a.r;k++){c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%mod;}}return c; }node quickm(node a,int m)//矩陣快速冪 {int i=0;node b;b.l=b.r=a.l;b=init(b);for(int i = 1;i<=b.l;i++){b.a[i][i] = 1;}while(m){if(m&1)b=mul(b,a);a=mul(a,a);m>>=1;}return b; }int count(long long a)//統計a的二進制中1的個數 {int ans = 0;while(a){if(a & 1) ans++;a >>= 1;}return ans; }int main() {long long n,k,z[maxn];while(cin>>n>>k){for(int i=1;i<=n;i++){cin>>z[i];}node A;A.r=A.l=n;A=init(A);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(count(z[i]^z[j])%3==0){A.a[i][j]=1;}}long long ans=0;A=quickm(A,k-1);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){ans+=A.a[i][j];ans%=mod;}cout<<ans<<endl;}return 0; }

?

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的沉默是金 矩阵快速幂的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。