题意

你需要在\([0,G-1]\)中选出\(n\)个不同的数,使它们异或起来等于\(0\),问有多少种不同的方案数;\(G\)是由一个二进制位小于等于\(50\)的二进制数\(S\)重复\(K\)次得到的.

题解

我们考虑选出的\(n\)个数\(A_i\)按从大到小排序,那么每次我们取出来的数是这样的:

\(G>A_n>A_{n-1}>A_{n-2}...>A_2>A_1\);

这样就能保证我们取的方案是不同的;

接下来考虑n个二进制长度为\(|S|\)的数该怎么取;

我们用一个\(01\)序列来表示当前\(n\)个数的大小关系比如\(10011\)表示\(G>A_5 \leq A_4 \leq A_3>A_2>A_1\);

现在我们考虑一位一位的得到这\(n\)个数的大小关系,已知当前位的大小关系时,只需要再枚举下一位\(n\)个数的二进制位,就能推出下一位的大小关系;

用\(F_{ij}\)表示当前大小关系状态\(i\)取\(|S|\)位后到状态\(j\)一共有多少种方式,于是我们便能用如上的状压递推的方式得到这个\(F\);

接下来的考虑取了\(i\)个\(|S|\)位大小关系是\(j\)时一共有多少种方案,因为每\(|S|\)个之间的转移是一样的,取\(i\)个\(|S|\)那么长实际上就是取\(F\)的\(i\)次方,能够使用矩阵快速幂快速得到;

复杂度 \(O(2^{n*3}*|S|+2^{n*3}*logk)\) ;

#include
    
     #define Fst first#define Snd second#define mem(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long LL;typedef unsigned int UI;typedef unsigned long long ULL;template
     
       inline void read(T& x) {    char c = getchar();    bool f = false;    for (x = 0; !isdigit(c); c = getchar()) {        if (c == '-') {            f = true;        }    }    for (; isdigit(c); c = getchar()) {        x = x * 10 + c - '0';    }    if (f) {        x = -x;    }}template
      
        inline void read(T& x, U& ... y) {    read(x), read(y...);}const int P=1e9+7;int n,K,len,LIM;int tmp[55],Next[1<<7][1<<7][55],F[55][1<<7];char S[55];struct Matrix {    int M[1<<7][1<<7];}Bas;typedef Matrix Mt;Mt operator *(Mt A,Mt B) {    Mt C;    for(int i=0;i
       
        >=1;    }    return res;}int cmp(int a,int b,int c) {    if(c) return 1;    if(a>b) return -1;    return a^b;}int main() {    read(n,K); scanf("%s",S+1); len=strlen(S+1);    LIM=1<
        
         >k&1,cnt+=tmp[k+1];            if((cnt&1)^1) {                for(int k=1;k<=len;++k) {                    int S1=0; bool OK=true; tmp[0]=S[k]-'0';                    for(int l=1;l<=n;++l) {                        int t=cmp(tmp[l],tmp[l-1],i>>(l-1)&1);                        if(~t) S1|=t<<(l-1);                        else {                            OK=false;                            break;                        }                    }                    if(OK) Next[i][j][k]=S1;                    else Next[i][j][k]=-1;                }            }            else for(int k=1;k<=len;++k) Next[i][j][k]=-1;        }    }    for(int i=0;i