A simple Blog for wyx I've been down the bottle hoping.
UNR#2 智障划水记
发表于: | 分类: Oi | 评论:0 | 阅读:142

我真是服了我自己了,一场比赛先是叉掉了自己正确的做法,然后又实力判错了T2,最后T3大傻*题还没想出来,然后标准分都没到感觉这样吃枣药丸啊,得调整一下,争取下一场翻到前30。

先说T1吧,T1现在我至少知道三个做法了我就说其中比较简单的两个吧

我最开始口胡口胡出了正解……然后被一个傻逼错误绕进去最后写了一个更麻烦的做法

首先要考虑到假设我现在有了一个合法状态,然后我们把所有的颜色按照他的一个排列重新标号,那么就得到了所有的方案数。注意到$\pmod 6$所以其实当用超过两种颜色染色的时候答案必然都是0,因为贡献中必然会有$3!$

然后就是两种颜色染图然后不能有相邻颜色相同了,答案显然是$2^t$, t是联通块的个数,注意到如果有图不是二分图答案直接就是 0

然后就没有然后了

我写了另外一个做法,还是先判断是不是二分图,然后一个图他的方案数显然是 $k\times (k-1)^{(size-1)}$

因为第一个点可以随便选,接下来的点显然就只有k-1种方案了,注意到二分图必然只有偶环,所以最后一个点和第一个点没有互相限制的约束

感觉就是送分的吧

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+5;
const int M = N << 2;
const int mod = 6;

inline int pow(int a,int b) {
    a %= mod;
    int res = 1;
    for(;b;b>>=1,a=a*a%mod)
        if(b&1)
            res =res * a % mod;
    return res;
}

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int head[N];

struct graph {
    int next, to;
    graph () {}
    graph (int _next,int _to)
    :next(_next), to(_to) {}
}edge[M];

int cnt, col[N];

inline void add(int x,int y) {
    edge[++cnt] = graph(head[x], y); head[x] = cnt;
    edge[++cnt] = graph(head[y], x); head[y] = cnt;
}

bool flag;

inline void DFS(int x, int p, int &size) {

    if(col[x] == -1) {
        size ++;
        col[x] = p;
    }

    for(int i = head[x]; i && !flag; i = edge[i].next) {
        if(col[edge[i].to] == -1) 
            DFS(edge[i].to, p ^ 1, size);
        else if(col[edge[i].to] + col[x] != 1) {
            flag = true;
            return;
        }
    }
}

int main() {
    int T;
    cin >> T;
    memset(col, -1, sizeof col);
    while(T--) {
        int n, m, k;
        cin >> n >> m >> k;
        for(int i = 1; i <= m; ++ i) {
            int x = read(), y = read();
            add(x, y);
        }
        int temp = 1, p;
        for(int i = 1; i <= n && !flag; ++ i) 
            if(col[i] == -1) {
                p = 0; DFS(i, 0, p); 
                temp = temp * k % mod * pow(k-1, p-1) % mod;
            }
        if(flag) puts("0");
        else printf("%d\n", temp);
        for(int i = 1; i <= n; ++ i) col[i] = -1;
        for(int i = 1; i <= n; ++ i) head[i] = 0;
        cnt = 0;
        flag = false;
    }
}

T2

我服了我自己了,数据范围5000达成3000,然后最后还没判断d=0,感觉自己变成智障。

正解非常神是链表的启发式合并,还是去看UOJ 吉司机的题解吧

T3做题的时候没剩多长时间了,差点就做出来了qwq

挺好的一个题,首先你需要get到这个题的一套dp的理论,然后你会发现我们可以构造多项式${P_n}$,满足$P_0 = 1, P_{a_i} = 2$,考虑 $FWT$这套理论都是线性变换,所以每个位置的数字显然不是-1就是3(因为0位置对每个数字的贡献都是1,然后$a_i$对一个位置的贡献如果是2那就是3,如果是-2那就是-1,所以不是-1就是3),然后考虑直接解个一元一次方程解出每个位置有多少个3,多少-1,然后快速幂就行了

我tm这都没做出来,真是想找块豆腐撞死啊

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e6+5;
const int Max = 1 << 20;
const int mod = 998244353;
const int inv2 = (mod+1) >> 1;
typedef long long LL;

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int pwn[Max<<1|111], n, a[Max<<1|111];

inline void FWT(int *a,int n) {
    for(int k = 1; k < 1 << n; k <<= 1) {
        for(int i = 0; i < 1 << n; i ++) {
            if(i & k) continue;
            LL temp = (a[i] + a[i+k]) % mod ;
            a[i+k] = (a[i] - a[i+k] + mod) % mod;
            a[i] = temp;
        }
    }
}

void iFWT(int *a,int n) {
    for(int k = 1; k < 1 << n; k <<= 1) {
        for(int i = 0; i <  1 << n ; ++ i) {
            if(i & k) continue;
            LL temp = (LL)(a[i] + a[i+k]) * inv2 % mod;
            a[i+k] = (a[i] - a[i+k] + mod) * inv2 % mod;
            a[i] = temp;
        }
    }
}

int main() {
    pwn[0] = 1;
    for(int i = 1 ; i < Max; ++ i) pwn[i] = (LL) pwn[i-1] * 3 % mod;
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++ i) {
        int x = read();
        a[x] ++;
    }
    FWT(a, 20);
    for(int i = 0; i < Max; ++ i) {
        int x = ((LL)n + a[i] + mod) % mod / 2 ,
            y = ((LL)n - a[i] + mod) % mod / 2;
        a[i] = pwn[x];
        if(y & 1) a[i] = mod - a[i];
    }
    iFWT(a, 20);
    printf("%d\n", (a[0] - 1 + mod) % mod);
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP