头像

Protein

OIer




离线:6小时前


活动打卡代码 AcWing 3246. 引水入城

Protein
3天前
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 5050;
int n, m, A, B, Q, X;
int r[N][N], c[N][N], d[N];
signed main() {
    cin >> n >> m >> A >> B >> Q >> X;
    for (int i = 1; i <= n - 1; i ++ )
        for (int j = 1; j <= m; j ++ )
            c[i][j] = X = (A * X + B) % Q;
    for (int i = 2; i <= n; i ++ )
        for (int j = 1; j < m; j ++ )
            r[i][j] = X = (A * X + B) % Q;
    for (int j = 1; j <= m; j ++ ) {
        for (int i = 1; i <= n - 1; i ++ ) d[i] += c[i][j];
        for (int i = 2; i <= n - 1; i ++ )
            d[i] = min(d[i], d[i - 1] + r[i][j]);
        for (int i = n - 2; i; i -- )
            d[i] = min(d[i], d[i + 1] + r[i + 1][j]);
    }
    int res = 1e18;
    for (int i = 1; i <= n - 1; i ++ ) res = min(res, d[i]);
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 2816. 判断子序列

Protein
10天前
#include <iostream>
using namespace std;
const int N = 100010;
int n, m, a[N], b[N];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < m; i++) scanf("%d", &b[i]);
    int i = 0, j = 0;
    for (; i < n; i++) {
        while (j < m && a[i] != b[j]) j++;
        if (j == m) break;
        if (a[i] == b[j]) j++;
    }
    if (i == n) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


活动打卡代码 AcWing 210. 异或运算

Protein
19天前
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N = 10010;
int T, n, m, a[N];
signed main() {
    scanf("%lld", &T);
    for (int C = 1; C <= T; C++) {
        printf("Case #%lld:\n", C);
        scanf("%lld", &n);
        for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
        int k = 0;
        for (int i = 62; i >= 0; i--) {
            bool flag = true;
            for (int j = k; j < n && flag; j++)
                if (a[j] >> i & 1) swap(a[j], a[k]), flag = false;
            if (!(a[k] >> i & 1)) continue;
            for (int j = 0; j < n; j++)
                if (j != k && (a[j] >> i & 1))
                    a[j] ^= a[k];
            if (++k == n) break;
        }
        reverse(a, a + k);
        scanf("%lld", &m);
        for (int x; m-- && scanf("%lld", &x); ) {
            int res = 0;
            if (k < n) x--;
            if (x >= (1ll << k)) res = -1;
            else for (int i = 0; i < k; i++)
                if (x >> i & 1) res ^= a[i];
            printf("%lld\n", res);
        }
    }
    return 0;
}


活动打卡代码 AcWing 3164. 线性基

Protein
19天前
#include <iostream>
#define int long long
using namespace std;
typedef long long LL;
const int N = 100010;
int n, a[N];
signed main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
    int k = 0;
    for (int i = 62; i >= 0; i--) {
        for (int j = k; j < n; j++)
            if (a[j] >> i & 1) {
                swap(a[j], a[k]);
                break;
            }
        if (!(a[k] >> i & 1)) continue;
        for (int j = 0; j < n; j++)
            if (j != k && (a[j] >> i & 1))
                a[j] ^= a[k];
        k++;
        if (k == n) break;
    }
    int res = 0;
    for (int i = 0; i < k; i++) res ^= a[i];
    printf("%lld\n", res);
    return 0;
}


活动打卡代码 AcWing 3020. 建筑师

Protein
19天前
#include <iostream>
#define int long long
using namespace std;
const int N = 50010, M = 210, mod = 1e9 + 7;
int f[N][M], c[M][M];
signed main() {
    f[0][0] = 1;
    for (int i = 1; i < N; i++)
        for (int j = 1; j < M; j++)
            f[i][j] = (f[i - 1][j - 1] + (i - 1) * (f[i - 1][j])) % mod;
    for (int i = 0; i < M; i++)
        for (int j = 0; j <= i; j++)
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    int T, n, A, B;
    cin >> T;
    while (T-- && cin >> n >> A >> B) 
        cout << f[n - 1][A + B - 2] * c[A + B - 2][A - 1] % mod << endl;
    return 0;
}



Protein
19天前
#include <iostream>
#define int long long
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, m, f[N][N];
signed main() {
    cin >> n >> m;
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            f[i][j] = (f[i - 1][j - 1] + j * f[i - 1][j]) % mod;
    cout << f[n][m] << endl;
    return 0;
}



Protein
19天前
#include <iostream>
#define int long long
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, m, f[N][N];
signed main() {
    cin >> n >> m;
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            f[i][j] = (f[i - 1][j - 1] + (i - 1) * f[i - 1][j]) % mod;
    cout << f[n][m] << endl;
    return 0;
}


活动打卡代码 AcWing 3134. 魔法手链

Protein
20天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 11, P = 9973;
int m;
struct MATRIX {
    int a[N][N];
    MATRIX() { memset(a, 0, sizeof a); }
}; 
MATRIX operator*(MATRIX a, MATRIX b) {
    MATRIX c;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 1; k <= m; k++)
                c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j]) % P;
    return c;
}
int qmi(MATRIX a, int b) {
    MATRIX res;
    for (int i = 1; i <= m; i++) res.a[i][i] = 1;
    while (b) {
        if (b & 1) res = res * a;
        a = a * a, b >>= 1;
    }
    int sum = 0;
    for (int i = 1; i <= m; i++) sum += res.a[i][i];
    return sum;
}
int phi(int n) {
    int res = n;
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            res = res / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) res = res / n * (n - 1);
    return res % P;
}
int inv(int n) {
    n %= P;
    for (int i = 1; i < P; i++)
        if (i * n % P == 1) return i;
    return -1;
}
int main() {
    int T, n, k;
    cin >> T;
    while (T-- && cin >> n >> m >> k) {
        MATRIX tr;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= m; j++)
                tr.a[i][j] = 1;
        for (int x, y; k-- && cin >> x >> y; ) 
            tr.a[x][y] = tr.a[y][x] = 0;
        int res = 0;
        for (int i = 1; i <= n / i; i++) 
            if (n % i == 0) {
                res = (res + qmi(tr, i) * phi(n / i)) % P;
                if (i != n / i) 
                    res = (res + qmi(tr, n / i) * phi(i)) % P;
            }
        cout << res * inv(n) % P << endl;
    }
    return 0;
}


活动打卡代码 AcWing 3133. 串珠子

Protein
20天前
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int GCD(int a, int b) { return b ? GCD(b, a % b) : a; };
int main() {
    int m, n;
    while (cin >> m >> n, n || m) {
        int res = 0;
        for (int i = 0; i < n; i++)
            res += pow(m, GCD(n, i));
        if (n & 1) res += n * pow(m, (n + 1) / 2);
        else res += n / 2 * (pow(m, n / 2 + 1) + pow(m, n / 2));
        cout << res / n / 2 << endl;
    }
    return 0;
}


活动打卡代码 AcWing 3132. 食物

Protein
20天前
#include <iostream>
using namespace std;
const int N = 510, mod = 10007;
char s[N];
int main() {
    cin >> s;
    long long n = 0;
    for (int i = 0; s[i]; i++)
        n = (n * 10 + s[i] - '0') % mod;
    cout << n * (n + 1) * (n + 2) / 6 % mod << endl;
    return 0;
}