yukicoder : No.41 貯金箱の溜息（EASY）

こちらは問題名通りEasy。
http://yukicoder.me/problems/40

問題

この国には1円玉の他に111111円、222222円…999999円と６桁のゾロ目に相当する9種類を含めた計10個の硬貨がある。
これらでM円を払う払い方は何通りあるか。

解法

端数は1円玉で一意に調整できる、と考えると111111円以上の硬貨でM円以下を払う払い方を求める問題となる。
さらに言い換えると、P=M/111111とすると、1～9を足してでP以下の非負整数を作る作り方を求める問題と言える。
ここまで行ければ後は簡単なDP。

ll mo = 1000000009;
ll dp[200000];
ll sum[200000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	dp[0]=1;
	for(j=1;j<=9;j++) FOR(i,100001) (dp[i+j]+=dp[i])%=mo;
	FOR(i,100001) sum[i]=((i?sum[i-1]:0)+dp[i])%mo;
	
	cin>>x;
	FOR(i,x) {
		ll M;
		cin>>M;
		cout<<sum[M/111111]<<endl;
	}
}

まとめ

なぜmod 1000000007でなくて1000000009なんだろう。