容斥 / dp

P1450 [HAOI2008] 硬币购物
$c_i$太大，每次做一次背包T
首先可以用完全背包处理出无限制的方案数，然后考虑怎么剪去不合法状态
因为物品数很少，不合法状态就是各物品超出限制后的并集，可以状压枚举那几个物品超出了限制，然后容斥解决

void yrzr(){
    std::vector<int> c(5);
    std::vector<ll> f(100005);
    for (int i=1;i<=4;i++){
        std::cin>>c[i];
    }
    f[0]=1;
    for (int i=1;i<=4;i++){
        for (int j=c[i];j<=100000;j++){
            f[j]+=f[j-c[i]];
        }
    }
    int n;
    std::cin>>n;
    while (n--){
        std::vector<int> d(5);
        for (int i=1;i<=4;i++){
            std::cin>>d[i];
        }
        int s;
        std::cin>>s;

        ll ans=0;
        for (int mask=1;mask<(1<<4);mask++){
            int now=0;
            for (int i=1;i<=4;i++){
                if (mask&(1<<(i-1))){
                    now+=(d[i]+1)*c[i];
                }
            }
            now=s-now;
            if (now>=0){
                if (__builtin_popcount(mask)&1){
                    ans+=f[now];
                }else{
                    ans-=f[now];
                }
            }
        }
        std::cout<<f[s]-ans<<"\n";
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

P2398 GCD SUM
CF1043F Make It One
CF547C Mike and Foam
一类问题：选出几个数，然后问这几个数的gcd为$x$的选取方案数
考虑用$f_i$表示gcd为$i$的方案数，然后可以逆推，首先可以直接求出$gcd$的个数，然后容斥剪去$gcd!=i$的方案数即可，发现复杂度是一个级数求和，$O(nlogn)$

void yrzr(){
    int n;
    std::cin>>n;
    std::vector<ll> f(n+1);

    ll ans=0;
    for (int i=n;i>=1;i--){
        f[i]=1LL*(n/i)*(n/i);
        for (int j=2*i;j<=n;j+=i){
            f[i]-=f[j];
        }
        ans+=1LL*f[i]*i;
    }
    std::cout<<ans<<"\n";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15