51nod 1158

Type:悬线法,单调栈(未学,用悬线法做的)

提示

蓝书P51,最大子矩阵 O(mn)

Code

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=510;
int m,n;
int mat[maxn][maxn],up[maxn][maxn],left[maxn][maxn],right[maxn][maxn];

void print(){
    printf("Up:\n");
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            printf("%d ",up[i][j]);
        }
        puts("");
    }
    printf("Left:\n");
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            printf("%d ",left[i][j]);
        }
        puts("");
    }
    printf("Right:\n");
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            printf("%d ",right[i][j]);
        }
        puts("");
    }
}

int main(){
    while(~scanf("%d%d",&m,&n)){
        for(int i=1;i<=m;++i){
            for(int j=1;j<=n;++j){
                scanf("%d",&mat[i][j]);
            }
        }
        int ans=0;
        for(int i=1;i<=m;++i){
            int lo=0,ro=n;
            for(int j=1;j<=n;++j){///从右往左扫描,维护up和left
                if(!mat[i][j]){
                    up[i][j]=left[i][j]=0;lo=j;
                }else{
                    up[i][j]=up[i-1][j]+1;
                    left[i][j]=max(left[i-1][j],lo+1);
                }
            }
            for(int j=n;j>=1;--j){///维护right
                if(!mat[i][j]){
                    right[i][j]=n+1;ro=j-1;
                }else{
                    right[i][j]=i==1?ro:min(right[i-1][j],ro);
                    ans=max(ans,up[i][j]*(right[i][j]-left[i][j]+1));
                }
            }
        }
        //print();
        printf("%d\n",ans);
    }
    return 0;
}

51nod 1225 余数之和

Type:逆元,数论,思维,同余定理

直接上代码,题解在代码中,这道题有点耗时间,但挺有趣的

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
LL N;
/*打表
void Table(int NN){
    for(int i=1;i<=NN;++i){
        printf("%04d-%04d ",i,NN%i);
    }
}
*/
LL fast_mod(LL a,LL n,LL Mod){
    LL ans=1;
    while(n){
        if(n&1){
            ans=(ans*a)%Mod;
        }
        a=(a*a)%Mod;
        n>>=1;
    }
    return ans;
}

LL inv2=fast_mod(2,mod-2,mod);
///对照算法
LL hh(){
    LL n=N;
    LL ans;
    ans=n%mod*(n%mod)%mod;
    for(LL t,r,i=1;i<=n;++i) {
        t=n/i;
        r=n/t;
        ans=ans-((r-i+1)%mod*((r+i)%mod))%mod*inv2%mod*t%mod;
        while(ans<0) ans+=mod;
        i=r;
    }
    return ans;
}

///本来想的是计算当前N/i相同的数量--结果为:
///(N-tmp*i)/i 即计算在 N-当前数字*(N/i)后还有多少个数字可以
///整分给(N/i),由于这个方法利用了除法,所以处理除法溢出有点麻烦
///1e9左右就炸掉了
///乘法溢出也很麻烦

///最好的方法就是 N/tmp 理解为最后一个除以 N 等于 tmp 的数字是几

///式子: F[N]=N*N-Sigma(N/i*i | i∈[1,N])
///其中 括号内的式子的 N/i 有sqrt(n)个不同的值
///证: 设 tmp=100/i 则 tmp*i=100 故 Count(tmp)<=sqrt(100)
///并且可以看出 相同的 N/i 对应的 i 是连续的.
///即我们可以用等差数列求和公式来求 当 tmp=N/i 时 i 的和
///用等差数列求和时/2用 2的逆元来做\

///自己坐着坐着就莫名其妙和他一样了= =
LL solve(){
    LL ans=N%mod*(N%mod)%mod;
    for(LL i=1;i<=N;){
        LL tmp=N/i;
        LL t=N/tmp;
        tmp=((i+t)%mod*((t-i+1)%mod))%mod*inv2%mod*tmp%mod;
        ans=(ans%mod-tmp%mod+mod)%mod;
        i=t+1;
    }
    return ans;
}

