C++ Solution, 16ms


  • 0
    P
    class Solution {
    public:
        int kInversePairs(int n, int k) {
        	if (k == 0) return 1;
        	if (n == 0) return 0;
            long p = 1000000007;
            vector<long> dp(k+10, 0);
    
            for (int i = 1; i <= n; ++i) {
                vector<long> cur(k+10, 0);
            	int mj = min(i * (i-1) / 2, k);
            	cur[0] = 1;
            	for (int j = 1; j <= mj; ++j) {
                    if (j >= i)
            	    cur[j] = (cur[j-1] + dp[j] + p - dp[j-i]) % p;
                    else
                        cur[j] = (cur[j-1] + dp[j]) % p;
            	}
            	swap(dp, cur);
            }
    
            return dp[k];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.