c++ - 计算K个反向对的数量时C++溢出

给定两个整数n和k，我想计算有多少不同的数组由1到n的数字组成，这样正好有k个逆对。（即对i，j使得i<j和a[i]>a[j]）mod 10^9+7。
我在使用动态编程，我定义DP[i][j]为i个元素的数组数，正好是j个逆，然后我导出了递归：
DP[i][j]=DP[i-1][j]+dp[i-1][j-1]+...+dp[i-1][j-i+1]
此外，我注意到：
DP[i][j-1]=DP[i-1][j-1]+DP[i-1][j-2]+...+DP[i-1][j-i]
因此，结合这两个和，我们得到：
DP[i][j]=DP[i-1][j]+DP[i][j-1]-DP[i-1][j-i]
我写了下面的动态编程解决方案，它是为大的n到n，k工作在800左右但是，一旦我传递了这些值（例如，n=1000，k=990），结果就会溢出，我不确定为什么会发生这种情况以下是我的解决方案：

class Solution {
public:
    long long MOD = 1e9+7;
    int kInversePairs(int n, int k) {
        vector< vector<long long> > dp(1001, vector<long long>(1001, -1));
        return solve(dp, n, k);
    }
    long long solve(vector< vector<long long> >& dp, int n, int k){
        if (k<0)return 0;
        if (k==0)return 1;
        if (n==0)return 0;
        if (dp[n][k]!=-1)return dp[n][k];
        dp[n][k]=solve(dp, n-1, k)%MOD;
        dp[n][k]+=solve(dp, n, k-1)%MOD;
        dp[n][k]-=solve(dp, n-1, k-n)%MOD;
        //if (dp[n][k]<0){
        //    cout << "Overflow: " << solve(dp, n-1, k-n) << " " << solve(dp, n-1, k) <<  " " << solve(dp, n, k-1) << endl;
        //}
        return dp[n][k]%=MOD;
    }
};

最佳答案

我终于找到了答案。我在这里添加它以完成。
在线dp[n][k]-=solve(dp, n-1, k-n)%MOD;之后，dp[n][k]可能小于零，因为我们在每一时刻都取模MOD，所以即使在这条线之前dp[n][k]的实际值是1e20，我们也取模MOD，所以它的值可能降到甚至零所以在这行之后，值可能是负的。
我解决这个问题的方法是在取最后一个模之前加上+mod。以下是工作代码：

class Solution {
public:
    long long MOD = 1e9+7;
    int kInversePairs(int n, int k) {
        vector< vector<long long> > dp(1001, vector<long long>(1001, -1));
        return solve(dp, n, k);
    }
    long long solve(vector< vector<long long> >& dp, int n, int k){
        if (k<0)return 0;
        if (k==0)return 1;
        if (n==0)return 0;
        if (dp[n][k]!=-1)return dp[n][k];
        dp[n][k]=solve(dp, n-1, k)%MOD;
        dp[n][k]+=solve(dp, n, k-1)%MOD;
        dp[n][k]-=solve(dp, n-1, k-n)%MOD;
        dp[n][k]+=MOD; //just in case it became negative
        return dp[n][k]%=MOD;
    }
};