头像

只要是你呀


访客:7726

离线:6小时前


活动打卡代码 AcWing 894. 拆分-Nim游戏

#include <iostream>
#include <cstring>
#include <unordered_set>

using namespace std;

const int N = 110;

int f[N];

int sg(int x)
{
    if(f[x] != -1) return f[x];

    unordered_set<int> S;
    for(int i = 0; i < x; i ++)
        for(int j = 0; j <= i; j ++)
            S.insert(sg(i) ^ sg(j));

    for(int i = 0;; i ++)
        if(!S.count(i))
            return f[x] = i;
}

int main()
{
    int n;
    cin >> n;

    memset(f, -1, sizeof f);

    int res = 0;
    while(n -- )
    {
        int x;
        cin >> x;
        res ^= sg(x);
    }

    if(res) puts("Yes");
    else puts("No");

    return 0;
}


活动打卡代码 AcWing 892. 台阶-Nim游戏

#include <iostream>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);

    int res = 0;

    for(int i = 1; i <= n; i ++)
    {
        int x;
        scanf("%d", &x);
        if(i % 2 != 0)
            res ^= x;
    }

    if(res) puts("Yes");
    else puts("No");

    return 0;
}



#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int a[N][N];

int gauss()
{
    int r, c;
    for(c = 0, r = 0; c < n; c ++)
    {
        int t = r;
        for(int i = r; i < n; i ++)
            if(a[i][c])
            {
                t = i;
                break;
            }

        if(!a[t][c]) continue;

        for(int i = c; i <= n; i ++) swap(a[t][i], a[r][i]);

        for(int i = r + 1; i < n; i ++)
            if(a[i][c])
                for(int j = n; j >= c; j --)
                    a[i][j] ^= a[r][j];

        r ++;
    }

    if(r < n)
    {
        for(int i = r; i < n; i ++)
            if(a[i][n])
                return 2;
        return 1;
    }

    for(int i = n - 1; i >= 0; i --)
        for(int j = i + 1; j < n; j ++)
            a[i][n] ^= a[i][j] & a[j][n];

    return 0;
}

int main()
{
    cin >> n;

    for(int i = 0; i < n; i ++)
        for(int j = 0; j <= n; j ++)
            cin >> a[i][j];

    int res = gauss();

    if(res == 0)
    {
        for(int i = 0; i < n; i ++)
            cout << a[i][n] << endl;
    }
    else if(res == 1) puts("Multiple sets of solutions");
    else puts("No solution");

    return 0;
}



#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }

    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main()
{
    int n;
    cin >> n;

    bool has_answer = true;
    LL a1, m1;

    cin >> a1 >> m1;

    for(int i = 0; i < n - 1; i ++)
    {
        LL a2, m2;
        cin >> a2 >> m2;

        LL k1, k2;
        LL d = exgcd(a1, a2, k1, k2);
        if((m2 - m1) % d)
        {
            has_answer = false;
            break;
        }

        k1 *= (m2 - m1) / d;
        LL t = a2 / d;
        k1 = (k1 % t + t) % t;

        m1 = a1 * k1 + m1;
        a1 = abs(a1 / d * a2);
    }

    if(has_answer)
        cout << (m1 % a1 + a1) % a1 << endl;
    else puts("-1");

    return 0;

}


活动打卡代码 AcWing 893. 集合-Nim游戏

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;

const int N = 110, M = 100010;

int n, m;
int s[N], f[M];

int sg(int x)
{
    if(f[x] != -1) return f[x];

    unordered_set<int> S;
    for(int i = 0; i < m; i ++)
    {
        int sum = s[i];
        if(x >= sum) S.insert(sg(x - sum));
    }

    for(int i = 0; ; i ++)
        if(!S.count(i))
            return f[x] = i;
}

int main()
{
    cin >> m;
    for(int i = 0; i < m; i ++) cin >> s[i];
    cin >> n;

    memset(f, -1, sizeof f);

    int res = 0;
    for(int i = 0; i < n; i ++)
    {
        int x;
        cin >> x;
        res ^= sg(x);
    }

    if(res) puts("Yes");
    else puts("No");

    return 0;
}


活动打卡代码 AcWing 891. Nim游戏

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    int res = 0;
    while(n -- )
    {
        int t;
        cin >> t;
        res ^= t;
    }

    if(res != 0) puts("Yes");
    else puts("No");

    return 0;
}


活动打卡代码 AcWing 890. 能被整除的数

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 20;

int p[N];

int main()
{
    int n, m;
    cin >> n >> m;

    for(int i = 0; i < m; i ++) cin >> p[i];

    int res = 0;
    for(int i = 1; i < 1 << m; i ++)
    {
        int t = 1, s = 0;
        for(int j = 0; j < m; j ++)
        {
            if(i >> j & 1)
            {
                if((LL)t * p[j] > n)
                {
                    t = -1;
                    break;
                }
                t *= p[j];
                s ++;
            }
        }
        if(t != -1)
        {
            if(s % 2) res += n / t;
            else res -= n / t;
        }
    }

    cout << res << endl;

    return 0;
}



#include <iostream>

using namespace std;

typedef long long LL;

const int mod = 1e9 + 7;

int qmi(int a, int k, int q)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        k >>= 1;
    }
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);

    int a = n * 2, b = n;

    int res = 1;
    for(int i = a; i > a - b; i --) res = (LL)res * i % mod;
    for(int i = 1; i <= b; i ++) res = (LL)res * qmi(i, mod - 2, mod) % mod;

    res = (LL)res * qmi(n + 1, mod - 2, mod) % mod;

    printf("%d\n", res);

    return 0;
}


活动打卡代码 AcWing 888. 求组合数 IV

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 5010;

int primes[N], cnt;
int sum[N];
bool st[N];

void get_primes(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i]) primes[cnt ++ ] = i;
        for(int j = 0; primes[j] <= n / i; j ++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0)
                break;
        }
    }
}

int get(int n, int p)
{
    int res = 0;
    while(n)
    {
        res += n / p;
        n /= p;
    }
    return res;
}

vector<int> mul(vector<int> a, int b)
{
    vector<int> c;
    int t = 0;
    for(int i = 0; i < a.size(); i ++)
    {
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while(t)
    {
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}

int main()
{
    int a, b;
    scanf("%d%d", &a, &b);

    get_primes(N);

    for(int i = 0; i < cnt; i ++)
    {
        int p = primes[i];
        sum[i] = get(a, p) - get(b, p) - get(a - b, p);
    }

    vector<int> res;
    res.push_back(1);

    for(int i = 0; i < cnt; i ++)
        for(int j = 0; j < sum[i]; j ++)
            res = mul(res, primes[i]);

    for(int i = res.size() - 1; i >= 0; i --)
        printf("%d", res[i]);

    return 0;
}


活动打卡代码 AcWing 887. 求组合数 III

#include <iostream>

using namespace std;

typedef long long LL;

int qmi(int a, int k, int p)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int C(int a, int b, int p)
{
    if(a < b)
        return 0;

    int res = 1;
    for(int i = 1, j = a; i <= b; i ++, j --)
    {
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2, p) % p;
    }
    return res;
}

int Lucas(LL a, LL b, int p)
{
    if(a < p && b < p)
        return C(a, b, p);
    return (LL)C(a % p, b % p , p) * Lucas(a / p, b / p, p) % p;
}

int main()
{
    int n;
    scanf("%d", &n);

    while(n -- )
    {
        LL a, b;
        int p;
        scanf("%lld%lld%d", &a, &b, &p);

        printf("%d\n", Lucas(a, b, p));
    }

    return 0;
}