ARC 096 Sol.

ARC 096 Sol.

C & D

两道 sb 题。1A 都嫌慢。

那我打 ABC 岂不是可以 AK.

#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
int main()
{
    int a, b, c, x, y; read(a, b, c); read(x, y);
    if(a + b <= 2 * c)
    {
        printf("%d\n", a * x + b * y);
        return 0;
    }
    if(x > y) swap(a, b), swap(x, y);
    int ret = x * 2 * c; y -= x;
    ret += min(y * b, y * 2 * c);
    printf("%d\n", ret);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const long long maxn = 1e5 + 5, maxc = 1e14 + 5;
long long sum[maxn], sum2[maxn], x[maxn], v[maxn], opt[maxn], opt2[maxn];
int main()
{
    int n; long long c; read(n, c);
    for(int i = 1; i <= n; ++i)
        read(x[i], v[i]);
    long long ret = 0, pos = 0, ret2 = 0, pos2 = 0;
    for(int i = 1; i <= n; ++i) 
    {
        sum[i] += sum[i - 1] - x[i] + x[i - 1] + v[i];
        opt[i] = opt[i - 1];
        if(sum[i] > opt[i]) opt[i] = sum[i], pos = i;
    }
    x[n + 1] = c;
    for(int i = n; i; --i) 
    {
        sum2[i] += sum2[i + 1] - x[i + 1] + x[i] + v[i];
        opt2[i] = opt2[i + 1];
        if(sum2[i] > opt2[i]) opt2[i] = sum2[i], pos2 = i;
    }
    long long ans = 0;
    for(int i = 1; i <= n; ++i)
    {
        ans = max(ans, max(sum[i], sum[i] - x[i] + opt2[i + 1]));
    }
    for(int i = n; i; --i)
    {
        ans = max(ans, max(sum2[i], sum2[i] - (c - x[i]) + opt[i - 1]));
    }
    printf("%lld\n", ans);
    return 0;
}

E

给 $ n\le5000 $ 个属性。要求选出一些集合，使得每个属性在所有集合出现两次以上。不能有两个集合属性完全一样。统计合法集合族的个数。

Sol.

考虑容斥。由对称性和二项式反演的知识有

$$ A=\sum_{i=0}^n (-1)^i{n\choose i}f_i $$

其中 $ f_i $ 表示 $ 1..i $ 每个属性至多只出现一次其余不管的方案数，那么 $ A $ 为全不满足这些限制的方案数。显然这就是所求答案。

考虑计算 $ f_i $ . 我们设辅助 $ g_{i,j} $ 表示 $ 1..i $ 每个属性恰好作用在 $ j $ 个集合之上（即这些集合没有空集），那么 $ f_i=2^{2^{n-i}}\sum_{j=0}^i g_{i,j}2^{(n-i)j} $ . 前面表示后面 $ n-i $ 种属性全不考虑的总数，后面表示当前考虑的这些属性的集合是不是还有其他属性存在。可以证明这样就是完备划分的：既不遗漏，又不重复。

计算 $ g_{i,j} $ 十分容易，由定义即有 $ g_{0,0}=1,g_{i,j}=g_{i-1,j-1}+(j+1)g_{i-1,j} $ .

#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 5e3 + 5;
int C[maxn][maxn], f[maxn][maxn];
int power(int a, int b, int p){int r = 1;for(; b;b >>= 1, a = 1ll * a * a % p)if(b & 1)r = 1ll * r * a % p; return r;}
int main()
{
    int n, m; read(n, m);
    C[0][0] = 1;
    for(int i = 1; i <= n; C[i][0] = 1, ++i) for(int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % m;
    f[0][0] = 1;
    for(int i = 1; i <= n; f[i][0] = 1, ++i) for(int j = 1; j <= i; ++j)
        f[i][j] = (f[i - 1][j - 1] + 1ll * f[i - 1][j] * (j + 1) % m) % m;
    int sum = 0;
    for(int i = 0, q = 1; i <= n; ++i, q = m - q)
    {
        int ret = 0, p = power(2, n - i, m);
        for(int j = 0; j <= i; ++j)
            (ret += 1ll * f[i][j] * power(p, j, m) % m) %= m;
        ret = 1ll * ret * power(2, power(2, n - i, m - 1), m) % m;
        ret = 1ll * ret * C[n][i] % m;
        ret = 1ll * ret * q % m;
        (sum += ret) %= m;
    }
    printf("%d\n", sum);
    return 0;
}

F

神仙题。不是很会会。待填。