Proficient.
Put your skills to the test.

Problem summary

Count strictly increasing sequences of two-digit numbers over digits 1…n, with the first digit smaller than the second, using each digit exactly twice. Return the count modulo 987654321.

Constraints

2 < n < 10000000.

Worked example

An independently prepared example for this explanation.

3

1

Solution analysis

1. View each two-digit number ij with i<j as an undirected edge on n labeled vertices. Strict increase prohibits repeated edges and fixes the sequence order. Each digit occurring twice means every vertex has degree two, so count simple labeled graphs made of disjoint cycles of length at least three.
2. Let a[n] count these graphs. The recurrence a[n]= (n−1)a[n−1] + ((n−1)(n−2)/2)a[n−3] follows by isolating vertex n: if its cycle has at least four vertices, remove n and join its two neighbors; reinsertion chooses one of n−1 edges. If its cycle is a triangle, choose its two partners and an arbitrary graph on the remaining vertices.
3. Use a[0]=1 and a[1]=a[2]=0. Then a[3]=1, a[4]=3 and a[5]=12. Only the previous three entries are needed. Compute the exact integer coefficient before reducing modulo the odd composite modulus; no modular division is necessary.

Why it works

In a cycle of length at least four, deleting n produces a unique simple degree-two graph on n−1 vertices and singles out the edge where it was inserted. There are n−1 edges in every such graph. Triangle components instead give exactly a choice of two partners and a graph on n−3 vertices. These disjoint bijections prove the recurrence.

Watch out. The modulus is composite. Do integer division by two before reduction, and reduce the coefficient before multiplication to avoid 64-bit overflow.

An independently written complete program with standard headers.

#include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    const long long mod=987654321;
    long long recent[3]={1,0,0};
    for(long long size=3;size<=n;++size){
        long long pairs=((size-1)*(size-2)/2)%mod;
        long long value=((size-1)*recent[(size-1)%3]+pairs*recent[size%3])%mod;
        // The overwritten slot contains a[size-3].
        recent[size%3]=value;
    }
    cout<<recent[n%3]<<'\n';
}