void dui_pai(){
    for(LL i=1;i<=1000000;++i){
        N=i;
        if(hh()!=solve()) printf("%lld Faild\n",N);
    }
    puts("Done");
}

int main(){
    //dui_pai();
    while(~scanf("%lld",&N)){
        printf("%lld\n",solve());
    }
    return 0;
}

51nod 1055 最长等差数列

Type: 动态规划,双向DP,思维,技巧

题目

N个不同的正整数,找出由这些数组成的最长的等差数列。

例如:1 3 5 6 8 9 10 12 13 14
等差子数列包括(仅包括两项的不列举)
1 3 5
1 5 9 13
3 6 9 12
3 8 13
5 9 13
6 8 10 12 14

其中6 8 10 12 14最长,长度为5。

Input

第1行:N,N为正整数的数量(3 <= N <= 10000)。
第2 – N+1行:N个正整数。(2<= A[i] <= 10^9)

Output

最长等差数列的长度。

Input示例

10
1
3
5
6
8
9
10
12
13
14

Output示例

5

题解

数据范围可判是O(N^2)
一开始我一直在想如何把数字,即两个数之间的差用哈希存起来,来方便dp.
然后搜了题解发现是论文题.
被叫做LLAP问题
Length of the Longest Arithmetic Progressio

论文Link:

https://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array/

论文解释

这道题可以转化为:

给与一个 排过序 的集合set,我们要求这个集合中的最长等差数列的长度.

标重点: 序列是已排好序的
我们设 dp[i][j] 为以下标 i 和 j 两个元素开头的等差序列最长长度.
我们可以创建一个浮标 j 作为等差数列的中间值

初始化一个 i=j-1,k=j+1.

1.如果 set[i]+set[k] < set[j]*2

k++

2.如果 set[i]+set[k] > set[j]*2

i–

如果 set[i]+set[k]=set[j]*2

则构成等差数列,我们只需要让

dp[i][j]=(dp[j][k]==0)?3:dp[j][k]+1

如果dp[j][k]=0的话,dp[i][j]直接=3就可以了,因为 i,j,k 三个刚好构成等差数列.否则等于 dp[j][k]+1

计算完以后 i–,k++ 继续计算其他以 j 为第二个点的等差数列

倒序计算,正序反过来即可

另外: 还可以 直接将 dp 数组初始化为 2(因为每个数的等差数列至少为2).
dp[i][j]=dp[j][k]+1

另外有一个小技巧: 如果int的取值范围不大,但是数组要开很大的时候,可以用 short int,比如这道题.

Code

#include<bits/stdc++.h>

using namespace std;

const int maxn=10000;

short int dp[maxn][maxn];
int Num[maxn],ans,N;

