首页 > ACM题库 > HDU-杭电 > HDU 4376-Simple Counting[解题报告]HOJ
2015
05-24

HDU 4376-Simple Counting[解题报告]HOJ

Simple Counting

问题描述 :

  Totalfrank and wlkilluajay have their lucky numbers. As we all know, 16 or any number contains 16 (116 for example) is lucky number for totalfrank and 2 or any number contains 2 (1723 for example) is lucky number for wlkilluajay.
  Totalfrank is a normal guy who reads from left to right while wlkilluajay enjoys reading from right to left which means 16 to totalfrank is 61 to wlkilluajay.
  Since their lucky numbers changes often, here is the simple counting question for you: given totalfrank’s and wlkilluajay’s lucky number and an interval, how many numbers in the given interval is at least a lucky number for one of them? Notice that wlkilluajay always read from right to left so a number which is outside the interval (in totalfrank’s perspective) may be inside the interval when it is read from right to left (in wlkilluajay’s perspective), you should also count that in (See samples for more details). By the way, because they read from different direction, 0 may be a problem (for example, if 2 is a lucky number for wlkilluajay, then 20, 200… is also a lucky number for her. But when read from right to left, they are all just 2 and there may be infinite lucky numbers for her in a given interval in a normal guy’s eyes). From this aspect, they decide to ignore any number contains 0.

输入:

The input contains no more than 50 test cases.
The first line contains a single integer T indicating the number of test cases.
For each test case:
  The first line of each test case includes two integers a (1 <= a <= 1018) and b (a <= b <= 1018).
  The second line contains two integers c (1 <= c <= 1018) and d (1 <= d <= 1018). c is the lucky number for totalfrank and d is the lucky number for wlkilluajay (c and d won’t contain any 0).

输出:

The input contains no more than 50 test cases.
The first line contains a single integer T indicating the number of test cases.
For each test case:
  The first line of each test case includes two integers a (1 <= a <= 1018) and b (a <= b <= 1018).
  The second line contains two integers c (1 <= c <= 1018) and d (1 <= d <= 1018). c is the lucky number for totalfrank and d is the lucky number for wlkilluajay (c and d won’t contain any 0).

样例输入:

2

62 62
62 62

1 9999
53 23

样例输出:

Case #1: 2
Case #2: 501
Hint
For the first case, 62 is a lucky number for totalfrank and 26 is a lucky number for wlkilluajay (when read from right to left, it is 62 which fills in the interval [62, 62]).So the answer is 2 (26 and 62).

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define MAXL 22
#define KIND 9
#define MAXNODE 42

typedef long long LL;

vector<int> A, B, RA, RB;
char subA[MAXL], subB[MAXL];
int N, end[MAXNODE], suffix[MAXNODE], q[MAXNODE], child[MAXNODE][KIND];
LL dp[MAXL][3][3][3][3][MAXNODE][1 << 2];

int change(char ch) {
	return ch - '1';
}

void Trie() {
    memset(end, 0, sizeof(end));
    memset(child, 0, sizeof(child));
    N = 1;
    for(int i = 0; i < 2; ++i) {
    	char* s = i == 0? subA: subB;
        int p = 1;
        for (int j = 0; s[j]; ++j) {
            int ch = change(s[j]);
            if (!child[p][ch]) child[p][ch] = ++N;
            p = child[p][ch];
        }
        end[p] |= 1 << i;
    }
}

void AC() {
    int ql = 0, qr = 0;
    for (int i = 0; i < KIND; ++i)
        if (child[1][i]) {
            suffix[child[1][i]] = 1;
            q[qr++] = child[1][i];
        }
        else child[1][i] = 1;
    while (ql < qr) {
        int u = q[ql++];
        for (int i = 0; i < KIND; ++i)
            if (child[u][i]) {
                suffix[child[u][i]] = child[suffix[u]][i];
                q[qr++] = child[u][i];
            }
            else child[u][i] = child[suffix[u]][i];
    }
    for (int i = 1; i <= N; ++i)
        for (int j = i; j != 1; j = suffix[j]) end[i] |= end[j];
}

int cal1(int pos, int val, int pre, vector<int>& vec) {
	if(pos >= vec.size()) return 2;
	if(pre != 0) return pre;
	if(val > vec[pos]) return 2;
	if(val < vec[pos]) return 1;
	return 0;
}

int cal2(int pos, int val, int pre, vector<int>& vec) {
	if(pos >= vec.size()) return 2;
	if(val > vec[pos]) return 2;
	if(val < vec[pos]) return 1;
	return pre;
}

