题目概要：可行性多重背包，但物品总数仅有 $2 \times 10^4$，最大可组成的价值为 $1.2\times 10^5$

拆成01背包后用bitset做的时间复杂度是：$O(n∑w_i \times \frac 1 w)$，其中 $w$ 应该为64？（不知道洛谷评测机cpu是多少位的）

疑问：

1. bitset本身的时间复杂度是不是错的？
2. 为什么同样是bitset，一份代码能过，另一份T飞了qwq

能过的代码（实际上是题解）：

评测记录

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 120005;
bitset <N> dp;
int a[10] ;
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int Case = 0;
    while(1) {
        Case++;
        int sum = 0;
        for(int i = 1; i <= 6; i++) cin >> a[i], sum += i * a[i] ;
        if(sum == 0) break ;
        cout << "Collection #" << Case << ":" << '\n';
        if(sum & 1) {
            cout << "Can't be divided." << '\n' << '\n';
            continue ;
        }
        dp.reset() ;
        dp.set(0) ;
        int ok = 0;
        for(int i = 1; i <= 6; i++) {
            for(int j = 1; j <= a[i]; j++) {
                dp |= (dp << i);
                if(dp[sum / 2]) ok = 1;
            }
        }
        if(ok) cout << "Can be divided." << '\n';
        else cout << "Can't be divided." <<'\n';
        cout << '\n';
    }
    return 0;
}

T飞的那份：

评测记录

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define of(i,a,b) for(int i=a;i>=b;--i)
#define P_B push_back
const int inf=0x3f3f3f3f;
const ll INF=9e18;
const int N=1e6+10;
bitset <N> f;
//f[i]:0/1 iÊÇ/·ñ ÄÜ×éºÏ³ö 
int a[16];
int main()
{
//	freopen("meow.out","w",stdout);//
	int CASE=1;
	while(1)
	{
		int sum=0;
		fo(i,1,6) {scanf("%d",&a[i]); sum+=a[i]*i;}
		if(!sum) break;
		printf("Collection #%d:\n",CASE);
		if(sum&1) printf("Can't be divided.");
		else 
		{
			f.reset(); f.set(0);
			fo(i,1,6)
				fo(j,1,a[i]) f |= (f<<i);
			if(f.test(sum>>1)) printf("Can be divided.");
			else printf("Can't be divided.");
		}
		++CASE; printf("\n\n");
	}
	return 0;
}
/*
in1:

out1:

*/