Run Time: 0.006
Ranking (as of 2016-01-03): 11 out of 453
Language: C++
/*
UVa 11472 - Beautiful Numbers
To build using Visual Studio 2012:
cl -EHsc -O2 UVa_11472_Beautiful_Numbers.cpp
*/
#include <cstdio>
const int N_max = 10, M_max = 100, mask_max = 1 << N_max, divisor = 1000000007;
int nrs[M_max + 1][N_max][mask_max];
// [number of digits][lastdigit used][mask of used digits]
int main()
{
for (int n = 1; n < N_max; n++)
nrs[1][n][1 << n] = 1;
for (int m = 2; m <= M_max; m++) {
for (int i = 1; i < mask_max; i++)
nrs[m][1][i | 1] = nrs[m - 1][0][i];
for (int n = 1; n < N_max - 1; n++)
for (int i = 1; i < mask_max; i++) {
nrs[m][n - 1][i | 1 << (n - 1)] += nrs[m - 1][n][i];
nrs[m][n - 1][i | 1 << (n - 1)] %= divisor;
nrs[m][n + 1][i | 1 << (n + 1)] += nrs[m - 1][n][i];
nrs[m][n + 1][i | 1 << (n + 1)] %= divisor;
}
for (int i = 1; i < mask_max; i++) {
nrs[m][N_max - 2][i | 1 << (N_max - 2)] += nrs[m - 1][N_max - 1][i];
nrs[m][N_max - 2][i | 1 << (N_max - 2)] %= divisor;
}
}
int T;
scanf("%d", &T);
while (T--) {
int N, M;
scanf("%d %d", &N, &M);
int mask = 1 << N, nr = 0;
for (int m = 2; m <= M; m++)
for (int n = 0; n < N; n++) {
nr += nrs[m][n][mask - 1];
nr %= divisor;
}
printf("%d\n", nr);
}
return 0;
}
Can You Share The Idea to solve this Problem ?
ReplyDeleteI got a hint from
ReplyDeletehttps://uva.onlinejudge.org/board/viewtopic.php?f=42&t=71043
that says:
I also used an O(2^N * N * M) solution.
My state is dp[length][used digits][first digit],
where dp[i][j][k] = number of ways to form a number with i digits,
such that the first digit is k and j is a bitwise mask indicating which digits I have used.
This method took 1 second (slow!) using memoization.
And, to get an idea of recurrence relation,
wrote down [number of digits][lastdigit used][mask of used digits] for N = 3, M = 1 - 5, like below.
Here, the lines starting with '+' are valid beautiful numbers, while the lines starting with '-' are not.
M:1
0
[1][0][001]:0
1
[1][1][010]
2
[1][2][100]
M:2
01 = 0 + 1
[2][1][011] = [1][0][001]
10 = 1 + 0
[2][0][011] = [1][1][010]
12 = 1 + 2
[2][2][110] = [1][1][010]
21 = 2 + 1
[2][1][110] = [1][2][100]
M:3
010 = 01 + 0
[3][0][011] = [2][1][011]
- 012 = 01 + 2
[3][2][111] = [2][1][011]
101 = 10 + 1
[3][1][011] = [2][0][011]
121 = 12 + 1
[3][1][110] = [2][2][110]
+ 210 = 21 + 0
[3][0][111] = [2][1][110]
212 = 21 + 2
[3][2][110] = [2][1][110]
M:4
0101 = 010 + 1
[4][1][011] = [3][0][011]
- 0121 = 012 + 1
[4][1][111] = [3][2][111]
1010 = 101 + 0
[4][0][011] = [3][1][011]
+ 1012 = 101 + 2
[4][2][111] = [3][1][011]
+ 1210 = 121 + 0
[4][0][111] = [3][1][110]
1212 = 121 + 2
[4][2][110] = [3][1][110]
+ 2101 = 210 + 1
[4][1][111] = [3][0][111]
2121 = 212 + 1
[4][1][110] = [3][2][110]
M:5
01010 = 0101 + 0
[5][0][011] = [4][1][011]
- 01012 = 0101 + 2
[5][2][111] = [4][1][011]
- 01210 = 0121 + 0
[5][0][111] = [4][1][111]
- 01212 = 0121 + 2
[5][2][111] = [4][1][111]
10101 = 1010 + 1
[5][1][011] = [4][0][011]
+ 10121 = 1012 + 1
[5][1][111] = [4][2][111]
+ 12101 = 1210 + 1
[5][1][111] = [4][0][111]
12121 = 1212 + 1
[5][1][110] = [4][2][110]
+ 21010 = 2101 + 0
[5][0][111] = [4][1][111]
+ 21012 = 2101 + 2
[5][2][111] = [4][1][111]
+ 21210 = 2121 + 0
[5][0][111] = [4][1][110]
21212 = 2121 + 2
[5][2][110] = [4][1][110]
And then, I wrote a solution.
Thaks for such a Fast Reply . I am trying to have this idea . I got several ideas to solve a problem from your Blog. They are great. I would like to request you to Share the Idea / Hint for a problem instead Code . You Can Share Code As an Extension. But an Idea Can help a Solver Much more to think .
DeleteOK, from now on, I will try to add some comments/explanatations to my solutions.
ReplyDelete