1 /*  2     题意：转换就是求n位数字，总和为s/2的方案数  3     DP+高精度：状态转移方程：dp[cur^1][k+j] = dp[cur^1][k+j] + dp[cur][k];  4                 高精度直接拿JayYe的:)  5     异或运算的规则:  6     0⊕0=0,0⊕1=1  7     1⊕0=1,1⊕1=0  8     口诀：相同取0，相异取1  9 */ 10 #include 
     
       11 #include 
      
        12 #include 
       
         13 #include 
        
          14 #include 
         
           15 using namespace std; 16  17 const int numlen = 1005; 18 const int numbit = 4; 19 const int addbit = 10000; 20 const int maxn = numlen/numbit + 10; 21  22 struct bign { 23     int len, s[numlen]; 24     bign() { 25         memset(s, 0, sizeof(s)); 26         len = 1; 27     } 28     bign(int num) { *this = num; } 29     bign(const char *num) { *this = num; } 30     bign operator = (const int num) { 31         char s[numlen]; 32         sprintf(s, "%d", num); 33         *this = s; 34         return *this; 35     } 36     bign operator = (const char *num){ 37         int clen = strlen(num); 38         while(clen > 1 && num[0] == '0')    num++, clen--; 39         len = 0; 40         for(int i = clen-1;i >= 0; i -= numbit) { 41             int top = min(numbit, i+1), mul = 1; 42             s[len] = 0; 43             for(int j = 0;j < top; j++) { 44                 s[len] += (num[i-j]-'0')*mul; 45                 mul *= 10; 46             } 47             len++; 48         } 49         deal(); 50         return *this; 51     } 52     void deal() { 53         while(len > 1 && !s[len-1]) len--; 54     } 55     bign operator + (const bign &a) const { 56         bign ret; 57         ret.len = 0; 58         int top = max(len, a.len), add = 0; 59         for(int i = 0;add || i < top; i++) { 60             int now = add; 61             if(i < len) now += s[i]; 62             if(i < a.len)   now += a.s[i]; 63             ret.s[ret.len++] = now%addbit; 64             add = now/addbit; 65         } 66         return ret; 67     } 68     bign operator * (const bign &a)const { 69         bign ret; 70         ret.len = len + a.len; 71         for(int i = 0;i < len; i++) { 72             int pre = 0; 73             for(int j = 0;j < a.len; j++) { 74                 int now = s[i]*a.s[j] + pre; 75                 pre = 0; 76                 ret.s[i+j] += now; 77                 if(ret.s[i+j] >= addbit) { 78                     pre = ret.s[i+j]/addbit; 79                     ret.s[i+j] -= pre*addbit; 80                 } 81             } 82             if(pre) ret.s[i+a.len] = pre; 83         } 84         ret.deal(); 85         return ret; 86     } 87 }dp[2][1005]; 88 istream& operator >> (istream &in, bign &x) { 89     string s; 90     in >> s; 91     x = s.c_str(); 92     return in; 93 } 94 ostream& operator << (ostream &out, const bign &x) { 95     printf("%d", x.s[x.len-1]); 96     for(int i = x.len-2;i >= 0; i--)    printf("%04d", x.s[i]); 97     return out; 98 } 99 100 int main(void)        //URAL 1036 Lucky Tickets101 {102     //freopen ("W.in", "r", stdin);103 104     int n, s;105     while (scanf ("%d%d", &n, &s) == 2)106     {107         if (s & 1)    {puts ("0");    continue;}108 109         dp[0][0] = 1;110         int cur = 0;111         for (int i=1; i<=n; ++i)112         {113             for (int j=0; j<=s/2; ++j)    dp[cur^1][j] = 0;    114             for (int j=0; j<=9; ++j)115             {116                 for (int k=0; k+j<=s/2; ++k)117                     dp[cur^1][k+j] = dp[cur^1][k+j] + dp[cur][k];118             }119             cur ^= 1;120         }121 122         cout << dp[cur][s/2] * dp[cur][s/2] << endl;123     }124 125     return 0;126 }