【算法竞赛】AtCoder Beginner Contest 171F 172E 172F

171F - Strivore

#pragma GCC optimize(2)

#include <bits/stdc++.h>

#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e6+10, P = 1e9+7;

int n, m;
string s;
int fact[N], factInv[N];

int qpm(int a, int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = (LL)ans*a%P;
        a = (LL)a*a%P;
        b >>= 1;
    }
    return ans;
}
void PrevCalu() {
    fact[0] = 1;
    for(int i = 1; i <= n+m; i ++)
        fact[i] = (LL)fact[i-1]*i%P;
    factInv[n+m] = qpm(fact[n+m], P-2);
    for(int i = n+m-1; i >= 0; i --)
        factInv[i] = (LL)factInv[i+1]*(i+1)%P;
}
int C(int n, int m) {
    return (LL)fact[n]*factInv[n-m]%P*factInv[m]%P;
}
void solve() {
    cin >> m >> s;
    n = s.size();
    PrevCalu();
    int res = 0;
    for(int i = n; i <= n+m; i ++) {
        res = ((LL)res+(LL)qpm(26, n+m-i)*qpm(25, i-n)%P*C(i-1, n-1)%P)%P;
    }
    cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;  // << setprecision(20); // double
    // freopen("i.txt", "r", stdin);
    // freopen("o.txt", "w", stdout);
    // int Tcase;
    // cin >> Tcase; // scanf("%d", &Tcase);
    // while (Tcase--) 
    solve();
    return 0;
}

/*
C(i-1, n-1) 最后一位的位置确定了

n+|s|的字符串的子序列有s的个数
求方案，假设得到最终子串，贪心地选，即取连续的子串的第一个字母
xxxxxx|xxxx
子序列的最后到|的前一位，后面都有26种选法，前面都有25种选法
*/

172E - NEQ

#pragma GCC optimize(2)

#include <bits/stdc++.h>

#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 5e5+10, P = 1e9+7;

int n, m;
int fact[N], factInv[N];

int qpm(int a, int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = (LL)ans*a%P;
        a = (LL)a*a%P;
        b >>= 1;
    }
    return ans;
}
void PrevCalu() {
    fact[0] = 1;
    int mx = max(n, m); // ...
    for(int i = 1; i <= mx; i ++) 
        fact[i] = (LL)fact[i-1]*i%P;
    factInv[mx] = qpm(fact[mx], P-2);
    for(int i = mx-1; i >= 0; i --)
        factInv[i] = (LL)factInv[i+1]*(i+1)%P;
}
int A(int n, int m) {
    return (LL)fact[n]*factInv[n-m]%P;
}
int C(int n, int m) {
    return (LL)fact[n]*factInv[n-m]%P*factInv[m]%P;
}
void solve() {
    cin >> n >> m;
    PrevCalu();
    int res = 0;
    for(int i = 0; i <= n; i ++) {
        int x = (LL)C(n, i)*A(m, i)%P*A(m-i, n-i)%P*A(m-i, n-i)%P;
        res = ((LL)res + ((i&1) ? -1 : 1)*x)%P;
        res = ((LL)res+P)%P;
    }
    cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;  // << setprecision(20); // double
    // freopen("i.txt", "r", stdin);
    // freopen("o.txt", "w", stdout);
    // int Tcase;
    // cin >> Tcase; // scanf("%d", &Tcase);
    // while (Tcase--) 
    solve();
    return 0;
}
/*


从全错排的推导可以过来
https://zhuanlan.zhihu.com/p/133818995

1. 容斥原理
    也先和普通的全错排证明一样，先确定某几个位置A, B相同 a_i == b_i --- C(n, i)
    在把这i个数填上                                              --- A(m, i)
    在剩下的位置A和B都随便放                                      --- A(m-i, n-i) * A(m-i, n-i)


（DP我现在也不是很看得懂，只先写了普通错排的DP）
2. DP
    f[i], 为i位错排的方案数
    对即将要放的数，同普通的全错排的考虑
    将i放在k的位置，若k在i的位置，那么就不用考虑i和k了，剩下的错排
    再考虑有i-1种可能这样的情况                                   --- (i-1)*f[i-2]
    将i放在k的位置，而k不在i的位置，那么不管i（i已经合法，即已经错排）
    而这种情况，我们预设k不在i，那就可以把i的位置当作k的原本的位置
    除i外的i-1个数错排的方案数                                    --- (i-1)*f[i-1]
*/

172F - Unfair Nim

需要先知道Nim的结论

#pragma GCC optimize(2)

#include <bits/stdc++.h>

#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

int n;

void solve() {
    cin >> n;
    vector<LL> a(n);
    for(auto &x : a) cin >> x;
    LL Xor = 0, And = 0, Add = a[0]+a[1];
    for(int i = 2; i < n; i ++) Xor ^= a[i];
    // a+b = a^b + 2*(a&b)
    And = Add-Xor;
    // Xor是期望的值，而不是式子里确定的值，导致以下不合法的情况，包括下面需要判断的不合法也是因为这个
    if(Xor > Add || And % 2) {
        cout << "-1\n";
        return;
    }
    And /= 2;
    /*
        a^b a&b     a   b
         0   0  ->  0   0
         1   1  ->  x   x   (不合法)
         0   1  ->  1   1
         1   0  ->  不 同
    */
    LL ans = And;
    for(int i = 60; i >= 0; i --) {
        int xx = Xor>>i&1, yy = And>>i&1;
        if(xx && yy) {
            cout << "-1\n";
            return;
        }
        if(xx && !yy && (ans|1LL<<i) <= a[0]) {
            ans |= 1LL<<i;
        }
    }
    if(!ans || ans > a[0]) {
        cout << "-1\n";
        return;
    }
    cout << a[0]-ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;  // << setprecision(20); // double
    // freopen("i.txt", "r", stdin);
    // freopen("o.txt", "w", stdout);
    // int Tcase;
    // cin >> Tcase; // scanf("%d", &Tcase);
    // while (Tcase--) 
    solve();
    return 0;
}