Bitmask DP

hats wearing

if (j & (1<<val)) {
	    // i th of hat, j ranges from 0~2^10
        dp[i][j] = (dp[i-1][j-(1<<val)]+dp[i][j])%(MOD); 
}
const int MOD = 1e9+7;
class Solution {
public:
    int numberWays(vector<vector<int>>& people) {
        vector<vector<int>> hats;
        map<int, vector<int>> mp;
        for (int i = 0; i < people.size(); ++i) {
            for (int j:people[i])
                mp[j].push_back(i);
        }
        for (int i = 1; i <= 40; ++i) {
            if (mp.count(i)) {
                sort(mp[i].begin(), mp[i].end());
                hats.push_back(mp[i]);
            }
        }
        int h = hats.size();
        int p = people.size();
        long long dp[42][(1<<10)+5];
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for (int i = 1; i <= h; ++i) {
            for (int j = 0; j < (1<<p); ++j) {
                for (int k = 0; k < hats[i-1].size(); ++k) {
                    int val = hats[i-1][k];
                    if (j & (1<<val)) {
                       		/* j-(1<<val) == j^(1<<val)*/
                            dp[i][j] = (dp[i-1][j^(1<<val)]+dp[i][j])%(MOD);
                    }
                }
                dp[i][j] = (dp[i][j]+dp[i-1][j]) % MOD;
            }
        }
        return dp[h][(1<<p)-1];
    }
};

Digit DP

不要62

  1. Simple solution: brutal force, we can use c++ library to help us identify which number contains ‘4’ or ‘62’.
  2. Fast solution: digit dp (illustrate the process by an example)
    • To get the answer from this interval [0, 456]
    • we use dp(i)(j) to record calculated interval, like 0~99, 0~999, 0~9999, 0~99999…, which can dramatically save the time consumption. The first one (i) means the total digits of the upper bound, the second (j) one means whether the digit before the highest digit of this number is six. (if it is six, then this digit can not be ‘2’).
    • Now we calculate [0,456]. the highest digit of this number is 4. there is no digit before; and this interval is not recorded in dp, so we need to divide this to a smaller problem. we divide it to interval [0, 099], [100, 199], [200, 299], [300, 399], [400, 456].
    • We move to the lower digit from the highest digit ‘4’, we can see the first 4 intervals have the the same answers, since they all contain the interval [0, 99].
    • For the fifth interval [0, 56] (move to a lower digit). We can use dfs to deal with this subproblem.
    • See the comment in code-2 for more details.
// Simple solution  time consumption: 432 ms
const int maxn=1e6+5;
char a[]="4",b[]="62";
int s[maxn];
char str[8];
void init(){
    for (int i=1; i<1e6; i++) {
        sprintf(str,"%d",i);
        if (strstr(str, a)!=NULL||strstr(str, b)!=NULL) s[i]=0;
        else s[i]=1;
    }
}
int main(){
    init();
    int m,n;
    while (scanf("%d%d",&m,&n)==2&&(m||n)) {
        int sum=0;
        for (int i=m; i<=n; i++) {
            sum+=s[i];
        }
        printf("%d\n",sum);
    }
    return 0;
}
// digit dp  
//time consumption: 15 ms
int num[10];
int d[10][2];
/* limit indicates whether this interval is like 0~99..9 */
/* cur marks which digit it is now processed */
int dfs(int cur,bool wassix,bool limit){
    int ans=0;
    if(cur==0) return 1;//cur=0 indicates the end of recursion
    /* have we calculated the interval before ? */
    if(!limit&&d[cur][wassix]!=-1) 
        return d[cur][wassix];
    int maxnum=limit==0?9:num[cur];
    /* divide to subproblems */
    for (int i=0; i<=maxnum; i++) {
        /* not-ok */
        if(i==4||(i==2&&wassix)) continue;
        /* move to a lower digit, was six ?,  a limit ?*/
        else ans += dfs(cur-1, i==6, i==maxnum&&limit);
    }
    if(limit==0) d[cur][wassix]=ans;
    return ans;
}
int cal(int n){
    int len=0;
    while (n) {
        num[++len]=n%10;
        n/=10;
    }
    return dfs(len,0,1);
}
int main(){
    int m,n;
    memset(d, -1, sizeof(d));
    while (scanf("%d%d",&m,&n)==2&&(m||n)) {
        printf("%d\n",cal(n)-cal(m-1));//注意是m-1
    }
    return 0;
}

XHXJ s LIS

/*
http://acm.hdu.edu.cn/showproblem.php?pid=4352
XHXJ's LIS

LIS + bitmask dp + digit dp
*/
#define ll long long
#define ull unsigned long long

using namespace std;

const int MOD = 1e9+7;
// const int INF = 0x7fffffff;
const int INF = 0x3f3f3f3f;
const int PI = acos(-1.0);

ll L, R, K;
int num[20];
ll dp[20][(1<<10)+5][15];

int decode(int status) {
    int ans = 0;
    while (status) {
        if (status&1) ans++;
        status >>= 1;
    }
    return ans;
}

int encode(int x, int status) { // O(nlogn) LIS solution
    for (int i = x; i < 10; ++i) {
        if (status & (1<<i)) return (status^(1<<i)) | (1<<x); // replace i with x; the pos(i) >= pos(x)
    }
    return status | (1<<x);
}

