プロジェクトオイラー Problem 76 「和の数え上げ」 †

Problem 76 「和の数え上げ」 †

5は数の和として6通りに書くことができる:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

2つ以上の正整数の和としての100の表し方は何通りか.

解法
素朴な動的計画法ではmemo[101][101]の配列が必要ですが。
Ｗｉｋｉに掲載されていた分割数の漸化式をそのまま実装します。
100は
Ｃ++


#include<stdio.h>
#include<iostream>

int pos(int n){
      n++;
      int n1=n/2*(n%2==0?1:-1);
      return (n1*(3*n1-1))/2;
}


int main(){
      __int64 memo[101]={0};
      memo[0]=1;
      for(int i=1;i<=100;i++){
            for(int j=1;j<=i;j++){
                  int p=pos(j);
                  if(i-p<0)break;
                  __int64 mult=((j-1)%4)/2==0?1:-1;
                  memo[i]+=memo[i-p]*mult;
            }
      }
      std::cout<<memo[100];
}