# Untitled

unknown
plain_text
6 months ago
1.7 kB
1
Indexable
Never
```1-------------
#define MOD 1000000007
class Solution {
public:
int kInversePairs(int n, int k) {
vector<vector<int>>dp(n+1,vector<int>(k+1,0));
dp[0][0]=1;
vector<int>prev(k+1,0);
prev[0]=1;

for(int i=1;i<=n;i++){
vector<int>cur(k+1);
for(int j=0;j<=k;j++){
for(int p=0;p<i;p++){
if(j-p>=0) cur[j]+=prev[j-p]%MOD;
}
}
prev=cur;
}
return prev[k]; //prev =cur
}
};
2------------------
#define MOD 1000000007
class Solution {
public:
int kInversePairs(int n, int k) {
vector<vector<int>>dp(n+1,vector<int>(k+1,0));
dp[0][0]=1;
vector<int>prev(k+1,0);
prev[0]=1;

for(int i=1;i<=n;i++){
vector<int>cur(k+1);
int sum=0;
for(int j=0;j<=k;j++){
if(j>=i) sum-=prev[j-i];
sum+=prev[j]%MOD;
cur[j]=sum;
}
prev=cur;
}
return prev[k]; //prev =cur
}
};
3--------------------------------------
#define MOD 1000000007
class Solution {
public:
int kInversePairs(int n, int k) {
vector<vector<int>>dp(n+1,vector<int>(k+1,0));
dp[0][0]=1;
vector<int>prev(k+1,0);
prev[0]=1;

for(int i=1;i<=n;i++){
vector<int>cur(k+1);
int sum=0;
for(int j=0;j<=k;j++){
if(j>=i) sum=(sum-prev[j-i]+MOD)%MOD;
sum=(sum+prev[j])%MOD;
cur[j]=sum;
}
prev=cur;
}
return prev[k]; //prev =cur
}
};```