[OCaml][C] ディビジョン・ナイン

@riverplus さんの CodeIQ 出題問題。
https://codeiq.jp/q/2561
http://togetter.com/li/956617

答案：整数分割問題として直接導出。

ざっと見た限り、見られる解き方は

0..8 mod9 の９連漸化式
F(n,sum) の漸化式
1,2,3,4 の登場回数探索総あたり

くらい？

本稿は上記以外の解法となる。
なお、F(19) F(20) の導出には 64bit 整数処理が必要(倍精度浮動小数だとけた落ちする）。

導出過程

高校数学（現行課程なら数I) の知識で。

まず、必要な事実を列挙しておく。

(n桁の)整数Ｎが９で割り切れる＝Ｎの各桁の数字の和が９で割り切れる、である。
整数Ｎに登場する数は1〜4のみであるから、Ｎの各桁の数字の和の上限は、4n である(下限はn)。

したがって、n が与えられた時、各桁の和が 9, 18, 27, ... で 4n 以下までを場合分けして探索する必要がある。

さて、登場可能な数を1〜4に限らず一般的に、和がsになるような0以上の整数(ここでは10以上もOKとして)分割を考える。特に、ちょうど n 個の非負整数に分割できるかどうかを考える。
と、これは単純な重複組み合わせである。nＨs = (s+n-1)Ｃ(n-1)

問題は非負整数ではないので、少しひねる必要がある。
まず、非負整数ではなく自然数、つまり０を除外することを考えると、各桁にまず1を分配してしまえば、残りは和がs-nになるようなn個の非負整数の分割問題に還元させることができる。
つまり、nＨ(s-n) = (s-1)Ｃ(n-1)

これだと、元の問題に対しては、各桁に５以上の数が含まれるケースも数え上げられてしまっているので、それを引かなければならない。

５以上の数が1つ以上含まれているケースは、nＨ(s-n-4) × nＣ1
５以上の数が2つ以上含まれているケースは、nＨ(s-n-4*2) × nＣ2
...
５以上の数がjつ以上含まれているケースは、nＨ(s-n-j*2) × nＣj

したがって、和がs になる、求める組み合わせ総数は、
F(n,s) = Σ(j=0 to n) ((-1)^j × nH(s-n-4*j)×nCj)
ゆえに総数は、
F(n)=Σ(s=9,18,..<=4n)Σ(j=0 to n) ((-1)^j × nH(s-n-4*j)×nCj)

となり、これをコーディングすればおしまい。

コード

CodeIQ 環境には nums.cma が組み込まれておらず Big_int 等が使えない。

let ( +% )=Int64.add
let ( -% )=Int64.sub
let ( *% )=Int64.mul
let ( /% )=Int64.div
let ( !% )=Int64.of_int
let ( !! )=Int64.to_string
let zero=Int64.zero
let one =Int64.one

let c n r=
  let rec cc m i q=
    let new_q=q *% (!% m)  /% (!% i) in
    if i<=r then cc (m+1) (i+1) new_q else q
  in
  if n0 then f_iter (i-9) (sum +% (fsub i n zero)) else sum
  in
  let sum=f_iter (n*4/9*9-n) zero in
  print_endline !!sum
;;
f (read_int())

#include 

/* Calc. Combination nCr */
long long c(int n, int r)
{
  long long q=1;
  int i,k;

  if( n0; i-=9){
    long long subsum=0;
    for(j=n; j>=0; j--)
      subsum = c(n,j) * c(i-j*4+n-1, n-1) - subsum;
    sum += subsum;
  }
  return sum;
}

int main()
{
  int n;
  scanf("%d",&n);
  printf("%lld\n",f(n));
  return 0;
}