UVa 10198 Counting (结合数学)

UVa 10198 Counting (组合数学)

10198 - Counting

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1139

The Problem

Gustavo knows how to count, but he is now learning how write numbers. As he is a very good student, he already learned 1, 2, 3 and 4. But he didn't realize yet that 4 is different than 1, so he thinks that 4 is another way to write 1. Besides that, he is having fun with a little game he created himself: he make numbers (with those four digits) and sum their values. For instance:

132 = 1 + 3 + 2 = 6112314 = 1 + 1 + 2 + 3 + 1 + 1 = 9 (remember that Gustavo thinks that 4 = 1)

After making a lot of numbers in this way, Gustavo now wants to know how much numbers he can create such that their sum is a number n. For instance, for n = 2 he noticed that he can make 5 numbers: 11, 14, 41, 44 and 2 (he knows how to count them up, but he doesn't know how to write five). However, he can't figure it out for n greater than 2. So, he asked you to help him.

The Input

Input will consist on an arbitrary number of sets. Each set will consist on an integer n such that 1 <= n <= 1000. You must read until you reach the end of file.

The Output

For each number read, you must output another number (on a line alone) stating how much numbers Gustavo can make such that the sum of their digits is equal to the given number.

Sample Input

23

Sample Output

513

思路：用f[i]表示n=i时的答案，则考虑末位数字，如果选择1的话，那么一共有f[i-1]个数，如果是2的话，一共有f[i-2]个数，3有f[i-3]个数，4有f[i-1]个数。

所以：f[i]=2*f[i-1]+f[i-2]+f[i-3]

完整代码：

/*0.014s*/#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn = 410;char numstr[maxn];struct bign{int len, s[maxn];bign(){memset(s, 0, sizeof(s));len = 1;}bign(int num){*this = num;}bign(const char* num){*this = num;}bign operator = (const int num){char s[maxn];sprintf(s, "%d", num);*this = s;return *this;}bign operator = (const char* num){len = strlen(num);for (int i = 0; i < len; i++) s[i] = num[len - i - 1] & 15;return *this;}///输出const char* str() const{if (len){for (int i = 0; i < len; i++)numstr[i] = '0' + s[len - i - 1];numstr[len] = '\0';}else strcpy(numstr, "0");return numstr;}///去前导零void clean(){while (len > 1 && !s[len - 1]) len--;}///加bign operator + (const bign& b) const{bign c;c.len = 0;for (int i = 0, g = 0; g || i < max(len, b.len); i++){int x = g;if (i < len) x += s[i];if (i < b.len) x += b.s[i];c.s[c.len++] = x % 10;g = x / 10;}return c;}///减bign operator - (const bign& b) const{bign c;c.len = 0;for (int i = 0, g = 0; i < len; i++){int x = s[i] - g;if (i < b.len) x -= b.s[i];if (x >= 0) g = 0;else{g = 1;x += 10;}c.s[c.len++] = x;}c.clean();return c;}///乘bign operator * (const bign& b) const{bign c;c.len = len + b.len;for (int i = 0; i < len; i++)for (int j = 0; j < b.len; j++)c.s[i + j] += s[i] * b.s[j];for (int i = 0; i < c.len - 1; i++){c.s[i + 1] += c.s[i] / 10;c.s[i] %= 10;}c.clean();return c;}///除bign operator / (const bign &b) const{bign ret, cur = 0;ret.len = len;for (int i = len - 1; i >= 0; i--){cur = cur * 10;cur.s[0] = s[i];while (cur >= b){cur -= b;ret.s[i]++;}}ret.clean();return ret;}///模、余bign operator % (const bign &b) const{bign c = *this / b;return *this - c * b;}bool operator < (const bign& b) const{if (len != b.len) return len < b.len;for (int i = len - 1; i >= 0; i--)if (s[i] != b.s[i]) return s[i] < b.s[i];return false;}bool operator > (const bign& b) const{return b < *this;}bool operator <= (const bign& b) const{return !(b < *this);}bool operator >= (const bign &b) const{return !(*this < b);}bool operator == (const bign& b) const{return !(b < *this) && !(*this < b);}bool operator != (const bign &a) const{return *this > a || *this < a;}bign operator += (const bign &a){*this = *this + a;return *this;}bign operator -= (const bign &a){*this = *this - a;return *this;}bign operator *= (const bign &a){*this = *this * a;return *this;}bign operator /= (const bign &a){*this = *this / a;return *this;}bign operator %= (const bign &a){*this = *this % a;return *this;}} f[1005];int main(void){f[1] = 1, f[2] = 5, f[3] = 13;for (int i = 4; i <= 1000; ++i)f[i] = f[i - 1] + f[i - 1] + f[i - 2] + f[i - 3] ;int n;while (scanf("%d", &n))puts(f[n].str());return 0;}