第一次用lrj的高精度类模板，感觉还是很好用的
c[x]表示数字x需要的火柴根数
将已经使用的火柴数i看做状态，每添加一个数字x状态就从i转移到i+c[x]
d[i]表示从节点0到节点i路径的条数，则答案f(n) = d(1) + d(2) + …… + d(n)
开始的时候不计入0，最后的时候如果n≥6答案再加一
1 #define LOCAL 2 #include3 #include 4 #include 5 using namespace std; 6 7 struct bign 8 { 9 int len, s[1000];10 bign() { memset(s, 0, sizeof(s)); len = 1; }11 bign operator = (const char* num)12 {13 len = strlen(num);14 for(int i = 0; i < len; ++i)15 s[i] = num[len - i - 1] - '0';16 return *this;17 }18 bign operator = (int num)19 {20 char s[1000];21 sprintf(s, "%d", num);22 *this = s;23 return *this;24 }25 bign (int num) { *this = num; }26 bign (const char* num) { *this = num; }27 string str() const28 {29 string res = "";30 for(int i = 0; i < len; ++i)31 res = (char)(s[i] + '0') + res;32 if(res == "") res = "0";33 return res;34 }35 36 bign operator + (const bign b) const37 {38 bign c;39 c.len = 0;40 for(int i = 0, g = 0; g || i < max(len, b.len); ++i)41 {42 int x = g;43 if(i < len) x += s[i];44 if(i < b.len) x += b.s[i];45 c.s[c.len++] = x % 10;46 g = x / 10;47 }48 return c;49 }50 51 bign operator += (const bign& b)52 {53 *this = *this + b;54 return *this;55 }56 };57 58 istream& operator >> (istream& in, bign& x)59 {60 string s;61 in >> s;62 x = s.c_str();63 return in;64 }65 66 ostream& operator << (ostream &out, const bign& x)67 {68 out << x.str();69 return out;70 }71 72 const int maxn = 2000;73 bign d[maxn + 10];74 int c[] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6};75 76 int main(void)77 {78 #ifdef LOCAL79 freopen("11375in.txt", "r", stdin);80 #endif81 82 memset(d, 0, sizeof(d));83 d[0] = 1;84 for(int i = 0; i <= maxn; ++i)85 for(int j = 0; j < 10; ++j)86 if(!(i==0 && j==0) && i+c[j]<=maxn)87 d[i+c[j]] += d[i];88 for(int i = 2; i <= maxn; ++i)89 d[i] += d[i-1];90 int x;91 while(scanf("%d", &x) == 1)92 {93 if(x < 6) cout << d[x] << endl;94 else cout << d[x] + 1 << endl;95 }96 return 0;97 }