https://blog.csdn.net/zhoufenqin/article/details/9821617   详细讲解

 

#include
      
       #define ll long longusing namespace std;const int maxn=1e2+50;int a[maxn][maxn];int ans[maxn];int main(){    int n;    while(~scanf("%d",&n)){        for(int i=1;i<=n;i++){            for(int j=0;j<=n;j+=i){                a[i][j]=1;            }        }        for(int i=1;i<=n;i++){            if(i==1){                for(int j=0;j<=n;j++){                    ans[j]=a[i][j];                }            }            else {                for(int j=0;j<=n;j++){                    a[i-1][j]=ans[j]; ans[j]=0;                }                for(int j=0;j<=n;j++){                    for(int k=0;k<=n;k++){                        if(j+k>n) continue;                        ans[j+k]+=a[i-1][j]*a[i][k];                    }                }            }        }        printf("%d\n",ans[n]);        for(int i=0;i<=n;i++){            for(int j=0;j<=n;j++)            a[i][j]=0;            ans[i]=0;        }    }}
      

 '

#include
      
       using namespace std;const int maxn=8000+10;int a[maxn];int b[maxn];int c[maxn];int ans[maxn];int num[maxn];int main(){    int x,y,z;    while(cin>>x>>y>>z){        if(x==0 &&y==0 && z==0){
    break; }        int n=1*x+2*y+5*z;       //cout<
       
        <
        
         n) continue;                ans[i+j]+=a[i]*b[j];            }        }        for(int i=0;i<=n;i++){            for(int j=0;j<=n;j++){                if(i+j>n) continue;                num[i+j]+=ans[i]*c[j];            }        }        int k=n+1;        for(int i=1;i<=n;i++){            if(num[i]==0) k=min(i,k);        }        cout<
         
          <
         
        
       
      

 拆分数+广义五边形优化 

五边形数  (1ll*3*x*x-x)*inv2%mod;  

        五边形数范围  0-n;

广义五边形数范围   0 1 -1 2 -2 3 -3 

p(k) = p(k − 1) + p(k − 2) − p(k − 5) − p(k − 7) + p(k − 12) + p(k − 15)  − p(k − 22) − ... 

#include
      
       using namespace std;const int maxn=1e5+10;const int mod=1e9+7;const int inv2=(1+mod)/2;int wu[maxn];    // 0, 1, 2, 5, 7, 12, 15, 22, 26, 35....            //    i 0, 1, -1, 2, -2, 3, -3, 4, -4 , 5.....int flug[maxn];int chai[maxn];  // 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42 ,56,77,101,135......int five(int x){    return (1ll*3*x*x-x)*inv2%mod;}void init(){    wu[0]=five(0);    for(int i=1;i
      

拆分数

#include
      
       using namespace std;const int maxn=1e5+10;const int mod=1e9+7;const int inv2=(1+mod)/2;int wu[maxn];    // 0, 1, 2, 5, 7, 12, 15, 22, 26, 35....            //    i 0, 1, -1, 2, -2, 3, -3, 4, -4 , 5.....int flug[maxn];int chai[maxn];  // 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42 ,56,77,101,135......int cmp[maxn];int five(int x){    return (1ll*3*x*x-x)*inv2%mod;}void init(){    wu[0]=five(0);    for(int i=1;i
      

拆分数  + 广义五边形优化

背包  前缀和  思维

#include
      
       using namespace std;const int maxn=1e5+10;const int mod=1e9+7;const int inv2=(1+mod)/2;int wu[maxn];    // 0, 1, 2, 5, 7, 12, 15, 22, 26, 35....                 //i0, 1, -1, 2, -2, 3, -3, 4, -4 , 5.....int flug[maxn];int chai[maxn];  // 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42 ,56,77,101,135......int five(int x){ return (1ll*3*x*x-x)*inv2%mod; }void init(){    wu[0]=five(0);    for(int i=1;i
       
        =1ll*(a[i]+1)*i;j--){  // n*sqrt(n);            dp[j]-=dp[j-(a[i]+1)*i];            dp[j]=(dp[j]%mod+mod)%mod;        }    }}int num[maxn];void slove(int n){    num[0]=dp[0];    for(int i=1;i<=n;i++){        num[i]=num[i-1]+dp[i];        num[i]%=mod;    }    for(int i=n+1;i<=2*n;i++){        dp[i]-=num[i-n-1];    }    for(int i=0;i<=2*n;i++)  dp[i]=(dp[i]%mod+mod)%mod;}int32_t main(){    init();    int n,m;  int cs=0;    while(~scanf("%d %d",&n,&m)){        for(int i=1;i<=n;i++) scanf("%d",&a[i]);        for(int i=1;i<=m;i++) scanf("%d",&b[i]);        work(n);        slove(n);        int mm=0;        for(int i=1;i<=m;i++) {mm+=dp[2*n-b[i]]; mm=mm%mod;}                printf("Case #%d: ", ++cs);                printf("%d\n",mm);        for(int i=0;i<=2*n;i++){  a[i]=b[i]=dp[i]=num[i]=0; }    }    return 0;}/*3 31 2 3    //  2 6 122 3 3*/