classSolution{public:intkInversePairs(intn,intk){constexprintkMod=1'000'000'007;// dp[i][j] := # of permutations of numbers 1..i with j inverse pairsvector<vector<int>>dp(n+1,vector<int>(k+1));// If there's no inverse pair, the permutation is unique "123..i"for(inti=0;i<=n;++i)dp[i][0]=1;for(inti=1;i<=n;++i)for(intj=1;j<=k;++j){dp[i][j]=(dp[i][j-1]+dp[i-1][j])%kMod;if(j-i>=0)dp[i][j]=(dp[i][j]-dp[i-1][j-i]+kMod)%kMod;}returndp[n][k];}};
classSolution{publicintkInversePairs(intn,intk){finalintkMod=1_000_000_007;// dp[i][j] := # of permutations of numbers 1..i with j inverse pairsint[][]dp=newint[n+1][k+1];// If there's no inverse pair, the permutation is unique "123..i"for(inti=0;i<=n;++i)dp[i][0]=1;for(inti=1;i<=n;++i)for(intj=1;j<=k;++j){dp[i][j]=(dp[i][j-1]+dp[i-1][j])%kMod;if(j-i>=0)dp[i][j]=(dp[i][j]-dp[i-1][j-i]+kMod)%kMod;}returndp[n][k];}}
classSolution:defkInversePairs(self,n:int,k:int)->int:kMod=1_000_000_007# dp[i][j] := # Of permutations of numbers 1..i with j inverse pairsdp=[[0]*(k+1)for_inrange(n+1)]# If there's no inverse pair, the permutation is unique '123..i'foriinrange(n+1):dp[i][0]=1foriinrange(1,n+1):forjinrange(1,k+1):dp[i][j]=(dp[i][j-1]+dp[i-1][j])%kModifj-i>=0:dp[i][j]=(dp[i][j]-dp[i-1][j-i]+kMod)%kModreturndp[n][k]