首页 > 其他 > 详细

@一句话题解 - 2020.03@

时间：2020-03-04 16:07:58      阅读：77      评论：0      收藏：0      [点我收藏+]

咕咕咕。

这些题目倒不一定是我 3 月才做的，有可能是我之前做了现在才写的题解。

topcoder - SRM545D1L3：按位考虑，除非该位全是 1，否则两边必须各自至少有一个 0。容斥哪些位有一边全为 1，利用并查集算出结果。

#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;

class SetAndSet{
    public:
        int a[20][50], cnt[20], fa[20][50];
        int find(int t, int x) {return fa[t][x] = (fa[t][x] == x ? x : find(t, fa[t][x]));}
        bool unite(int t, int x, int y) {
            int fx = find(t, x), fy = find(t, y);
            if( fx != fy ) {
                fa[t][fx] = fy;
                return true;
            }
            else return false;
        }
        ll ans; int n;
        void dfs(int d, int k, int f) {
            if( d == 20 ) {
                ans += f*((1LL << k) - 2);
                return ;
            }
            if( d )
                for(int i=0;i<n;i++) fa[d][i] = fa[d-1][i];
            else for(int i=0;i<n;i++) fa[d][i] = i;
            dfs(d + 1, k, f);
            if( cnt[d] ) {
                for(int i=1;i<cnt[d];i++)
                    if( unite(d, a[d][0], a[d][i]) ) k--;
                dfs(d + 1, k, -f);
            }
        }
        ll countandset(vector<int>A) {
            n = A.size();
            for(int i=0;i<20;i++) {
                cnt[i] = 0;
                for(int j=0;j<n;j++)
                    if( !((A[j] >> i) & 1) ) a[i][cnt[i]++] = j;
            }
            dfs(0, n, 1);
            return ans;
        }
};

ZOJ - 4064：考虑容斥，枚举哪些格子禁止覆盖。只有相邻禁止覆盖的格子才有贡献，所以记 dp[i][j] 表示最近一个禁止覆盖位置为 i，有 j 个可以选择覆盖的区间的方案数*容斥系数，转移随便做。本题有点卡常。

#include <cstdio>

const int MAXN = 100;
const int MOD = int(1E9) + 7;

inline int add(int x, int y) {return (x + y >= MOD ? x + y - MOD : x + y);}
inline int sub(int x, int y) {return (x - y < 0 ? x - y + MOD : x - y);}
inline int mul(int x, int y) {return 1LL * x * y % MOD;}

int pow_mod(int b, int p) {
    int ret = 1;
    for(int i=p;i;i>>=1,b=mul(b,b))
        if( i & 1 ) ret = mul(ret, b);
    return ret;
}

int f[MAXN + 5][MAXN*MAXN + 5], A[MAXN + 5], n, m;

void solve() {
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++)
        scanf("%d", &A[i]);
    A[n + 1] = f[0][0] = 1;
    for(int i=0;i<=n;i++) {
        int t = i*(i + 1)/2;
        for(int j=0;j<=t;j++) {
            if( f[i][j] ) {
                for(int k=i+1;k<=n+1;k++) {
                    if( A[k] == 1 ) {
                        f[k][j+(k-i)*(k-i-1)/2] = add(f[k][j+(k-i)*(k-i-1)/2], f[i][j]);
                        break;
                    }
                    else if( A[k] == 2 )
                        f[k][j+(k-i)*(k-i-1)/2] = sub(f[k][j+(k-i)*(k-i-1)/2], f[i][j]);
                }
            }
        }
    }
    int ans = 0, t = n*(n + 1)/2;
    for(int i=0;i<=t;i++)
        ans = add(ans, mul(f[n+1][i], pow_mod(i, m)));
    for(int j=0;j<=n+1;j++)
        for(int k=0;k<=t;k++)
            f[j][k] = 0;
    printf("%d\n", ans);
}

int main() {
    int T; scanf("%d", &T);
    while( T-- ) solve();
}

topcoder - SRM583D1L3：min-max 容斥。枚举行的子集，根据贡献的表达式，对于列作个简单的背包。

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

