Codeforces Round #309 (Div. 1), problem: (C) Love Triangles

可以發現love的關係是等價關係，
然後這世界只有兩種值: 0, 1

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

typedef long long int int64;
const int64 P = 1000000007;

typedef vector<int> VI;

int Fat(VI& fat, int a){return (fat[a] == a) ? a: fat[a] = Fat(fat, fat[a]);}
void Onion(VI& fat, int a, int b){fat[Fat(fat, a)] = Fat(fat, b);return;}

struct _rel{int a, b, c;};

_rel rel[100000];

int main(){
    int n, k; scanf("%d %d", &n, &k);
    for(int lx = 0;lx < k;lx++){
        scanf("%d %d %d", &rel[lx].a, &rel[lx].b, &rel[lx].c);
        rel[lx].a--, rel[lx].b--;
    }

    VI test(2*n);
    for(int lx = 0;lx < 2*n;lx++) test[lx] = lx;
    for(int lx = 0;lx < k;lx++){
        if(rel[lx].c)
            Onion(test, rel[lx].a, rel[lx].b),
            Onion(test, rel[lx].a+n, rel[lx].b+n);
        else
            Onion(test, rel[lx].a, rel[lx].b+n),
            Onion(test, rel[lx].b, rel[lx].a+n);
    }
    
    bool check = true;
    for(int lx = 0;lx < n and check;lx++)
        if(Fat(test, lx) == Fat(test, lx+n))
            check = false;
    if(!check){
        puts("0");
        return 0;
    }

    for(int lx = 0;lx < n;lx++)
        Onion(test, lx, lx+n);

    set<int> sign;
    int64 ans = (1+P)/2;
    for(int lx = 0;lx < n;lx++){
        if(sign.count(Fat(test, lx))) continue;
        ans = (ans*2)%P;
        sign.insert(Fat(test, lx));
    }

    printf("%d\n", (int)ans);

    return 0;
}

Codeforces Round #309 (Div. 1), problem: (A) Kyoya and Colored Balls

#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

typedef long long int int64;

int64 mut[1000001];;

const int64 P = 1000000007;

int64 npow(int64 a, int n){
    if(!n) return 1;
    int64 g = npow(a, n>>1);
    g = (g*g)%P;
    if(n&1) return (g*a)%P;
    return g;
}

int64 rev(int64 n){ return npow(n, P-2);}

int64 C(int64 a, int64 b){
    int64 ret = mut[a];
    ret *= rev(mut[b]); ret %= P;
    ret *= rev(mut[a-b]); ret %= P;
    return ret;
}

int main(){
    mut[0] = 1;
    for(int lx = 1;lx <= 1000000;lx++)
        mut[lx] = (mut[lx-1]*lx)%P;

    int n; scanf("%d", &n);
    int64 ans = 1; int sum = 0;
    for(int lx = 0;lx < n;lx++){
        int k; scanf("%d", &k);
        ans *= C(sum+k-1, sum);
        ans %= P;
        sum += k;
    }
    printf("%d\n", (int)ans);
    return 0;
}