给一个n，s；表示2*n位的一个数，每位上的数之和是s，前n位和与后n位和相等则是luck number，求符合要求的luck number的数目！

很简单的DP，dp[i][j]=SUM(dp[i-1][j-k])      0=<k<=9    因为i位和为j有多种来源，第i位可以是0--9，那么上一个状态就是dp[i-1][j-k] 

坑： 注意如果s是奇数的话就直接输出0

数据量：不大1 ≤ N ≤
50  0 ≤ S ≤
1000   肯定不会超时，在不会超时的前提下为什么要这么小的数据量呢？！！  

#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define FOR(i,a,b) for(i = (a); i < (b); ++i)
#define FORE(i,a,b) for(i = (a); i <= (b); ++i)
#define FORDE(i,a,b) for(i = (a); i >= (b); --i)

int n, s, ts;
short dp[60][1010][150];
short endd[300];

void add(int x, int y, int z) {
    int s = 0, c = 0, i;

    FOR(i, 0, 150) {
        s = c + dp[x][y][i] + dp[x - 1][y - z][i];
        dp[x][y][i] = s % 10;
        c = s / 10;
    }
}

void multi(int t, int j) {
    int i, s = 0, c = 0;

    FOR(i, 0, 300) {
        if(i + j >= 300)
            break;
        s = endd[i + j] + dp[n][ts][i] * t + c;
        endd[i + j] = s % 10;
        c = s / 10;
    }
}

void solve() {
    int i, j, k;

    cin>>n>>s;
    if(s & 1) {
        cout<<"0\n"; return ;
    }
    ts = s / 2;
    dp[0][0][0] = 1;///临界状态
    FORE(i, 1, n)
    FORE(k, 0, ts)
    FORE(j, 0, min(k, 9))
        add(i, k, j);
        
    FOR(i, 0, 150)
        multi(dp[n][ts][i], i);
    FORDE(i, 299, 0)
        if(endd[i] != 0)
            break;
    if(i == -1)
        cout<<"0\n";
    else {
        FORDE(j, i, 0)
            cout<<endd[j];
        cout<<endl;
    }
}

int main() {
    solve();
    return 0;
}

timus   1036. Lucky Tickets   URAL 解题报告