ll dfs(int pos, int status, int isub, int iszero) {
    if (pos == 0)
        return decode(status)==K; // decode the status to see if it is satisfied
    if (!isub && dp[pos][status][K]!=-1)  // return stored dp value ?
        return dp[pos][status][K];
    int mx = isub==0 ? 9:num[pos];
    ll ans = 0;
    for (int i = 0; i <= mx; ++i) {
        // is the former digits are all zero ? does it have upper bound ? the status transformation ?
        ans += dfs(pos-1, (i==0&&iszero) ? 0:encode(i, status), isub&&i==mx, iszero&&i==0);
    }
    if (!isub) dp[pos][status][K] = ans;
    return ans;
}

ll cal(long long val) {
    int len = 0;
    while (val) {
        num[++len] = val%10;
        val /= 10;
    }
    return dfs(len, 0, 1, 1);
}

int main() {
    int t;
    scanf("%d", &t);
    int kase = 0;
    memset(dp, -1, sizeof(dp));
    while (t--) {
        scanf("%lld%lld%lld", &L, &R, &K);
        printf("Case #%d: %lld\n", ++kase, cal(R)-cal(L-1));
    }
	return 0;
}

Round Numbers


/*
POJ 3252
Round Numbers
*/
#define ll long long
#define ull unsigned long long

using namespace std;

const int MOD = 1e9+7;
// const int INF = 0x7fffffff;
const int INF = 0x3f3f3f3f;
const int PI = acos(-1.0);

const int offset = 35;
ll L, R;
int num[35];
ll dp[35][70][2]; // the last dimension is to identify whether the digits before are all zero

ll dfs(int pos, bool waszero, bool isup, int zeros) {
    ll ans = 0;
    // special case for '0' and '1'
    if (pos==1 && waszero && (isup==0||num[pos]==1)) return 0;
    if (pos==0) return (zeros>=0) ? 1:0;
    if (!isup && dp[pos][zeros+offset][waszero]!=-1) return dp[pos][zeros+offset][waszero];
    int mx = isup ? num[pos]:1;
    for (int i = 0; i <= mx; ++i) {
        ans += dfs(pos-1, i==0&&waszero, i==mx&&isup, (i==0&&waszero)==1 ? 0:(zeros-(i==0 ? -1:1)));
    }
    if (!isup) dp[pos][zeros+offset][waszero] = ans;
    return ans;
}

ll cal(long long val) {
    if (val == 0) return 0;
    int len = 0;
    while (val) {
        num[++len] = val%2;
        val >>= 1;
    }
    return dfs(len, 1, 1, 0);
}

int main() {
    memset(dp, -1, sizeof(dp));
    while (scanf("%lld%lld", &L, &R)==2) {
        printf("%lld\n", cal(R)-cal(L-1));
    }
	return 0;
}

Balanced number

ll L, R;
int num[30];
ll dp[20][20][2000];

ll dfs(int pos, int pre, int pivot, bool isup) {
    ll ans = 0;
    if (pre < 0) return 0; // cut this branch!
    if (pos == 0) return pre==0; // is this number balanced ?
    if (dp[pos][pivot][pre]!=-1 && !isup) return dp[pos][pivot][pre];
    int end = isup ? num[pos]:9;
    for (int i = 0; i <= end; ++i) {
        ans += dfs(pos-1, pre+(pos-pivot)*i, pivot, isup && i==end); // calculate weight!
    }
    if (!isup) dp[pos][pivot][pre] = ans;
    return ans;
}

ll cal(long long val) {
    if (val < 0) return 0;
    int len = 0;
    while (val) {
        num[++len] = val%10;
        val /= 10;
    }
    num[0] = 0;
    ll ans = 0;
    for (int i = len; i > 0; --i) { // to select each position as the pivot
        ans += dfs(len, 0, i, 1);
    }
    return ans-(len-1); // 0, 00, 000 this kind of value are calculated more than one times!
}

int main() {
    memset(dp, -1, sizeof(dp));
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld", &L, &R);
        printf("%lld\n", cal(R)-cal(L-1));
    }
	return 0;
}

B-number

#define ll long long
#define ull unsigned long long

using namespace std;

const int MOD = 1e9+7;
// const int INF = 0x7fffffff;
const int INF = 0x3f3f3f3f;
const int PI = acos(-1.0);

ll L, R;
int len;
int num[20];
/* represent the status: which position, is the previous digit one ? 
   is the the digits before contain '13'? the mod of 13 of the previous number
*/
ll dp[15][2][2][15];

ll dfs(int pos, bool wasone, bool isup, bool ok, int m) {
    ll ans = 0;
    if (pos == 0 && ok) {
        return m==0;
    } else if (pos == 0) return 0;
    if (!isup && dp[pos][wasone][ok][m]!=-1) return dp[pos][wasone][ok][m];
    int end = isup ? num[pos]:9;
    // cout << "end: " << end << endl;
    for (int i = 0; i <= end; ++i) {
        ans += dfs(pos-1, i==1, isup&&i==end, (wasone&&i==3)||(ok), (m*10+i)%13);
    }
    if (!isup) dp[pos][wasone][ok][m] = ans;
    return ans;
}

ll cal(long long val) {
    len = 0;
    while (val) {
        num[++len] = val%10;
        val /= 10;
    }
    num[0] = 0;
    ll ans = 0;
    return dfs(len, 0, 1, 0, 0);
}

int main() {
    memset(dp, -1, sizeof(dp));
    while (scanf("%lld", &R) != EOF) {
        printf("%lld\n", cal(R));
    }
	return 0;
}

Similar problems