linux畅想

http://acm.hdu.edu.cn/showproblem.php?pid=1284

Problem Description
在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。

Input
每行只有一个正整数N，N小于32768。

Output
对应每个输入，输出兑换方法数。

Sample Input
2934
12553

Sample Output
718831
13137761

代码

#include<stdio.h>
void main()
{
    int n;
    while(~scanf("%d",&n))
        printf("%d\n",n/3+1+((n/3+1)*(n+n%3)/2-(n/3+1)/2-n%2*n%3%2)/2);
}

分析
先来看只有1分2分的情况。
记a[i]为将钱i兑换成硬币1分2分的兑换种数。
则a[i]=(i-i%2)/2+1。
设n=3t+k（其中t=n/3，k=n%3）。
设s[n]为将钱n换成硬币1分2分3分的兑换种数。
则s[n]=a[k]+a[3*1+k]+…+a[3*i+k]+…+a[3*t+k]。
s[n]=[(k-k%2)/2+1]+…+[((3*i+k)-(3*i+k)%2)/2+1]+…+[((3*t+k)-(3*t+k)%2)/2+1]
=t+1+{[k+…+(3*i+k)+…+(3*t+k)]-[k%2+…+(3*i+k)%2+…+(3*t+k)%2]}/2
=t+1+{(t+1)(3*t+k+k)/2-[k%2+…+(3*i+k)%2+…+(3*t+k)%2]}/2
=t+1+{(n/3+1)(n+n%3)/2-[k%2+…+(3*i+k)%2+…+(3*t+k)%2]}/2
=t+1+{(n/3+1)(n+n%3)/2-[(t+1)/2+k%2*(3*t+k)%2]}/2
=n/3+1+[(n/3+1)(n+n%3)/2-(n/3+1)/2-n%3%2*n%2]/2
整理一下就可得到上述代码中的公式