Concatenated Permutations Divisible by 16
National Olympiad — Municipal round (2019 season)
Submission name: perm16.cpp
Problem summary
Permute the integers 1…N and concatenate their decimal representations. Count permutations whose resulting integer is divisible by 16, modulo 1,000,000,007.
Input
One integer N.
Output
The permutation count modulo 1,000,000,007.
Constraints
3 ≤ N ≤ 50.
Worked example
An independently prepared example for this explanation.
Input
8
Output
2592
Solution analysis
- Divisibility by 16 depends only on the last four decimal digits, because 10⁴ is divisible by 16. Build an ordered suffix of whole numbers from right to left until its total decimal length is at least four.
- The suffix needs at most four numbers. Track its value modulo 16 and its decimal place multiplier. When four digits have been covered, every arrangement of the unused N−used numbers has the same divisibility, contributing (N−used)! if the suffix remainder is zero.
- For N=8 all numbers have one digit, so every ordered four-number suffix is considered. Suffix 7312 is divisible by 16; it represents 4!=24 full permutations obtained by freely arranging 4,5,6,8 before it. If N<4, explicitly reaching all N numbers also ends a branch.
Why it works
Every full permutation has a unique shortest suffix of whole numbers covering its last four digits, or consists entirely of the suffix if shorter. The recursive process reaches exactly that suffix and no longer one. Earlier digits contribute a multiple of 10⁴ and hence cannot change the remainder. The remaining distinct numbers can be arranged in exactly (N−used)! ways, so the sum counts each valid permutation once.
Watch out. Stop after covering four digits, even if the leftmost chosen number makes the suffix five digits long. Count permutations of unused numbers with factorials. Never construct the full concatenated integer.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
const long long MOD=1000000007;
int n;
vector<bool>used;
vector<long long>factorial;
long long answer=0;
void search(int count,int digits,int remainder,int place){
if(digits>=4||count==n){
if(remainder==0){
answer=(answer+factorial[n-count])%MOD;
}
return;
}
for(int value=1;value<=n;value++){
if(!used[value]){
used[value]=true;
int power=value<10?10:100;
// Prepend this whole number to the existing suffix.
search(count+1,digits+(value<10?1:2),(value*place+remainder)%16,
place*power%16);
used[value]=false;
}
}
}
int main(){
cin>>n;
used.assign(n+1,false);
factorial.assign(n+1,1);
for(int i=1;i<=n;i++){
factorial[i]=factorial[i-1]*i%MOD;
}
search(0,0,0,1);
cout<<answer<<'\n';
}