class RandomPaintingOnABoard{
    public:
        int a[150][150], s[150], b[150], S, n, m;
        double ans; long long dp[150*9];
        void dfs(int d, int f, int t) {
            if( d == n ) {
                int tot; dp[tot = 0] = 1;
                for(int i=0;i<m;i++) {
                    for(int j=tot+1;j<=tot+b[i];j++)
                        dp[j] = 0;
                    tot += b[i];
                    for(int j=tot;j>=b[i];j--)
                        dp[j] = dp[j] - dp[j-b[i]];
                }
                for(int i=0;i<=tot;i++)
                    if( i + t ) ans += 1.0*f*dp[i]*S/(i + t);
                return ;
            }
            dfs(d + 1, f, t);
            for(int i=0;i<m;i++) b[i] -= a[d][i], t += a[d][i];
            dfs(d + 1, -f, t);
            for(int i=0;i<m;i++) b[i] += a[d][i], t -= a[d][i];
        }
        double expectedSteps(vector<string>p) {
            n = (int)p.size(), m = (int)p[0].size();
            if( n < m ) {
                for(int i=0;i<n;i++)
                    for(int j=0;j<m;j++)
                        a[i][j] = p[i][j] - '0', S += a[i][j];
            }
            else {
                for(int i=0;i<n;i++)
                    for(int j=0;j<m;j++)
                        a[j][i] = p[i][j] - '0', S += a[j][i];
                swap(n, m);
            }
            for(int j=0;j<m;j++)
                for(int i=0;i<n;i++)
                    b[j] += a[i][j];
            dfs(0, -1, 0);
            return ans;
        }
};

topcoder - 2016 TCO Algorithm Algo Final D1L3：首先做个 O(3^k) 的状压 dp 求出每个小图剖分成 i 条路径的方案数 f[i]。相当于 n 个图每个图都剖分成小路径然后将这些路径进行排列，并要求来源相同的路径不能相邻。不能相邻是一个经典容斥，路径全排列可以看作指数型生成函数的幂。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MOD = 998244353;
const int MAXN = 50000;
const int MAXK = 14;
const int MAXM = 2*MAXN*MAXK;

inline int add(int x, int y) {return (x + y >= MOD ? x + y - MOD : x + y);}
inline int sub(int x, int y) {return (x - y < 0 ? x - y + MOD : x - y);}
inline int mul(int x, int y) {return 1LL * x * y % MOD;}

int pow_mod(int b, int p) {
    int ret = 1;
    for(int i=p;i;i>>=1,b=mul(b,b))
        if( i & 1 ) ret = mul(ret, b);
    return ret;
}

