题目大意：给定n个物品，每个物品有一个体积，对于所有的 1≤i≤n,1≤j≤m 输出在不使用第 i 个物品的情况下装满大小为 j 的背包的方案数

我这傻逼居然真的去写了分治背包……
第i个物品存在的时间为 [1,i?1] 和 [i+1,n] 两个区间
然后分治……
时间复杂度 O(n2logn)
黄学长我仰慕您

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #define M 2020 using namespace std; struct abcd{ int l,r,x; abcd() {} abcd(int _,int __,int ___): l(_),r(__),x(___) {} }; int n,m; void Divide_And_Conquer(int x,int y,vector
        
          &v,vector
         
           a) { int i,j,mid=x+y>>1; vector
          
            l,r; for(i=0;i<(signed)v.size();i++) { abcd temp=v[i]; if(temp.l==x&&temp.r==y) for(j=m;j>=temp.x;j--) (a[j]+=a[j-temp.x])%=10; else if(temp.r<=mid) l.push_back(temp); else if(temp.l>mid) r.push_back(temp); else l.push_back(abcd(temp.l,mid,temp.x)),r.push_back(abcd(mid+1,temp.r,temp.x)); } if(x==y) { for(i=1;i<=m;i++) printf("%d",a[i]); puts(""); return ; } Divide_And_Conquer(x,mid,l,a); Divide_And_Conquer(mid+1,y,r,a); } int main() { int i,x; cin>>n>>m; vector
           
             v; for(i=1;i<=n;i++) { scanf("%d",&x); if(i!=1) v.push_back(abcd(1,i-1,x)); if(i!=n) v.push_back(abcd(i+1,n,x)); } vector
            
              a(m+1,0);a[0]=1; Divide_And_Conquer(1,n,v,a); return 0; }