Description

如果整數(shù)序列{a1,a2,…,an}滿足以下條件，則它是一個(gè)“一序列”：1、對于任何的k（1<=k<n），|ak-ak+1| =1；2、a1＝0。給定兩個(gè)整數(shù)len和sum，求滿足以下條件的“一序列”共有多少個(gè)：長度為len，元素的總和等于sum。

Input

包含多組測試數(shù)據(jù)。每組測試數(shù)據(jù)包含一個(gè)正整數(shù)len 和一個(gè)整數(shù)sum。len <= 500，|sum| <= 100000

Output

每組測試數(shù)據(jù)輸出占一行。

如果不存在這樣的數(shù)列，輸出字符串“NIE”。否則輸出一個(gè)正整數(shù)ans，表示長度為len，各項(xiàng)總和為sum的“一序列”的種數(shù)。由于總數(shù)很大， 你只需要輸出結(jié)果對100000007取模的結(jié)果。

Sample Input 

6 310 100
Sample Output
3NIE分析：首先要判斷給出的兩個(gè)數(shù)能不能組成“一序列”，設(shè)輸入n、m，對于一個(gè)含有n項(xiàng)的“一序列”，其最大值為n*(n-1)/2[0+1+……+(n-1)]，同理，最小值為-n*(n-1)/2。設(shè)max = n*(n-1)/2，如果給出的和不在-max和max之間，則不能組成“一序列”，無解；另外，對于一個(gè)“一序列”，其項(xiàng)奇偶性為偶、奇、偶、奇、……，所以呢，序列的和的奇偶性是一定的，即同奇同偶，反之，則無解。
參考代碼
#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<string>#include<algorithm>#include<stack>#include<queue>#include<vector>#include<map> using namespace std;const int mod = 100000007;int n,m;int ans;int dp[2000005]; inline int add( int x)//1+2+...+x{    int tmp = 0;    for( int i = 1; i <= x; i++)        tmp += i;    return tmp;} int main(){    while( ~scanf("%d%d",&n,&m))    {       memset(dp,0,sizeof(dp));       n--;       int sum = add(n)-m;       //0+1+2+...+(n-1) < m的絕對值 或者 sum 為奇數(shù) 則不存在這樣的序列       if( add(n) < abs(m) || sum&1)            PRintf("NIE/n");        else        {            dp[0] = 1;            n = n*2;            for( int i = 2; i <= n; i++)            {                for( int j = sum; j >= i; j -= 2)                    dp[j] = (dp[j]+dp[j-i])%mod;            }            printf("%d/n",dp[sum]);         }     }     return 0;}