列表

详情

NC20222. [JSOI2016]位运算

描述

JYY最近在研究位运算。他发现位运算中最有趣的就是异或（xor）运算。对于两个数的异或运算，JYY发现了一个结论：两个数的异或值为0当且仅当他们相等。于是JYY又开始思考，对于N个数的异或值会有什么性质呢？
【问题描述】
JYY想知道，如果在0到R-1的范围内，选出N个不同的整数，并使得这N个整数的异或值为0，那么一共有多少种选择的方法呢？（选择的不同次序并不作重复统计，请参见样例）
JYY是一个计算机科学家，所以他脑海里的R非常非常大。为了能够方便的表达，如果我们将R写成一个0-1串，那么R是由一个较短的0-1串S重复K次得到的。
比如，若S=“101”，K=2，那么R的2进制表示则为“101101”。由于计算的结果会非常大，JYY只需要你告诉他选择的总数对10^9+7取模的结果即可

输入描述

第一行包含两个正整数N和K。
接下来一行包含一个由0和1组成的字符串S。
我们保证S的第一个字符一定为1。

输出描述

一行一个整数，表示选择的方案数对10^9+7取模的值。

示例1

输入: 

3 1
100

输出: 

1

说明:

对于第一个样例， 唯一的一种选择方法是选择 {1, 2, 3}。

原站题解

import java.util.Scanner;
public class Main {
public static void main(String[] arg) {
Scanner scanner = new Scanner(System.in);
// todo
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

C++11(clang++ 3.9) 解法, 执行用时: 481ms, 内存消耗: 1128K, 提交时间: 2019-03-16 12:57:37 

#include<cstdio>

#include<cstring>

#include<algorithm>

#define mo 1000000007

using namespace std;

int n,k;

char s[1000];

struct mat{

    int m[130][130];

    mat(){

        for (int i=0;i<(1<<n);i++)

            for (int j=0;j<(1<<n);j++)

                m[i][j]=0;

    }

} a[2];

mat mul(mat a,mat b){

    mat re;

    for (int i=0;i<(1<<n);i++)

        for (int j=0;j<(1<<n);j++)

            for (int k=0;k<(1<<n);k++){

                re.m[i][j]+=1ll*a.m[i][k]*b.m[k][j]%mo;

                if (re.m[i][j]>=mo) re.m[i][j]-=mo;

            }

    return re;

}

int main(){

    scanf("%d%d%s",&n,&k,&s);int len=strlen(s);

    

    for (int zt=0;zt<(1<<n);zt++){

        for (int zy=0;zy<(1<<n);zy++){

            int td=0;

            for (int i=1;i<=n;i++) if (zy&(1<<(i-1))) td++;

            if (td&1) continue;



            if (zt&1){

                int ha=0;

                for (int i=n;i;i--){

                    if (zy&(1<<(i-1))) ha=1;

                    if (zt&(1<<(i-1))) break;

                }

                if (ha) continue;

            }

            

            td=0;

            for (int i=1;i<n;i++) if ((zy&(1<<(i-1)))&&!(zy&(1<<i))){

                if (!(zt&(1<<i))) td=1;

            }

            if (td) continue;

    

            int go=zt;

            for (int i=1;i<n;i++) if (!(zy&(1<<(i-1)))&&(zy&(1<<i)))

                go|=(1<<i);

            a[0].m[go][zt]++;

        }

    }



    for (int zt=0;zt<(1<<n);zt++){

        for (int zy=0;zy<(1<<n);zy++){

            int td=0;

            for (int i=1;i<=n;i++) if (zy&(1<<(i-1))) td++;

            if (td&1) continue;



            int ha=0;

            for (int i=n;i;i--){

                if (zy&(1<<(i-1))) ha=1;

                if (zt&(1<<(i-1))) break;

            }

            

            td=0;

            for (int i=1;i<n;i++) if ((zy&(1<<(i-1)))&&!(zy&(1<<i))){

                if (!(zt&(1<<i))) td=1;

            }

            if (td) continue;

    

            int go=zt;

            for (int i=1;i<n;i++) if (!(zy&(1<<(i-1)))&&(zy&(1<<i)))

                go|=(1<<i);

            if (!ha&&(go&1)) go^=1;

            a[1].m[go][zt]++;

        }

    }

    

    mat td,ret,lj,init;

    for (int i=0;i<(1<<n);i++) td.m[i][i]=ret.m[i][i]=1;

    for (int i=0;i<len;i++) td=mul(a[s[i]-'0'],td);

    for (lj=td;k;k/=2,lj=mul(lj,lj)) if (k&1)

        ret=mul(ret,lj);

    init.m[1][0]=1;

    ret=mul(ret,init);

    printf("%d\n",ret.m[(1<<n)-2][0]);

}

C++14(g++5.4) 解法, 执行用时: 462ms, 内存消耗: 740K, 提交时间: 2020-06-09 14:23:42 

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 7

#define S 50

#define X 1000000007

#define Inc(x,y) ((x+=(y))>=X&&(x-=X))

using namespace std;

int l,n,K,lim,op[1<<N],f[S+5][1<<N];char s[S+5];

struct M

{

    int a[1<<N][1<<N];I M() {memset(a,0,sizeof(a));}

    I int *operator [] (CI x) {return a[x];}

    I M operator * (Con M& o) Con

    {

        RI i,j,k;M t;for(i=0;i^lim;++i) for(j=0;j^lim;++j)

            for(k=0;k^lim;++k) t[i][j]=(1LL*a[i][k]*o.a[k][j]+t[i][j])%X;return t;

    }

    I M operator ^ (RI y) Con

    {

        M x=*this,t;for(RI i=0;i^lim;++i) t[i][i]=1;W(y) y&1&&(t=t*x,0),x=x*x,y>>=1;return t;

    }

}U;

I int T(CI p,CI k,CI s)

{

    RI i,x,y,t=0;for(i=n-1;i;--i) if(p>>i&1)

        {if((x=(k>>i)&1)>(y=(k>>i-1)&1)) return -1;x==y&&(t|=1<<i);}

    if(p&1) {if((x=k&1)>s) return -1;x==s&&(t|=1);}return t;

}

int main()

{

    RI i,j,k,t;scanf("%d%d%s",&n,&K,s+1),l=strlen(s+1);

    for(lim=1<<n,op[0]=i=1;i^lim;++i) op[i]=op[i>>1]^(i&1);

    for(RI w=0;w^lim;++w)

    {

        memset(f,0,sizeof(f)),f[0][w]=1;

        for(i=1;i<=l;++i) for(j=0;j^lim;++j) if(f[i-1][j])

            for(k=0;k^lim;++k) op[k]&&~(t=T(j,k,s[i]&1))&&Inc(f[i][t],f[i-1][j]);

        for(i=0;i^lim;++i) U[w][i]=f[l][i];

    }return printf("%d",(U^K)[lim-1][0]),0;

}

上一题

© 2025 nowcoder.com