URAL 1036 Lucky Tickets（基础dp）

题目链接：
URAL 1036 Lucky Tickets
题意；
要将$s$分成两组$n$个$[0,9]$之间的和相等，求方案数。
数据范围：$1\leq n \leq 50,0\leq s \leq 1000$
分析：
用$dp[i][j]$表示前$i$个数和为$j$的方案数。需要注意每个数字只能属于$[0,9]$

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
typedef long long LL;
#define MAXN 100struct BigInteger {int len, s[MAXN];BigInteger () {memset(s, 0, sizeof(s));len = 1;}BigInteger operator = (const char *num) { //字符串赋值len = strlen(num);for(int i = 0; i < len; i++) s[i] = num[len - i - 1] - '0';}BigInteger operator = (int num) { //int 赋值char s[MAXN];sprintf(s, "%d", num);*this = s;return *this;}BigInteger (int num) {*this = num;}BigInteger (const char*num) {*this = num;}string str() const { //转化成stringstring res = "";for(int i = 0; i < len; i++) res = (char)(s[i] + '0') + res;if(res == "") res = "0";return res;}BigInteger operator + (const BigInteger& b) const {BigInteger 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;}BigInteger clean() {while(len > 1 && !s[len-1]) len--;return *this;}BigInteger operator *(const BigInteger& b) {BigInteger 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;}return c.clean();}BigInteger operator - (const BigInteger& b) {BigInteger 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;}return c.clean();}BigInteger operator / (const BigInteger &b) {BigInteger c, f = 0;for(int i = len-1; i >= 0; i--) {f = f*10;f.s[0] = s[i];while(f >= b) {f = f - b;c.s[i]++;}}c.len = len;return c.clean();}BigInteger operator % (const BigInteger &b) {BigInteger r = *this / b;r = *this - r * b;return r;}BigInteger operator /= (const BigInteger &b) {*this  = *this / b;return *this;}BigInteger operator %= (const BigInteger &b) {*this = *this % b;return *this;}bool operator < (const BigInteger& 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 BigInteger& b) const {return b < *this;}bool operator <= (const BigInteger& b) {return !(b < *this);}bool operator == (const BigInteger& b) {return !(b < *this) && !(*this < b);}bool operator != (const BigInteger &b) {return !(*this == b);}BigInteger operator += (const BigInteger& b) {*this = *this + b;return *this;}bool operator >= (const BigInteger &b) {return *this > b || *this == b;}
};istream& operator >>(istream &in, BigInteger& x) {string s;in >> s;x = s.c_str();return in;
} ostream& operator <<(ostream &out, const BigInteger& x) {out << x.str();return out;
}BigInteger dp[101][1001];void init()
{dp[0][0] = 1;for(int i = 1; i < 55; ++i) {for(int j = 0; j < 550; ++j) {for(int k = 0; k < 10; ++k) {dp[i][j + k] = dp[i][j + k] + dp[i - 1][j];}}}
}int main()
{init();int n, s;while(~scanf("%d%d", &n, &s)){if(s & 1) puts("0");else cout << dp[n][s >> 1] * dp[n][s >> 1] << endl;}return 0;
}