int main(){
    while(~scanf("%d",&N)){
        memset(dp,0,sizeof(dp));
        for(int i=0;i<N;++i){
            scanf("%d",&Num[i]);
        }
        sort(Num,Num+N);
        ans=0;
        for(int j=N-2;j>=1;--j){
            int i=j-1,k=j+1;
            while(k<N&&i>=0){
                if(Num[i]+Num[k]>2*Num[j]){
                    --i;
                }else if(Num[i]+Num[k]<2*Num[j]){
                    ++k;
                }else{
                    dp[i][j]=(dp[j][k]==0)?3:dp[j][k]+1;
                    ans=max(ans,(int)dp[i][j]);
                    --i;++k;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

51NOD 1241 特殊的排序

Type:动态规划,思维,最长等差数列(简化)

题目

一个数组的元素为1至N的整数,现在要对这个数组进行排序,在排序时只能将元素放在数组的头部或尾部,问至少需要移动多少个数字,才能完成整个排序过程?
例如:
2 5 3 4 1 将1移到头部 =>
1 2 5 3 4 将5移到尾部 =>
1 2 3 4 5 这样就排好了,移动了2个元素。

给出一个1-N的排列,输出完成排序所需的最少移动次数。

Input

第1行:1个数N(2 <= N <= 50000)。
第2 – N + 1行:每行1个数,对应排列中的元素。

Output

输出1个数,对应所需的最少移动次数。

Input示例

5
2
5
3
4
1

Output示例

2

题解

一开始会想到和逆序数有关,排序就是减少逆序数,所以会想到其中非逆序序列中最长的那个不用变化.

然后可以容易地证明剩余的数只需要移动一次即可到达正确的位置上

比如 12346587
可以发现最长等差整数序列是 12345 而我们需要 12345678
第一次: 1234587 6
第二次: 1234586 7
第三次: 1234567 8
OK,往数列前面放的也一样

那么我们的问题就是如何求最长等差数列(等差为1)了,

因为等差为1,所以我们不难想到:
dp[i] 为数字 i 的最长等差数列.
遍历Num[]数组的时候计算 dp 即可
dp[i]=dp[i-1]+1

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=50000+10;

int dp[maxn],N,Num[maxn],max_;

int main(){
    while(cin>>N){
        memset(dp,0,sizeof(dp));
        dp[0]=0;
        max_=1;
        for(int i=1;i<=N;++i){
            cin>>Num[i];
        }
        for(int i=1;i<=N;++i){
            dp[Num[i]]=dp[Num[i]-1]+1;
            max_=max(dp[Num[i]],max_);
            //cout<<i<<" "<<dp[Num[i]]<<endl;
        }
        cout<<N-max_<<endl;
    }
    return 0;
}

51nod 1120 机器人走方格 V3

Type:Lucas+Catalan序列+逆元

题目

N * N的方格,从左上到右下画一条线。一个机器人从左上走到右下,只能向右或向下走。并要求只能在这条线的上面或下面走,不能穿越这条线,有多少种不同的走法?由于方法数量可能很大,只需要输出Mod 10007的结果。

Input

输入一个数N(2 <= N <= 10^9)。

Output

输出走法的数量 Mod 10007。

Input示例

4

Output示例

10

题解

画图会发现就是一个Catalan序列,
但我一开始没理解题意,原来只是不能跨过斜线,但可以在斜线上走…

在Excel中画了一下,因为两边是对称的,所以我们只需要求一边,将最终的答案*2即可.

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=10007;

LL Pow(LL a,LL b,LL p){
    LL ans=1;
    while(b){
        if(b&1)
        {
            b--;
            ans=(ans*a)%p;
        }
        b>>=1;
        a=(a*a)%p;
    }
    return ans;
}

LL Comb(LL a,LL b,LL p)
{
    if(a < b) return 0;
    if(a == b) return 1;
    if(b > a-b) b = a-b;
    LL ans = 1, ca = 1, cb = 1;
    for(LL i=0; i<b; ++i)
    {
        ca = (ca*(a-i))%p;
        cb = (cb*(b-i))%p;
    }
    ans = (ca*Pow(cb, p-2,p))%p;
    return ans;
}
LL Lucas(LL n, LL m, LL p)
{
    LL ans = 1;
    while(n && m && ans)
    {
        ans = (ans * Comb(n%p, m%p, p))%p;
        n /= p;
        m /= p;
    }
    ///如果等于0则返回1
    return ans==0?1:ans;
}

void extgcd(LL a,LL b,LL& d,LL& x,LL& y){
    if(!b){ d=a; x=1; y=0;}
    else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }
}
LL inv(LL a,LL n){
    LL d,x,y;
    extgcd(a,n,d,x,y);
    return d==1?(x+n)%n:-1;
}

int main(){
    LL N;
    while(cin>>N){
        N=N-1;
        LL d1,d2;
        LL x=Lucas(2*N,N,mod);
        LL d=inv(N+1,mod);
        //cout<<"Lucas: "<<x<<endl;
        //cout<<"Inv: "<<d<<endl;
        cout<<2*x*d%mod<<endl;
    }
    return 0;
}

51nod 1119 机器人走方格V2

Type: 组合数学,二项式定理,逆元

题目

M * N的方格,一个机器人从左上走到右下,只能向右或向下走。有多少种不同的走法?由于方法数量可能很大,只需要输出Mod 10^9 + 7的结果。

Input

第1行,2个数M,N,中间用空格隔开。(2 <= m,n <= 1000000)

Output

输出走法的数量 Mod 10^9 + 7。

Input示例

2 3

Output示例

3

题解

画一下图会发现这就是杨辉三角,而我们需要求的是C(N+M-2,N-1)
用逆元和递推公式算一下就可以了

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
const int maxn=1000000+10;
int m,n;

LL inv[maxn];
void init(){
    inv[1]=1;
    for(int i=2;i<maxn;++i){
        inv[i]=(mod-mod/i)*1ll*inv[mod%i]%mod;
    }
}

LL solve(int N,int M){
    ///ans=C(N,M)
    //cout<<N<<" "<<M<<endl;
    LL ans=1;
    for(int i=1;i<=M;++i){
        ans=ans*(N-i+1)*1ll%mod*inv[i]%mod;
    }
    return ans;
}

int main(){
    init();
    while(cin>>m>>n){
        cout<<solve(n+m-2,n-1)<<endl;
    }
    return 0;
}

51nod 1383 整数分解为2的幂

Type: 组合数学,母函数

题目

任何正整数都能分解成2的幂,给定整数N,求N的此类划分方法的数量!由于方案数量较大,输出Mod 1000000007的结果。
比如N = 7时,共有6种划分方法。

7=1+1+1+1+1+1+1
=1+1+1+1+1+2
=1+1+1+2+2
=1+2+2+2
=1+1+1+4
=1+2+4

Input

输入一个数N(1 <= N <= 10^6)

Output

输出划分方法的数量Mod 1000000007

Input示例

7

Output示例

6

题解

生成函数

我们可以将题意理解为:

有1,2,4,…,2^N<=1000000 种物品可以选择,每种物品可以选择数量为无限,问你当背包重量为 M 时有多少种选择.

列出生成函数为:

g(m)=(1+x+x^2+x^3+…)(1+x^2+x^4+x^6+…)
(1+x^4+x^8+x^12+…)(1+x^8+x^16+x^24+…)
…(1+x^19) | (因为x^20>1e6)

只需要求出展开式中每项的序数即可,输入 N 输出 K[N]

我们给定一个数组 c1 作为储存系数用.

只需要将每个括号内的式子乘入数组 c1 即可.

限制条件为
i=2^t <= 1000000
j+i <= 1000000

所有的计算都向第一个括号 (1+x+x^2+…+x^1000000)
为基准进行合并,合并到 j+i>1000000 为止.

其他部分解释放在代码中

Code

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int maxn=1000100;
int c1[maxn]={1};

inline void init(int n){
    for(int i=1;i<=n;i<<=1){
        for(int j=0;(j+i)<=n;++j){
            ///j+i是 当前值为j,加上第log2(i)括号内的等差幂次i
            ///后计算出目标待加值为 (j+i)
            ///即幂次为(j+i)的母函数系数计算过程为:
            /// (k)x^(i+j)=(k1)x^j*x^i*(k2)x^(i+j)
            /// 即 k=k1+k2
            /// 即 c1[j+i]=c[j]+c[j+i]
            ///x^i系数为1因为生成函数第log2(i)个括
            ///号中所有x^i的系数为1
            c1[j+i]=(c1[j+i]+c1[j])%mod;
        }
    }
}


int main(){
    init(1000000);
    int N;

    while(cin>>N){
        cout<<c1[N]<<endl;
    }
    return 0;
}

51nod 1201 整数划分

Type:DP,思维

题意

将N分为若干个不同整数的和,有多少种不同的划分方式,例如:n = 6,{6} {1,5} {2,4} {1,2,3},共4种。由于数据较大,输出Mod 10^9 + 7的结果即可。

Input

输入1个数N(1 <= N <= 50000)。

Output

输出划分的数量Mod 10^9 + 7。

Input示例

6

Output示例

4

题解

首先我们可以由

1+2+3+…+m=n 估算出 大概只有sqrt(2*n)个数字左右

我们设当前状态为 dp[i][j]

dp[i][j] 代表当前数字为 j ,被划分成了 i 部分.
状态转移推倒:

我们假设已知所有 dp 的划分数序列.

(1) 我们将 dp[i][j-i] 每个 划分数每个数字 +1 ,我们将得到 不存在1 的划分数.

(2) 我们将 dp[i-1][j-i] 每个 划分数每个数字(共 i-1 个) +1 ,我们将得到 不存在1 的且长度为 i-1 ,和为 j-1 的划分数,然后我们将 1 放到划分数中,即得到全部 有1 的划分数.

即 dp[i][j]=(dp[i][j-i]+dp[i-1][j-i])%mod

正确性证明:

假设已知 dp[i][j] 的全部序列.
我们只需要一直对每个数字 -1 就可以将所有序列置为 全0.

给一个例子自己倒着推一下也成立

组成1的 有 {1} 

组成2的 有 {2} 

组成3的 有 {1,2} {3}

组成4的 有 {1,3} {4}

组成5的 有 {1,4} {2,3} {5}

组成6的 有 {1,5} {2,4} {1,2,3} {6}

组成7的 有 {1,6} {2,5} {3,4} {1,2,4} {7}

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=50010;
const LL mod=1e9+7;
int N;
LL dp[330][maxn];

int main(){
    scanf("%d",&N);
    dp[1][1]=1ll;
    for(int i=2;i<=N;++i){
        for(int j=1;j<=(int)sqrt(2*i);++j){
            dp[j][i]=(dp[j][i-j]+dp[j-1][i-j])%mod;
        }
    }
    LL ans=0;
    for(int i=1;i<=(int)sqrt(2*N);++i) ans=(ans+dp[i][N])%mod;
    printf("%lld\n",ans);
    return 0;
}

51nod 1084 矩阵取数问题 V2

Type:DP,多路(进程)DP

题目

一个M*N矩阵中有不同的正整数,经过这个格子,就能获得相应价值的奖励,先从左上走到右下,再从右下走到左上。第1遍时只能向下和向右走,第2遍时只能向上和向左走。两次如果经过同一个格子,则该格子的奖励只计算一次,求能够获得的最大价值。

例如:3 * 3的方格。

1 3 3
2 1 3
2 2 1

能够获得的最大价值为:17。1 -> 3 -> 3 -> 3 -> 1 -> 2 -> 2 -> 2 -> 1。其中起点和终点的奖励只计算1次。

Input

第1行:2个数M N,中间用空格分隔,为矩阵的大小。(2 <= M, N <= 200)
第2 – N + 1行:每行M个数,中间用空格隔开,对应格子中奖励的价值。(1 <= A[i,j] <= 10000)

Output

输出能够获得的最大价值。

Input示例

3 3
1 3 3
2 1 3
2 2 1

Output示例

17

题解

一开始的想法是先走一遍取最大值,然后回溯到起点,把走过的地方置为 0,然后WA= =,发现是行不通的,因为两次都是最有没办法保证全局最优.

然后搜了题解

这里用到多进程dp,即我们用 dp[step][j][k] 代表当前走了 step 步,第一个走的人在第 j行,第二个走的人在第 k行时最大的经过路径之和.

如果 j==k 时,即两个人当前路径点重合了.我们只需要随便选取一个加到记忆化数组中即可.

而当我们多路dp时,两个人来到当前状态的方向可能是

(1) 第一个人往下走,第二个人往下走
(2) 第一个人往下走,第二个人往右走
(3) 第一个人往右走,第二个人往下走
(4) 第一个人往右走,第二个人往右走

我们只需要在遍历到每个状态时,对以上四个状态找最大值加上两个人当前地点的数字即可

答案是dp[M+N][N][N]

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=210;
int N,M,A;
int mp[maxn][maxn],dp[2*maxn][maxn][maxn];

int main(){
    ///读题bug,N是行,第二个读入
    scanf("%d%d",&M,&N);
    for(int i=1;i<=N;++i){
        for(int j=1;j<=M;++j){
            scanf("%d",&mp[i][j]);
        }
    }
    ///枚举步数
    for(int i=2;i<=N+M;++i){
        ///枚举位于行数 i-j or k即为当前所处列(因为总步数为i(行数加列数和))
        for(int j=1;j<=N&&i-j>=0;++j){
            for(int k=1;k<=N&&i-k>=0;++k){
                ///分为四种情况,下下,下右,右下,右右
                if(k==j){
                    //下下
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-1]+mp[j][i-j]);
                    //下右
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]+mp[j][i-j]);
                    //右下
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k]+mp[j][i-j]);
                    //右右
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]+mp[j][i-j]);
                }else{
                    //下下
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-1]+mp[j][i-j]+mp[k][i-k]);
                    //下右
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]+mp[j][i-j]+mp[k][i-k]);
                    //右下
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k]+mp[j][i-j]+mp[k][i-k]);
                    //右右
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]+mp[j][i-j]+mp[k][i-k]);
                }
            }
        }
    }
    printf("%d\n",dp[N+M][N][N]);
    return 0;
}


