C++14(g++5.4) 解法, 执行用时: 401ms, 内存消耗: 356K, 提交时间: 2018-07-21 10:57:28

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
typedef long long ll;
const ll mod=1e9+7;
ll a[maxn+5];
char s[maxn+5];
map<ll,int> h;
int n,m;
ll base[60];
ll ans;
int main()
{
    base[0]=1;
    for(int i=1;i<60;++i) base[i]=base[i-1]*2%mod;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(a,0,sizeof(a));
        for(int i=0;i<n;++i)
        {
            scanf("%s",s+1);
            for(int j=1;j<=m;++j)
                if(s[j]=='1') a[j]|=1LL<<i;
        }
      //  printf("%lld %lld\n",a[1],a[2]);
        ans=0;
        for(int i=1;i<=m;++i)
        {
            h.clear();
            int t=n;
            for(int j=0;j<n;++j)
                if((1LL<<j)&a[i])
                {
                    t=j;
                    break;
                }
           // printf("%d\n",t);
            for(int j=1;j<=m;++j)
            {
                ll tmp=a[j];
                if(t<n&&((1LL<<t)&a[j])) tmp^=a[i];
                h[tmp]++;
            }
            //printf("%d %d\n",h[0],h[1]);
            ll s1=1LL*h[0]*h[0]%mod,s2=2LL*h[0]*(m-h[0])%mod,s3=1LL*(m-h[0])*(m-h[0])%mod;
            ll s0=0;
            for(auto x:h)
            {
                if(x.first==0) continue;
                s3=(s3-1LL*x.second*x.second%mod+mod)%mod;
                s2=s2+1LL*x.second*x.second%mod;
                s2%=mod;
            }
           // printf("%lld %lld %lld\n",s1,s2,s3);
           if(a[i]==0) s0=s1,s1=s2,s2=s3,s3=0;
            if(s3) ans=(ans+base[n-3]*s3%mod)%mod;
            if(s2) ans=(ans+base[n-2]*s2%mod)%mod;
            if(s1) ans=(ans+base[n-1]*s1%mod)%mod;
            if(s0) ans=(ans+base[n]*s0%mod)%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

C++ 解法, 执行用时: 45ms, 内存消耗: 564K, 提交时间: 2021-10-11 16:04:22

#include<bits/stdc++.h>
using namespace std;
const int mo=1e9+7;
int n,m,ans,cnt[4];
long long a[1005];
char s[55][1005];
map<long long,int>mp;
int ksm(int x,int y)
{
    int t=1;
    for (;y;y>>=1)
    {
        if (y&1) t=1ll*t*x%mo;
        x=1ll*x*x%mo;
    }
    return t;
}
int main()
{
    while (scanf("%d%d",&n,&m)!=EOF){
    for (int i=1;i<=n;i++) scanf("%s",s[i]+1);
    for (int i=1;i<=m;i++)
    {
        a[i]=0;
        for (int j=1;j<=n;j++) a[i]=a[i]*2+s[j][i]-'0';
    }
    sort(a+1,a+m+1);
    mp.clear();
    for (int i=1;i<=m;i++) mp[a[i]]++;
    memset(cnt,0,sizeof(cnt));
    cnt[3]=m*m*m;
    m=unique(a+1,a+m+1)-a-1;
    int p=mp[0];
    cnt[0]=p*p*p;
    for (int i=(p>0)+1;i<=m;i++)
    {
        int x=mp[a[i]]+p;
        cnt[1]+=x*x*x-cnt[0];
    }
    for (int i=(p>0)+1;i<=m;i++)
        for (int j=i+1;j<=m;j++)
        {
            int x=mp[a[i]],y=mp[a[j]];
            cnt[2]+=3*x*y*(x+y+p*2);
            long long z=a[i]^a[j];
            if (z<a[j]) continue;
            if (mp.count(z)) z=mp[z]; else z=0;
            cnt[2]+=6*x*y*z;
        }
    cnt[3]-=cnt[0]+cnt[1]+cnt[2];
    int tot=(cnt[3]+cnt[2]*2ll+cnt[1]*4ll+cnt[0]*8ll)%mo;
    ans=1ll*tot*ksm(2,mo+n-4)%mo;
    printf("%d\n",ans);
    }
    return 0;
}