Proficient.
Put your skills to the test.

Problem summary

Count permutations of N distinct layers with between L and R inversions, inclusive. An inversion is a pair whose relative chronological order disagrees with its depth order. Return the count modulo 1,000,000,007.

Constraints

1 ≤ N ≤ 500; 0 ≤ L ≤ R ≤ N(N−1)/2.

Worked example

An independently prepared example for this explanation.

4 1 2

8

Solution analysis

1. Let dp[k] count permutations of the elements already inserted that have k inversions. Inserting the next, largest element among i elements creates any number t from 0 through i−1 of new inversions, once for each possible insertion position.
2. Thus next[k] is the sum of dp[k], dp[k−1], …, dp[k−i+1]. Maintain this sum in a sliding window as k increases: add dp[k] and remove dp[k−i] when that index exists. Values above R are never needed because subsequent insertions cannot decrease the inversion count.
3. For N = 4 the inversion counts 0, 1, 2 have frequencies 1, 3, 5. Summing frequencies for 1 and 2 gives 8. Initialize dp[0] = 1 for the empty permutation, then perform all N insertion stages.

Why it works

Every permutation of i elements has a unique position for its largest element. Removing it leaves one permutation of i−1 elements, and the elements after it are exactly its new inversions. The recurrence therefore counts every permutation once. The sliding window evaluates that recurrence exactly, and summing its final entries from L through R yields the requested answer.

Watch out. Include both endpoints. Normalize a window after subtraction modulo the prime. Never retain values from the previous stage in the destination array.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
// Algorithm: Let dp[k] count permutations of the elements already inserted that have k
// inversions.
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,left,right;
    cin>>n>>left>>right;
    const long long mod=1000000007;
    vector<long long>dp(right+1),next(right+1);
    dp[0]=1;
    for(int count=1;count<=n;++count){
        long long window=0;
        for(int inversions=0;inversions<=right;++inversions){
            window+=dp[inversions];
            if(inversions>=count){
                window-=dp[inversions-count];
            }
            window=(window%mod+mod)%mod;
            next[inversions]=window;
        }
        dp.swap(next);
    }
    long long answer=0;
    for(int inversions=left;inversions<=right;++inversions){
        answer=(answer+dp[inversions])%mod;
    }
    cout<<answer<<'\n';
}