51nod 1020 逆序排列

Type:DP,逆序数

题目

在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2 4 3 1中,2 1,4 3,4 1,3 1是逆序,逆序数是4。

1-n的全排列中,逆序数最小为0(正序),最大为n*(n-1) / 2(倒序)
给出2个数n和k,求1-n的全排列中,逆序数为k的排列有多少种?
例如:n = 4 k = 3。

1 2 3 4的排列中逆序为3的共有6个,分别是:
1 4 3 2
2 3 4 1
2 4 1 3
3 1 4 2
3 2 1 4
4 1 2 3

由于逆序排列的数量非常大,因此只需计算并输出该数 Mod 10^9 + 7的结果就可以了。

Input

第1行:一个数T,表示后面用作输入测试的数的数量。(1 <= T <= 10000)
第2 – T + 1行:每行2个数n,k。中间用空格分隔。(2 <= n <= 1000, 0 <= k <= 20000)

Output

共T行,对应逆序排列的数量 Mod (10^9 + 7)

Input示例

1
4 3

Output示例

6

题解

考虑 dp[i][j] 表示 元素个数为 i 个时 逆序数为 j 的全排列个数为 dp[i][j] 个.

设当前元素为 N ,则 N 可以放在原来 N-1 个元素的任意全排列的 N-i(i∈[0,N)) 上的位置.