int main() {
//	freopen("data.in", "r", stdin);
//	freopen("data.out", "w", stdout);
	int T;
	scanf("%d", &T);
	for(int cas = 1; cas <= T; ++cas) {
		LL a, b;
		cin >> a >> b;
		scanf("%s%s", subA, subB);

		LL sub = 0, rsub = 0;
		for(int i = 0; subA[i]; ++i)
			sub = sub * 10 + subA[i] - '0';
		for(int i = 0; subB[i]; ++i)
			rsub = rsub * 10 + subB[i] - '0';
		reverse(subB, subB + strlen(subB));

		Trie();
		AC();

		A.clear();
		B.clear();
		RA.clear();
		RB.clear();
		LL ta = a, tb = b;
		while(ta) {
			RA.push_back(ta % 10);
			ta /= 10;
		}
		while(tb) {
			RB.push_back(tb % 10);
			tb /= 10;
		}
		A = RA;
		B = RB;
		reverse(A.begin(), A.end());
		reverse(B.begin(), B.end());

		int l = B.size();
		memset(dp, 0, sizeof(dp));
		for(int j = 1; j < 10; ++j) {
			int s1 = cal1(0, j, 0, A);
			int s2 = cal1(0, j, 0, B);
			int rs1 = cal2(0, j, 0, RA);
			int rs2 = cal2(0, j, 0, RB);
			int v = child[1][j - 1];
			++dp[0][s1][s2][rs1][rs2][v][end[v]];
		}

		for(int i = 0; i + 1 < l; ++i) {
			for(int s1 = 0; s1 < 3; ++s1) for(int s2 = 0; s2 < 3; ++s2) for(int rs1 = 0; rs1 < 3; ++rs1) for(int rs2 = 0; rs2 < 3; ++rs2)
				for(int u = 1; u <= N; ++u)
					for(int mask = 0; mask < (1 << 2); ++mask) if(dp[i][s1][s2][rs1][rs2][u][mask]) {
						for(int val = 1; val < 10; ++val) {
							int ns1 = cal1(i + 1, val, s1, A);
							int ns2 = cal1(i + 1, val, s2, B);
							int nrs1 = cal2(i + 1, val, rs1, RA);
							int nrs2 = cal2(i + 1, val, rs2, RB);
							int v = child[u][val - 1];
							dp[i + 1][ns1][ns2][nrs1][nrs2][v][mask | end[v]] += dp[i][s1][s2][rs1][rs2][u][mask];
						}
					}
		}

		LL res = 0;
		int la = A.size(), lb = B.size();
		for(int len = la; len < lb - 1; ++len) {
			for(int s1 = 0; s1 < 3; ++s1) for(int s2 = 0; s2 < 3; ++s2) for(int rs1 = 0; rs1 < 3; ++rs1) for(int rs2 = 0; rs2 < 3; ++rs2)
				for(int u = 1; u <= N; ++u)
					for(int mask = 1; mask < (1 << 2); ++mask)
						res += dp[len][s1][s2][rs1][rs2][u][mask];
		}

		if(la != lb) {
			for(int s1 = 0; s1 < 3; ++s1) for(int s2 = 0; s2 < 3; ++s2) for(int rs1 = 0; rs1 < 3; ++rs1) for(int rs2 = 0; rs2 < 3; ++rs2)
				for(int u = 1; u <= N; ++u)
					for(int mask = 1; mask < (1 << 2); ++mask) {
						bool flaga = false;
						if(mask == 1 || mask == 3) {
							if(s1 == 0 || s1 == 2) flaga = true;
						}
						if(mask == 2 || mask == 3) {
							if(rs1 == 0 || rs1 == 2) flaga = true;
						}
						if(flaga)
							res += dp[la - 1][s1][s2][rs1][rs2][u][mask];
						bool flagb = false;
						if(mask == 1 || mask == 3) {
							if(s2 == 0 || s2 == 1) flagb = true;
						}
						if(mask == 2 || mask == 3) {
							if(rs2 == 0 || rs2 == 1) flagb = true;
						}
						if(flagb)
							res += dp[lb - 1][s1][s2][rs1][rs2][u][mask];
					}
		} else {
			for(int s1 = 0; s1 < 3; ++s1) for(int s2 = 0; s2 < 3; ++s2) for(int rs1 = 0; rs1 < 3; ++rs1) for(int rs2 = 0; rs2 < 3; ++rs2)
				for(int u = 1; u <= N; ++u)
					for(int mask = 1; mask < (1 << 2); ++mask) {
						bool flag = false;
						if(mask == 1 || mask == 3) {
							if((s1 == 0 || s1 == 2) && (s2 == 0 || s2 == 1)) flag = true;
						}
						if(mask == 2 || mask == 3) {
							if((rs1 == 0 || rs1 == 2) && (rs2 == 0 || rs2 == 1)) flag = true;
						}
						if(flag) res += dp[la - 1][s1][s2][rs1][rs2][u][mask];
					}
		}
		printf("Case #%d: ", cas);
		cout << res << endl;
	}
	return 0;
}