Kickstart Round H 2018

打了ks好久都没有更新

诶，自己的粗心真的是没救了，A题大数据都能错

A

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <cstring>

#include <vector>

#include <list>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <bitset>

#include <algorithm>

#include <functional>

#include <assert.h>

#include <iomanip>

using namespace std;

// const int N = 7005;

// const int M = 2e5 + 5;

const int INF = 0x3f3f3f3f;

const int MOD = 1000000007;

typedef long long ll;

char seq[105][55];

int tot, Root;

int nx[10005][2];

int tag[10005];

int newNode() {

    nx[tot][0] = nx[tot][1] = -1; tag[tot] = 0;

    return tot ++;

}

int N, P;

void Insert(char* s) {

    int len = strlen(s);

    int root = Root;

    for(int i = 0; i < len; ++i) {

        int id = s[i] == 'R';

        if(nx[root][id] == -1) {

            nx[root][id] = newNode();

        }

        root = nx[root][id];

    }

    tag[root] ++;

}

ll dfs(int rt, int deep) {

    if(tag[rt]) return 1ll<<(N - deep);

    ll ans = 0;

    if(nx[rt][0] != -1) ans += dfs(nx[rt][0], deep + 1);

    if(nx[rt][1] != -1) ans += dfs(nx[rt][1], deep + 1);

    return ans;

}

int main() {

    freopen("A-large-practice2.in", "r", stdin);

    freopen("A-large-practice2.out", "w", stdout);

    int T;

    scanf("%d", &T);

    for(int _ = 1; _ <= T; ++_) {

        tot = 0;

        Root = newNode();

        scanf("%d %d", &N, &P);

        for(int i = 0; i < P; ++i) {

            scanf("%s", seq[i]);

            Insert(seq[i]);

        }

        printf("Case #%d: %lld\n", _, (1ll<<N) - dfs(Root, 0));

    }

    return 0;

}

B

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <cstring>

#include <vector>

#include <list>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <bitset>

#include <algorithm>

#include <functional>

#include <assert.h>

#include <iomanip>

using namespace std;

const int M = 5e6 + 5;

const int INF = 0x3f3f3f3f;

const int MOD = 1000000007;

typedef long long ll;

char seq[M];

int main() {

    freopen("B-large.in", "r", stdin);

    freopen("B-large.out", "w", stdout);

    int T;

    scanf("%d", &T);

    for(int _ = 1; _ <= T; ++_) {

        int n;

        scanf("%d %s", &n, seq + 1);

        int ans = 0; int tmp = 0;

        for(int i = 1; i <= (n+1)/2; ++i) {

            tmp += seq[i] - '0';

        }

        ans = max(ans, tmp);

        for(int i = (n+1)/2 + 1, j = 1; i <= n; ++i, ++j) {

            tmp -= seq[j] - '0';

            tmp += seq[i] - '0';

            ans = max(ans, tmp);

        }

        printf("Case #%d: %d\n", _, ans);

    }

    return 0;

}

C容斥原理

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <cstring>

#include <vector>

#include <list>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <bitset>

#include <algorithm>

#include <functional>

#include <assert.h>

#include <iomanip>

using namespace std;

// const int N = 7005;

const int M = 2e5 + 5;

const int INF = 0x3f3f3f3f;

const int MOD = 1000000007;

typedef long long ll;

ll Mul[M];

ll Pow(ll x, ll y) {

    ll ans = 1;

    while(y) {

        if(y & 1) ans = 1ll * ans * x % MOD;

        x = 1ll * x * x % MOD;

        y >>= 1;

    }

    return ans;

}

ll C(int x, int y) {

    if(y == 0) return 1;

    if(x == y) return 1;

    return 1ll* Mul[x] * Pow(Mul[y] * Mul[x - y] % MOD, MOD - 2) % MOD;

}

int main() {

    freopen("C-small-attempt0.in", "r", stdin);

    freopen("C-small-attempt0.out2", "w", stdout);

    int T;

    scanf("%d", &T);

    Mul[1] = 1;

    Mul[0] = 1;

    for(int i = 2; i < M; ++i) {

        Mul[i] = Mul[i-1] * i % MOD;

    }

    for(int _ = 1; _ <= T; ++_) {

        int n, m;

        scanf("%d %d", &n, &m);

        ll ans = Mul[2*n];

        int init = 2*n; ll mul2 = 1;

        for(int i = 1; i <= m; ++i) {

            init --;

            mul2 = mul2 * 2 % MOD;

            ll tmp = mul2 * Mul[init] % MOD * C(m, i) % MOD;

            ans = (ans + ( (i % 2) ? -tmp : tmp) + MOD) % MOD;

        }

        printf("Case #%d: %lld\n", _, ans);

    }

    return 0;

}