Permutations with Inequalities
National Olympiad — Regional round (2025 season)
Submission name: permutation.cpp
Problem summary
Given n−1 signs < or >, count permutations of 1 through n whose consecutive elements satisfy those signs. Return the count modulo 1,000,000,007.
Input
n, followed by a string t of length n−1.
Output
The number of valid permutations modulo 1,000,000,007.
Constraints
2 ≤ n ≤ 3000; every character of t is < or >.
Worked example
An independently prepared example for this explanation.
Input
4 <><
Output
5
Solution analysis
- Keep dp[r], the number of valid relative orderings of the current prefix whose final element has zero-based rank r within that prefix. The actual values do not matter yet; only their relative order determines the comparisons.
- Append a new final element of rank r in a prefix of length length. If the preceding sign is <, the old final rank must be less than r, giving the prefix sum of dp before r. If the sign is >, its old rank must be at least r, giving the suffix sum from r. Prefix sums evaluate all transitions in linear time per length.
- For <><, the rank distributions after lengths 1,2,3,4 are [1], [0,1], [1,1,0], and [0,1,2,2]. Their final sum is 5. Initialize the single-element prefix with one ordering and finally sum all possible last ranks.
Why it works
Inserting the new element at its chosen rank gives a bijection from old relative orderings to extended orderings. Old ranks below the inserted rank stay smaller; old ranks at least that rank shift up and become larger. Hence the two transition ranges are exactly the required inequality cases. Induction proves every rank count, and summing the last ranks counts all full permutations.
Watch out. For > include old rank r in the suffix; inserting the new rank shifts that old element upward. Clear or overwrite every entry used by the next stage.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
#include<vector>
// Algorithm: Keep dp[r], the number of valid relative orderings of the current prefix whose
// final element has zero-based rank r within that prefix.
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
string signs;
cin>>n>>signs;
const int mod=1000000007;
vector<int>dp(n),next(n),prefix(n+1);
dp[0]=1;
for(int length=2;length<=n;++length){
prefix[0]=0;
for(int rank=0;rank<length-1;++rank){
prefix[rank+1]=(prefix[rank]+dp[rank])%mod;
}
for(int rank=0;rank<length;++rank){
if(signs[length-2]=='<'){
next[rank]=prefix[rank];
}
else{
next[rank]=(prefix[length-1]-prefix[rank]+mod)%mod;
}
}
dp.swap(next);
}
int answer=0;
for(int rank=0;rank<n;++rank){
answer=(answer+dp[rank])%mod;
}
cout<<answer<<'\n';
}