为什么60啊orz

#include<iostream>
#include<algorithm>
#include<cstdio> 
#include<cstring>
#include<vector>
using namespace std;

typedef long long ll;
ll f[85][25][1<<8], cnum[85][25];
int state[300], num[300];

bool check(int x){
    bool flag=false;
    while(x){
        if(!flag) flag=(x&1);
        else if(x&1) return false;
        x=x>>1;
    }
    return true;
}

bool check2(int x, int y){
    while(x&&y){
        if((x&1)&&(y&1)) return false;
        x=x>>1; y=y>>1;
    }
    return true;
}

int getnum(int x){
    int ret=0;
    while(x){
        if(x&1) ret++;
        x=x>>1;
    }
    return ret;
}

ll gcd(ll x, ll y){
    if(y==0) return x;
    return gcd(y, x%y);
}

ll c(ll x, ll y){
    if(y==0||x==y) return 1;
    if(x==0) return 0;
    if(cnum[x][y]!=-1) return cnum[x][y];
    return cnum[x][y]=c(x-1, y)+c(x-1, y-1);
}

int main(){
    int n, m, k, cnt=0; cin>>n>>m>>k;
    if(n>m) swap(n, m);
    if(k==0){ cout<<"1/1"<<endl; }
    int p=1<<n;
    f[0][0][0]=1;
    for(int i=0;i<p;i++) if(check(i)){ state[++cnt]=i; num[cnt]=getnum(i);  }
    for(int i=1;i<=m;i++)
        for(int l=1;l<=cnt;l++){
            f[i][num[l]][state[l]]=1;
            for(int j=num[l]+1;j<=k;j++)
                    for(int g=1;g<=cnt;g++)
                        if(check2(state[l], state[g]))
                                f[i][j][state[l]]+=f[i-1][j-num[l]][state[g]];
        }                   
    ll tot=0;
    for(int i=1;i<=cnt;i++) tot+=f[m][k][state[i]];
    if(!tot){ cout<<"Impossible!"<<endl; return 0; }
    memset(cnum, -1, sizeof(cnum));
    ll tmp=c(n*m, k);
    ll d=gcd(tot, tmp);
    tot/=d; tmp/=d;
    cout<<tmp<<'/'<<tot<<endl;
    return 0;
}

1 条评论

  • @ 2017-09-03 17:53:04

    好吧解决了

    #include<iostream>
    #include<algorithm>
    #include<cstdio> 
    #include<cstring>
    #include<vector>
    using namespace std;
    
    typedef long long ll;
    ll f[85][25][1<<8], cnum[85][25];
    int state[300], num[300];
    
    bool check(int x){
        while(x){
            if((x&3)==3) return false;
            x=x>>1;
        }
        return true;
    }
    
    bool check2(int x, int y){
        while(x&&y){
            if((x&1)&&(y&1)) return false;
            x=x>>1; y=y>>1;
        }
        return true;
    }
    
    int getnum(int x){
        int ret=0;
        while(x){
            if(x&1) ret++;
            x=x>>1;
        }
        return ret;
    }
    
    ll gcd(ll x, ll y){
        if(y==0) return x;
        return gcd(y, x%y);
    }
    
    ll c(ll x, ll y){
        if(y==0||x==y) return 1;
        if(x==0) return 0;
        if(cnum[x][y]!=-1) return cnum[x][y];
        return cnum[x][y]=c(x-1, y)+c(x-1, y-1);
    }
    
    int main(){
        int n, m, k, cnt=0; cin>>n>>m>>k;
        if(n>m) swap(n, m);
        if(k==0){ cout<<"1/1"<<endl; }
        int p=1<<n;
        f[0][0][0]=1;
        for(int i=0;i<p;i++) if(check(i)){ state[++cnt]=i; num[cnt]=getnum(i);  }
        for(int i=1;i<=m;i++)
            for(int l=1;l<=cnt;l++){
                f[i][num[l]][state[l]]=1;
                for(int j=num[l]+1;j<=k;j++)
                        for(int g=1;g<=cnt;g++)
                            if(check2(state[l], state[g]))
                                    f[i][j][state[l]]+=f[i-1][j-num[l]][state[g]];
            }                   
        ll tot=0;
        for(int i=1;i<=cnt;i++) tot+=f[m][k][state[i]];
        if(!tot){ cout<<"Impossible!"<<endl; return 0; }
        memset(cnum, -1, sizeof(cnum));
        ll tmp=c(n*m, k);
        ll d=gcd(tot, tmp);
        tot/=d; tmp/=d;
        cout<<tmp<<'/'<<tot<<endl;
        return 0;
    }
    
    
    
  • 1

信息

ID
1286
难度
6
分类
动态规划 | 状态压缩DP数论 | 欧几里得算法 点击显示
标签
(无)
递交数
592
已通过
149
通过率
25%
被复制
8
上传者