Counting Crypto Permutations
Autumn Tournament (2017)
Submission name: crypto.cpp
Problem summary
Encrypt a permutation of 1..N by replacing each number with the corresponding prime. For every contiguous interval of length at least K, take the product of its K smallest elements. Given N, K and the number P of distinct products, count the original permutations modulo 1,000,000,007.
Input
One line: N K P.
Output
The number of permutations modulo 1,000,000,007.
Constraints
1 ≤ K ≤ N ≤ 400; 1 ≤ P ≤ 1,000,000,000.
Worked example
The second official example, with whitespace restored from the PDF.
Input
4 2 4
Output
12
Solution analysis
- Unique prime factorization means that two products are equal exactly when their K selected values form the same set. There is no need to construct primes or multiply them. Build a permutation by inserting the values 1,2,...,N in increasing order.
- When the largest value is inserted into a permutation of length i−1, old K-smallest sets remain possible. A new set containing the new maximum must consist of K consecutive elements in the new permutation: any extra element would be smaller than the maximum and replace it. If j elements lie to its left, the number of new sets is r=min(j,K−1)+min(i−1−j,K−1)−K+2, or zero when i<K.
- For i≥K, let R=min(K,i−K+1). Insertion increments 1..R−1 each occur twice, while R occurs i−2R+2 times. This includes i=K, when every one of the i positions adds exactly one set. dp[i][p] counts permutations with p distinct sets. Sum the previous row over these increments; prefix sums make each transition constant time.
- Worked example: with N=3 and K=2, length 2 has two permutations and one set. At length 3 the three insertion slots add 1,2,1 sets. Therefore P=2 occurs four times and P=3 occurs twice. Continuing one more layer gives 12 permutations for N=4,K=2,P=4. The code caps P by the sum of the largest possible increments before allocating memory.
Why it works
Each final permutation has exactly one predecessor obtained by removing its largest value. Old sets survive because removing that largest value from an interval cannot change its K smallest values. The newly appearing sets containing it correspond bijectively to length-K windows covering its insertion position. Counting insertion positions by their increment therefore counts every permutation exactly once.
Watch out. Do not count intervals rather than distinct K-element sets. The coefficient for the largest increment is i−2R+2, including all i slots when i=K. Reduce modulo the prime after subtraction and multiplication. K=1 and K=N both have fixed P and must still count all N! permutations.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,k;
long long requested;
cin>>n>>k>>requested;
int maximum=0;
for(int length=k;length<=n;++length){
maximum+=min(k,length-k+1);
}
if(requested>maximum){
cout<<0<<'\n';
return 0;
}
int p=static_cast<int>(requested);
const long long mod=1000000007;
vector<long long>previous(p+1),current(p+1),prefix(p+2);
previous[0]=1;
for(int length=1;length<=n;++length){
fill(current.begin(),current.end(),0);
if(length<k){
for(int value=0;value<=p;++value){
current[value]=previous[value]*length%mod;
}
}
else{
int largest=min(k,length-k+1);
// Prefix sums collect all contributions with increment 1..largest-1.
prefix[0]=0;
for(int value=0;value<=p;++value){
prefix[value+1]=(prefix[value]+previous[value])%mod;
}
for(int value=1;value<=p;++value){
int left=max(0,value-largest+1);
int right=value;
long long sum=(prefix[right]-prefix[left]+mod)%mod;
current[value]=2*sum%mod;
if(value>=largest){
int slots=length-2*largest+2;
current[value]=(current[value]+slots*previous[value-largest])%mod;
}
}
}
previous.swap(current);
}
cout<<previous[p]<<'\n';
}