class HamiltonianPaths{
    private :
        int dp1[14][1<<14], g[1<<14], dp2[15][1<<14], bts[1<<14], f[15];
        int lowbit(int x) {return x & -x;}
        void get1() {
            int t = (1 << k);
            for(int i=0;i<k;i++) dp1[i][1<<i] = 1;
            for(int s=1;s<t;s++) {
                if( s != lowbit(s) ) {
                    for(int i=0;i<k;i++)
                        if( (s >> i) & 1 ) {
                            int s2 = s ^ (1 << i);
                            for(int j=0;j<k;j++)
                                if( ((s2 >> j) & 1) && (G[j] & (1 << i)) )
                                    dp1[i][s] = add(dp1[i][s], dp1[j][s2]);
                        }
                }
                for(int i=0;i<k;i++)
                    g[s] = add(g[s], dp1[i][s]);
            }
            dp2[0][0] = 1;
            for(int s=1;s<t;s++) {
                int s2 = s, q = lowbit(s); bts[s] = bts[s>>1] + (s & 1);
                do {
                    if( s2 & q ) {
                        for(int p=1;p-1<=bts[s^s2]&&p<=bts[s];p++)
                            dp2[p][s] = add(dp2[p][s], mul(g[s2], dp2[p-1][s^s2]));
                    }
                    if( !s2 ) break;
                    s2 = (s2 - 1) & s;
                }while( true );
            }
            for(int i=1;i<=k;i++) f[i] = dp2[i][t-1];
        }
        int a[15], b[15][15], c[15][15], fct[MAXM + 5];
        void get2() {
            for(int i=0;i<=k;i++) {
                c[i][0] = 1;
                for(int j=1;j<=i;j++)
                    c[i][j] = add(c[i-1][j], c[i-1][j-1]);
            }
            fct[0] = 1;
            for(int i=1;i<=n*k;i++) fct[i] = mul(fct[i-1], i);
            for(int i=1;i<=k;i++) {
                for(int j=0;j<=i;j++)
                    for(int p=0;p<=i;p++)
                        b[j][p] = 0;
                b[0][i] = 1;
                for(int j=1;j<=i;j++) {
                    for(int p=1;p<=i;p++)
                        for(int q=1;q<=p;q++) {
                            int del = mul(mul(c[p][q], fct[q]), b[j-1][p]);
                            b[j][p-q] = (q & 1 ? add(b[j][p-q], del) : sub(b[j][p-q], del));
                        }
                }
                for(int j=1;j<=i;j++)
                    a[j] = add(a[j], mul(f[i], b[j][0]));
            }
            for(int i=1;i<=k;i++) a[i] = mul(a[i], pow_mod(fct[i], MOD - 2));
        }
        int w[22], iw[22], inv[MAXM + 5];
        void ntt(int *A, int n, int type) {
            for(int i=0,j=0;i<n;i++) {
                if( i < j ) swap(A[i], A[j]);
                for(int k=(n>>1);(j^=k)<k;k>>=1);
            }
            for(int i=1;(1<<i)<=n;i++) {
                int s = (1 << i), t = (s >> 1);
                int u = (type == 1 ? w[i] : iw[i]);
                for(int j=0;j<n;j+=s) {
                    for(int k=0,p=1;k<t;k++,p=mul(p,u)) {
                        int x = A[j+k], y = mul(A[j+k+t], p);
                        A[j+k] = add(x, y), A[j+k+t] = sub(x, y);
                    }
                }
            }
            if( type == -1 ) {
                int iv = inv[n];
                for(int i=0;i<n;i++)
                    A[i] = mul(A[i], iv);
            }
        }
        int length(int n) {
            int len; for(len = 1; len <= n; len <<= 1);
            return len;
        }
        void init() {
            for(int i=0;i<22;i++) {
                w[i] = pow_mod(3, (MOD - 1) / (1 << i));
                iw[i] = pow_mod(w[i], MOD - 2);
            }
            inv[1] = 1;
            for(int i=2;i<=MAXM;i++)
                inv[i] = sub(0, mul(MOD/i, inv[MOD%i]));
        }
        int A[MAXM + 5], B[MAXM + 5];
        int get3() {
            init();
            int tmp = n, nA = 0, nB = k;
            for(int i=1;i<=k;i++) B[i] = a[i];
            A[0] = 1;
            while( true ) {
                if( tmp & 1 ) {
                    int len = length(nA + nB);
                    ntt(A, len, 1), ntt(B, len, 1);
                    for(int i=0;i<len;i++)
                        A[i] = mul(A[i], B[i]);
                    ntt(A, len, -1), ntt(B, len, -1);
                    nA += nB;
                }
                tmp >>= 1;
                if( tmp == 0 ) break;
                int len = length(nB * 2);
                ntt(B, len, 1);
                for(int i=0;i<len;i++)
                    B[i] = mul(B[i], B[i]);
                ntt(B, len, -1);
                nB *= 2;
            }
            int ans = 0;
            for(int i=n;i<=n*k;i++)
                ans = add(ans, mul(fct[i], A[i]));
            return ans;
        }
    public :
        int G[14], n, k;
        int countPaths(int _k, vector<int>a, vector<int>b, int _n) {
            int m = (int)a.size(); k = _k, n = _n;
            for(int i=0;i<k;i++) G[i] = (1 << k) - 1;
            for(int i=0;i<m;i++) G[a[i]] ^= (1 << b[i]), G[b[i]] ^= (1 << a[i]);
            get1(), get2();
            return get3();
        }
};

