Divisibility Sequences
National Olympiad — National round
Submission name: divseq.cpp
Problem summary
Count length-N sequences with values from 1 to K such that each adjacent pair has at least one member dividing the other. Return the count modulo 1,000,000,009.
Input
N K.
Output
The sequence count modulo 1000000009.
Constraints
1≤N,K≤1000. Subtasks: N≤5,K≤10; N≤10,K≤20; N,K≤100.
Worked example
An independently prepared example for this explanation.
Input
3 2
Output
8
Solution analysis
- dp[v] counts sequences of the current length ending in v. Initialize every value with one.
- For every divisor d and strict multiple v, transfer dp[d] to next[v] and dp[v] to next[d]. Add dp[v] once for equality.
- Repeat N−1 layers and sum the final layer.
Why it works
The final adjacent pair uniquely specifies the previous endpoint. Divisor–strict-multiple pairs enumerate each legal unequal transition once, while the separate equality transition prevents double counting.
Complexity: O(NK log K) time and O(K) space.
Watch out. The divisibility direction may change between adjacent pairs; equal adjacent values are allowed.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The final adjacent pair uniquely specifies the previous endpoint. Divisor–strict-multiple
// pairs enumerate each legal unequal transition once, while the separate equality transition prevents
// double counting.
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
int main(){
int n,k;
cin>>n>>k;
const int MOD=1000000009;
vector<int>d(k+1,1),e;
d[0]=0;
auto add=[&](int&a,int b){
a+=b;
if(a>=MOD){
a-=MOD;
}
};
for(int len=2;len<=n;len++){
e=d;
for(int a=1;a<=k;a++){
for(int b=2*a;b<=k;b+=a){
add(e[a],d[b]);
add(e[b],d[a]);
}
}
d.swap(e);
}
int ans=0;
for(int v=1;v<=k;v++){
add(ans,d[v]);
}
cout<<ans<<'\n';
}