牛客练习赛19 托米看电影

标签 ： 状态压缩dp

---

题目链接

https://www.nowcoder.com/acm/contest/111/B

分析

• 用dp[i][j]来表示已经有i个人成功就坐,且坐下的状态为j的二进制.
• 转移的时候枚举第i个人卡片上的数字

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
using namespace std;
typedef long long ll;
ll dp[15][1<<16];
vector<int> v[20];
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
int main(){
    int t;
    scanf("%d", &t);
    for(int i = 0; i < (1<<15); ++i){
        int j=i,cnt=0;
        while(j) j-=(j&-j),cnt++;
        v[cnt].push_back(i);
    }
    while(t--){
        int n,k;
        scanf("%d%d", &n,&k);
        memset(dp,0,sizeof dp);
        dp[0][0]=1;
        for(int i = 0; i <= n; ++i){
            for(int j = 0; j < (1<<k); ++j){
                if(dp[i][j]==0) continue;
                for(int l = 1; l <= k; ++l){
                    for(int p = l-1; p < k; ++p){
                        if((j>>p)%2==0){
                            dp[i+1][j|(1<<p)]+=dp[i][j];
                            break;
                        }
                    }
                }
            }
        }
        ll sum=0;
        for(auto x:v[n]) sum+=dp[n][x];
        ll tot=1;
        for(int i = 0; i < n; ++i) tot*=k;
        sum=tot-sum;
        ll d=gcd(tot,sum);
        sum/=d;
        tot/=d;
        printf("%lld/%lld\n", sum,tot);
    }
    return 0;
}