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;
}

Codeforces Round #307 (Div. 2), problem: (D) GukiZ and Binary Operations

以前碰到的題目好像都有保證m > 1之類，看來以後要多注意._.

#include <cstdio>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long int int64;

int64 n, k, m;

int64 mul(int64 a, int64 b){
    return (a*b)%m;
}

int64 Pow(int64 a, int64 n){
    if(n == 0) return 1;
    if(n == 1) return a;
    int64 P = Pow(a, n>>1);
    P = mul(P, P);
    if(n&1) return mul(P, a);
    return P;
}

struct Mat{
    int64 a, b, c, d;
    Mat(int64 _a = 1, int64 _b = 0, int64 _c = 0, int64 _d = 1):
        a(_a%m), b(_b%m), c(_c%m), d(_d%m){return;}
};

Mat operator*(Mat& s, Mat& t){
    return Mat(mul(s.a,t.a) + mul(s.b,t.c),
               mul(s.a,t.b) + mul(s.b,t.d),
               mul(s.c,t.a) + mul(s.d,t.c),
               mul(s.c,t.b) + mul(s.d,t.d));
}

Mat Pow(Mat a, int64 n){
    if(n == 0) return Mat();
    if(n == 1) return Mat(a);
    Mat P = Pow(a, n>>1);
    P = P*P;
    if(n&1) return P*a;
    return P;
}

int main(){
    int l;
    scanf("%I64d %I64d %d %I64d", &n, &k, &l, &m);
    int64 ans = 1%m;
    Mat gg(Pow(Mat(0, 1, 1, 1), n-2));
    // b1 = 2, b2 = 3, b3 = 5
    int64 bb = (3*gg.a+5*gg.b)%m;
    int64 aa = (Pow(2, n)-bb+m)%m;
    for(int lx = 0;lx < l;lx++){
        if(k&1) ans = mul(ans, aa); 
        else ans = mul(ans, bb);
        k>>=1;
    }
    if(k) ans = 0;
    printf("%I64d\n", ans);
    return 0;
}

Codeforces Round #307 (Div. 2), problem: (B) ZgukistringZ

#include <cstdio>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long int int64;

char bufc[100010];
char stra[100010];
char strb[100010];

int cnta[26] = {0}, cntb[26] = {0}, cntc[26] = {0};

int gety(int x){
    int y = 100000000;
    for(int lx = 0;lx < 26;lx++){
        if(cntc[lx] < cnta[lx]*x) return -1;
        if(cntb[lx] != 0)
            y = min(y, (cntc[lx]-cnta[lx]*x)/cntb[lx]);
    }
    return y;
}

void build(char* str, int* cc){
    for(int lx = 0;str[lx] != 0;lx++)
        cc[str[lx]-'a']++;
    return;
}

void func(int* c1, int* c2){
    for(int lx = 0;lx < 26;lx++)
        c1[lx] -= c2[lx];
    return;
}

void print(int* a){
    for(int lx = 0;lx < 26;lx++)
        printf("%d ", a[lx]);
    puts("");
    return;
}

int main(){
    scanf("%s %s %s", bufc, stra, strb);
    build(bufc, cntc);
    build(stra, cnta);
    build(strb, cntb);
    
    int mx = 0, my = 0, mm = 0;
    for(int lx = 0;;lx++){
        int x = lx, y = gety(x);
        if(y >= 0 and x+y >= mm)
            mx = x, my = y, mm = x+y;
        if(y < 0)
            break;
    }
    
    for(int lx = 0;lx < mx;lx++){
        printf("%s", stra);
        func(cntc, cnta);
    }
    for(int lx = 0;lx < my;lx++){
        printf("%s", strb);
        func(cntc, cntb);
    }

    for(int lx = 0;lx < 26;lx++)
        while(cntc[lx]--)
            printf("%c", 'a'+lx);

    puts("");
    return 0;
}

Codeforces Round #307 (Div. 2), problem: (A) GukiZ and Contest

#include <cstdio>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long int int64;

int arr[10000];

int main(){
    int n; scanf("%d", &n);
    for(int lx = 0;lx < n;lx++) scanf("%d", arr+lx);
    for(int lx = 0;lx < n;lx++){
        int cc = 0; for(int ly = 0;ly < n;ly++) cc += arr[lx] < arr[ly];
        cc++;
        printf("%d ", cc);
    }
    puts("");
    return 0;
}

Codeforces Round #306 (Div. 2), problem: (E) Brackets in Implications

分三種：zerocnt = 1 or zerocnt = 2 or zerocnt = 3討論

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cassert>
using namespace std;

typedef long long int int64;

struct node{
    bool val;
    bool is_leaf;
    node *a, *b;
    node(bool v){
        val = v, is_leaf = true;
        return;
    }
    node(node* aa, node* bb){
        a = aa, b = bb; is_leaf = false;
        return;
    }

    void print(){
        if(is_leaf){printf("%d", val);return;}
        printf("(");
        a->print();
        printf(")->(");
        b->print();
        printf(")");
        return;
    }

};

int arr[100011];

vector<node*> build(int a, int b){
    vector<node*> ret;
    for(int lx = a;lx <= b;lx++)
        ret.push_back(new node(arr[lx]));
    return ret;
}

node* from_right(vector<node*> pp){
    assert(pp.size());
    node* prc = pp[(int)(pp.size())-1];
    for(int lx = (int)(pp.size())-2;lx >= 0;lx--)
        prc = new node(pp[lx], prc);
    return prc;
}

int main(){
    int n; scanf("%d", &n);
    for(int lx = 0;lx < n;lx++) scanf("%d", arr+lx);
    
    if(arr[n-1] != 0){
        puts("NO");
        return 0;
    }
    
    int zcnt = 0; for(int lx = 0;lx < n;lx++) zcnt += 1^arr[lx];
    
    if(zcnt == 1){
        puts("YES");
        from_right(build(0, n-1))->print();
        puts("");
    }else if(zcnt == 2){
        if(arr[n-2] == 0){
            puts("NO");
        }else{
            puts("YES");
            int z0, z1 = n-1; for(int lx = 0;lx < n-1;lx++) if(arr[lx] == 0){ z0 = lx; break;}
            (new node(
                new node(
                    from_right(build(0, z0)),
                    from_right(build(z0+1, z1-1))
                ),
                new node(0)
            ))->print();
            puts("");
        }
    }else{
        puts("YES");
        vector<node*> pp;
        int p1 = -1;
        for(int lx = 0;lx < n;lx++){
            if(arr[lx] == 1){
                if(p1 == -1) p1 = lx;
            }else{
                if(p1 == -1) pp.push_back(new node(0));
                else{
                    pp.push_back(from_right(build(p1, lx)));
                    p1 = -1;
                }
            }
        }
        node* tail = pp[(int)pp.size()-1];
        pp.pop_back();
        (new node(
            from_right(pp),
            tail
        ))->print();
        puts("");
    }
    return 0;
}