atcoder - AGC005D：显然容斥，记 f[j] 表示有多少方案使得满足 |ai - i| = K 的 i 数量为 j，求出 f[j] 之后很简单。可以把相差为 K 的数字放在一起做 dp，然后全局再做个背包即可 O(n^2) 求 f。

#include <cstdio>

const int MOD = 924844033;
const int MAXN = 2000;

inline int add(int x, int y) {return (x + y >= MOD ? x + y - MOD : x + y);}
inline int sub(int x, int y) {return (x - y < 0 ? x - y + MOD : x - y);}
inline int mul(int x, int y) {return 1LL * x * y % MOD;}

int fct[MAXN + 5];
int f[2][2][MAXN + 5], h[2][2][MAXN + 5], g[MAXN + 5], t;
void init() {
    fct[0] = 1;
    for(int i=1;i<=MAXN;i++)
        fct[i] = mul(fct[i-1], i);
    g[t = 0] = 1;
}

void insert(int m) {
    for(int i=0;i<=t;i++)
        f[0][0][i] = f[0][1][i] = f[1][1][i] = 0, f[1][0][i] = g[i];
    for(int i=1;i<=m;i++) {
        for(int j=0;j<=t;j++)
            for(int p=0;p<=1;p++)
                for(int q=0;q<=1;q++)
                    h[p][q][j] = f[p][q][j], f[p][q][j] = 0;
        t++, f[0][0][t] = f[0][1][t] = f[1][0][t] = f[1][1][t] = 0;
        for(int j=0;j<=t;j++)
            for(int p=0;p<=1;p++)
                for(int q=0;q<=1;q++) {
                    f[q][0][j] = add(f[q][0][j], h[p][q][j]);
                    if( p == 0 ) {
                        f[q][0][j+1] = sub(f[q][0][j+1], h[p][q][j]);
                        f[q][1][j+1] = sub(f[q][1][j+1], h[p][q][j]);
                    }
                    else f[q][1][j+1] = sub(f[q][1][j+1], h[p][q][j]);
                }
    }
    for(int i=0;i<=t;i++) g[i] = add(f[0][0][i], f[1][0][i]);
}

int a[MAXN + 5], N, K;
int main() {
    init(), scanf("%d%d", &N, &K);
    for(int i=1;i<=N;i++) a[i % K]++;
    for(int i=0;i<K;i++) insert(a[i]);
    int ans = 0;
    for(int i=0;i<=N;i++)
        ans = add(ans, mul(fct[N-i], g[i]));
    printf("%d\n", ans);
}

atcoder - AGC012D：如果 wi 与同颜色最小的 minw[ci] 相加 <= X，则可以把 wi 等价改成 w‘i = minw[ci]。修改过后，如果一个元素的 wi 与异色最小的 wj 相加 <= Y，则认为这个元素是可动的。最终答案即这些可动的元素的可重排列。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 200000;
const int MOD = int(1E9) + 7;
const int INF = (1<<30);

int pow_mod(int b, int p) {
    int ret = 1;
    for(int i=p;i;i>>=1,b=1LL*b*b%MOD)
        if( i & 1 ) ret = 1LL*ret*b%MOD;
    return ret;
}

int fct[MAXN + 5], ifct[MAXN + 5];
void init() {
    fct[0] = 1;
    for(int i=1;i<=MAXN;i++)
        fct[i] = 1LL*i*fct[i-1]%MOD;
    ifct[MAXN] = pow_mod(fct[MAXN], MOD - 2);
    for(int i=MAXN-1;i>=0;i--)
        ifct[i] = 1LL*ifct[i+1]*(i+1)%MOD;
}

int c[MAXN + 5], w[MAXN + 5], N, X, Y;
int mn[MAXN + 5], cnt[MAXN + 5];

