Divisible Digit Subsequences
National Olympiad — Regional round (2017 season)
Submission name: sdiv.cpp
Problem summary
Count nonempty subsequences of a decimal digit string whose represented number is divisible by n. Leading zeroes are allowed, and subsequences selected at different index sets count separately. Report the count modulo m.
Input
Digit string, then n m.
Output
The count modulo m.
Constraints
String length < 10000; 1 < n < 1000; 1 < m < 10^12.
Worked example
Official sample; other valid outputs may exist.
Input
222 2 10
Output
7
Solution analysis
- Maintain dp[r], the number modulo m of nonempty subsequences of the processed prefix with remainder r. When digit d arrives, each old subsequence can omit it or append it, changing remainder to (10r+d) mod n.
- Start the new array as a copy of the old array for omissions, add every append transition, and add the singleton subsequence consisting only of d. Separate arrays prevent reusing the current digit several times.
- For 222 and divisor 2, all seven nonempty index subsets form even numbers. They include three different one-digit subsequences and three different two-digit subsequences.
Why it works
Every nonempty subsequence after the new position either omits the position, consists of that position alone, or uniquely appends it to a nonempty earlier subsequence. These cases are disjoint and exhaustive. The remainder update follows decimal concatenation, so induction proves all DP counts and dp[0] is the requested count.
Watch out. Do not count the empty subsequence. Equal resulting strings from different index sets remain distinct. Use 64-bit counts.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every nonempty subsequence after the new position either omits the position, consists of
// that position alone, or uniquely appends it to a nonempty earlier subsequence. These cases are
// disjoint and exhaustive.
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
int n;
long long mod;
cin>>s>>n>>mod;
vector<long long>dp(n,0);
for(char c:s){
int digit=c-'0';
vector<long long>next=dp;
for(int r=0;r<n;++r){
int nr=(10*r+digit)%n;
next[nr]=(next[nr]+dp[r])%mod;
}
next[digit%n]=(next[digit%n]+1)%mod;
dp.swap(next);
}
cout<<dp[0]<<'\n';
}