全班隔離期望值＿遞迴code.cpp

#include <bits/stdc++.h>
#define ld long double
#define int long long int
#define IOS ios::sync_with_stdio(0),cout.tie(0)
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
bool table[8][8];
int n = 3,test[40],timer = 0;
int tp[30];
const ld full = pow(2,n*n);
fstream f;
set<int> st;
bitset<16> sss;

bool set_table(int s){
    memset(table,0,sizeof(table));
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            if(s % 2 == 1){
                table[i][j] = 1;
                for(int p = max(i-1,(int)1);p <= min(i+1,n);p++){
                    for(int q = max(j-1,(int)1);q <= min(j+1,n);q++){
                        table[p][q] = 1;
                    }
                }
            }
            s = s >> 1;
        }
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            if(!table[i][j])return 0;
        }
    }
    return 1;
}

int times(int s){
    int ans = 0;
    for(int i = 1;i <= (n*n);i++){
        if(s % 2)ans++;
        s = s >> 1;
    }
    return ans;
}

void print(int s){
    for(int i = 1;i <= (n*n);i++){
        cout<<s%2<<" ";
        s = s >> 1;
        if(i % 4 == 0)cout<<endl;
    }
    cout<<endl;
}

void dfs(int s,int id,bool pass){
    timer++;
    if(timer % 100000 == 0){
        cout<<"Processing: "<<(ld)timer / full<<endl;
    }
    if(id > (n*n))return;
    
    if(pass == 1 || set_table(s)){
        if(pass == 0 && set_table(s)){
            tp[times(s)] += 1;
            //print(s);
//            sss = s;
//            cout<<sss<<endl;
//            cout<<times(s)<<endl;
//            cout<<endl;
        }
        st.insert(s);
//        sss = s;
//        cout<<sss<<endl;
        dfs((s|(1<<id)),id+1,1);
        dfs((s),id+1,1);
        return;
    }
    dfs((s|(1<<id)),id+1,0);
    dfs((s),id+1,0);
    return;
}

signed main(){
    IOS;
    memset(table,0,sizeof(table));
    memset(tp,0,sizeof(tp));
    dfs(0,0,0);
    int total[100];memset(total,0,sizeof(total));
    cout<<st.size()<<endl;
    for(auto it = st.begin();it != st.end();it++){
        total[times(*it)] += 1;
    }
    for(int i = 1;i <= (n*n);i++)cout<<total[i]<<" ";
    cout<<endl;
    for(int i = 1;i <= (n*n);i++)cout<<i<<" ";
    cout<<endl<<endl;
    
    int temp = 0;
    for(int i = 1;i <= (n*n);i++){
        cout<<tp[i]<<" ";temp+=tp[i];
    }
    cout<<endl;
    ld posi = 0.0;
    for(int i = 1;i <= (n*n);i++){
        posi += i * ((ld)tp[i] / temp);
    }
    cout<<posi<<endl;
}