首页 > 其他 > 详细

SRM 605 div 2 T3

时间:2018-09-01 19:56:29      阅读:184      评论:0      收藏:0      [点我收藏+]
#include <bits/stdc++.h>
#define Mo 1000000007
#define MAXN 50
#define MAXK 10
using namespace std;
int dp[2*MAXN+2][1<<MAXK];
class AlienAndSetDiv2 {
public:
    int N, K;
    int calc(int n, int unmatched)
    {
        int res = 0;
        if (-1 != dp[n][unmatched]) {
            return dp[n][unmatched];
        }
 
        if (n == 2 * N + 1) {
            if (0 == unmatched) {
                res = 1;
            }
        } else {
            if (0 == unmatched) {
                res += ( 2 * calc(n + 1, 1) ) % Mo;
            } else {
                int newset = unmatched;
                int i = 0;
                for (i = 0; (newset & 0x80000000 ) == 0; newset = ( newset << 1 ), ++i) {
                }
                int mx = 31 - i;
                res += calc(n + 1,  (unmatched - (1 << mx)) << 1 );    
                res %= Mo;
 
                if (mx != K - 1) {
                    newset = unmatched;
                    newset = ( (newset << 1) | 1 );
                    res += calc(n + 1, newset);
                    res %= Mo;
                }
            }    
        }
        dp[n][unmatched] = res;
        return res;
    }

 

SRM 605 div 2 T3

原文:https://www.cnblogs.com/wjnclln/p/9571318.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!