萌新求助容斥+线性基入门题。
查看原帖
萌新求助容斥+线性基入门题。
455490
Sharpsmile楼主2024/9/6 10:16

获得了0分高分,输出容斥系数貌似是对的,但是看了很久也不知道哪里错了qwq

#include <bits/stdc++.h>
#define pii pair<int,int>
#define p1(x) x.first
#define p2(x) x.second
#define endl "\n"
using namespace std;
#define int long long
int f[11];
int S[11][11];
int n,s;
string p[61];
int bel[11],ct;
struct LB{
    int n,siz;
    int w[61];
    inline void ins(int x){
        for(int i=n-1;i>=0;i--)
        if((x>>i)&1){
            if(w[i])x^=w[i];
            else{
                w[i]=x;
                siz++;
                return ;
            }
        }
    }
    inline void clr(){
        n=siz=0;
        memset(w,0,sizeof(w));
    }
}A;
int a[61];
inline int calc(){
    A.clr(); 
    int loc=0;
    for(int i=0;i<n;i++)    
        for(int j=i+1;j<n;j++){
            if(bel[i]!=bel[j]){
                for(int k=1;k<=s;k++)
                    if(p[k][loc]=='1')a[k]|=1<<A.n;
                    A.n++;
            }
            loc++;
        }
    for(int i=1;i<=s;i++)
        A.ins(a[i]);
    return (1ll<<s-A.siz);
}   
__int128_t res=0;
inline void dfs(int S){
    if(!S){
        res+=(__int128_t)calc()*f[ct];
        return ;
    }
    ct++;
    int lst=0;
    for(int i=0;i<n;i++)
    if((S>>i)&1){lst=i;break;}
    S^=1<<lst;
    bel[lst]=ct;
    for(int T=S;;T=(T-1)&S){
        for(int j=0;j<n;j++)
        if((T>>j)&1)bel[j]=ct;
        dfs(S^T);
        if(T==0)break;
    }
    ct--;
}
inline void prt(__int128_t x){
    stack<int>S;
    while(x)S.push(x%10),x/=10;
    while(!S.empty())cout<<S.top(),S.pop();
}
signed main(){
    ios::sync_with_stdio(0);
    // freopen("genshin.in","r",stdin);
    // freopen("genshin.out","w",stdout);
    cin>>s;
    for(int i=1;i<=s;i++)
    cin>>p[i];
    while(n*(n-1)/2<p[1].size())n++;
    S[0][0]=1;
    for(int i=1;i<=10;i++)
    for(int j=1;j<=i;j++)
    S[i][j]=S[i-1][j-1]+j*S[i-1][j];

    for(int i=1;i<=10;i++){
        int r=i==1;
        for(int j=1;j<i;j++)
            r-=f[j]*S[i][j];
        f[i]=r/S[i][i];
    }
    dfs((1<<n)-1);
    prt(res);

    cout.flush();
    fflush(stdout);
    return 0;
}
2024/9/6 10:16
加载中...