51Nod 1043 幸运号码

 #include <stdio.h>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 const int mod = 1e9 + ;

 int dp[][];

 // dp[i][j] : i 个数，组成总和为j 的数量

 int main()

 {

     int n;

     scanf("%d", &n);

     dp[][] = ;

     for (int i = ; i <= ; i++)

         dp[][i] = ;

     for (int i = ; i <= n; i++)

     {

         for (int j = ; j <=  * i; j++)

         {

             int sum = ;

             for (int k = ; k <= ; k++)

             {

                 if (j >= k)

                     sum = (sum + dp[i - ][j - k]) % mod;

                 else

                     break;

             }

             dp[i][j] = sum;

         }

     }

     ll ans = ;

     for (int i = ; i <=  * n; i++)

         ans = (ans + (ll)dp[n][i] * (dp[n][i] - dp[n - ][i])) % mod;

     printf("%lld\n", ans);

     return ;

 }