当 N 放在位置 N-i 上时,该排列的逆序数会增长 i (因为N最大,所以后面i个为逆序,前面为顺序),所以当我们想要找长度为 N ,逆序数为 k 的个数时,只需要找长度为 N-1 ,逆序数为 k-i 的全排列的个数即可.

所以 dp[N][k] = lambda(dp[N-1][k-i] | i∈[0,N))

复杂度为 O(k(N^2)) 会炸.

考虑优化:

① dp[N][k] = lambda(dp[N-1][k-i] | i∈[0,N))
② dp[N][k-1] = lambda(dp[N-1][k-1-i] | i∈[0,N))
①-②: dp[N][k]-dp[N][k-1] = dp[N-1][k]-dp[N-1][k-N]
dp[N][k]=dp[N-1][k]-dp[N-1][k-N]+dp[N][k-1]

得出递推公式:

① dp[i][j]=1 j=0
② dp[i][j]=dp[i-1][j]-dp[i-1][j-i]+dp[i][j-1]

由题目的约束条件:

逆序数最小为0(正序),最大为n*(n-1) / 2(倒序)

故枚举逆序数只需要枚举到 i*(i-1)/2&&j\<20000即可
注意j-i不能<0

Code

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int dp[1010][20010];

void init(){
    for(int i=1;i<=1000;++i) dp[i][0]=1;
    for(int i=2;i<=1000;++i){
        for(int j=1;j<=i*(i-1)/2&&j<=20000;++j){
            dp[i][j]=(dp[i][j-1]+dp[i-1][j])%mod;
            if(j-i>=0)dp[i][j]=(((dp[i][j]-dp[i-1][j-i])%mod)+mod)%mod;
        }
    }
}

int main(){
    init();
    int T;
    scanf("%d",&T);
    while(T--){
        int n,k;
        scanf("%d%d",&n,&k);
        printf("%d\n",dp[n][k]);
    }
    return 0;
}