zcmimi's blog
查看原题

点击跳转

g(x)=(1+x+x^2+x^3+...)(1+x^2+x^4+x^6+...)(1+x^3+x^6+x^9+...)...

模拟一下

\Theta(n^2)

#include<bits/stdc++.h>
#define Fur(i,x,y) for(int i=x;i<=y;++i)
const int N=121;
int n,a[2][N];
int main(){
    Fur(i,0,120)a[1][i]=1;
    Fur(i,2,120){
        memset(a[i&1],0,sizeof a[i&1]);
        int p=0;
        while(p<=120){
            Fur(j,0,120-p)a[i&1][p+j]+=a[!(i&1)][j];
            p+=i;
        }
    }
    while(~scanf("%d",&n))printf("%d\n",a[0][n]);
}
HDU 1028 Ignatius-and-the-Princess-III
comment评论
Search
search