int main() {
    init(), scanf("%d%d%d", &N, &X, &Y);
    for(int i=1;i<=N;i++) mn[i] = INF;
    for(int i=1;i<=N;i++) {
        scanf("%d%d", &c[i], &w[i]);
        mn[c[i]] = min(mn[c[i]], w[i]);
    }
    for(int i=1;i<=N;i++)
        if( mn[c[i]] + w[i] <= X )
            w[i] = mn[c[i]];
    int fmn = -1, smn = -1;
    for(int i=1;i<=N;i++)
        if( mn[i] != INF ) {
            if( fmn == -1 || mn[fmn] > mn[i] )
                smn = fmn, fmn = i;
            else if( smn == -1 || mn[smn] > mn[i] )
                smn = i;
        }
    int tot = 0;
    for(int i=1;i<=N;i++) {
        if( c[i] == fmn ) {
            if( smn != -1 && w[i] + mn[smn] <= Y )
                cnt[c[i]]++, tot++;
        }
        else {
            if( w[i] + mn[fmn] <= Y )
                cnt[c[i]]++, tot++;
        }
    }
    int ans = fct[tot];
    for(int i=1;i<=N;i++)
        ans = 1LL*ans*ifct[cnt[i]]%MOD;
    printf("%d\n", ans);
}

atcoder - AGC013E：没有限制时，长度为 i 的权值对应的生成函数是 \(F(x) = \frac{(1-x)^3}{-x^3+2x^2-4x+1}\)，满足递推公式 \(f_n = 4f_{n-1} - 2f_{n-2} + f_{n-3}\)，可以矩阵的幂描述 \(f_n\)。考虑容斥，枚举强制断开，并使用 dp。记上一次强制断开为 i 时权值为 dp[i]。朴素转移 O(n^2)。注意转移总是乘上矩阵的某个幂（对应某个 \(f_i\)），可以所有状态批量转移。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MOD = int(1E9) + 7;
const int MAXM = 100000;

inline int add(int x, int y) {return (x + y >= MOD ? x + y - MOD : x + y);}
inline int sub(int x, int y) {return (x - y < 0 ? x - y + MOD : x - y);}
inline int mul(int x, int y) {return 1LL * x * y % MOD;}

struct matrix{
    int m[3][3], r, c;
    matrix() {memset(m, 0, sizeof m);}
    friend matrix operator + (matrix A, matrix B) {
        matrix C; C.r = A.r, C.c = B.c;
        for(int i=0;i<C.r;i++)
            for(int j=0;j<C.c;j++)
                C.m[i][j] = add(A.m[i][j], B.m[i][j]);
        return C;
    }
    friend matrix operator * (matrix A, matrix B) {
        matrix C; C.r = A.r, C.c = B.c;
        for(int i=0;i<C.r;i++)
            for(int k=0;k<A.c;k++)
                for(int j=0;j<C.c;j++)
                    C.m[i][j] = add(C.m[i][j], mul(A.m[i][k], B.m[k][j]));
        return C;
    }
    friend matrix mpow(matrix A, int p) {
        matrix ret; ret.r = ret.c = A.r;
        for(int i=0;i<ret.r;i++)
            for(int j=0;j<ret.c;j++)
                ret.m[i][j] = (i == j);
        while( p ) {
            if( p & 1 ) ret = ret*A;
            A = A*A;
            p >>= 1;
        }
        return ret;
    }
}A, B, S;

void init() {
    A.r = A.c = 3;
    A.m[0][0] = 4, A.m[0][1] = MOD - 2, A.m[0][2] = 1;
    A.m[1][0] = A.m[2][1] = 1;
    B.r = 3, B.c = 1;
    B.m[0][0] = 5, B.m[1][0] = 1, B.m[2][0] = 0;
}

matrix get(int x) {
    matrix R; R.r = R.c = 3;
    R.m[0][0] = R.m[1][1] = R.m[2][2] = x;
    return R;
}

int f[MAXM + 5], X[MAXM + 5], N, M;
int main() {
    init(); scanf("%d%d", &N, &M);
    for(int i=1;i<=M;i++) scanf("%d", &X[i]);
    X[M + 1] = N, f[0] = -1, S = get(sub(0, f[0]));
    for(int i=1;i<=M+1;i++) {
        S = S * mpow(A, X[i] - X[i-1]);
        f[i] = (S*B).m[2][0];
        S = (S + get(sub(0, f[i])));
    }
    printf("%d\n", (S*B).m[2][0]);
}

@一句话题解 - 2020.03@

原文：https://www.cnblogs.com/Tiw-Air-OAO/p/12409459.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！