头像

帝一


访客:21663

离线:1小时前


活动打卡代码 AcWing 214. Devu和鲜花

帝一
9小时前
#include <iostream>
#include <cstring>

using namespace std;
typedef long long LL;
const int N = 20, mod = 1e9 + 7;

LL A[N];

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

int C(LL a, LL b)
{
    if(a < b)return 0;
    int up = 1, down = 1;
    for(LL i = a; i > a - b; i --)up = i % mod * up % mod;
    for(int i = 1; i <= b; i ++)down = (LL)down * i % mod;

    return (LL)up * qmi(down, mod - 2) % mod;
}

int main()
{
    LL n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i ++)cin >> A[i];
    int res = 0;
    for(int i = 0; i < 1 << n; i ++)
    {
        int sign = 1;
        LL a = n + m - 1, b = n - 1;
        for(int j = 0; j < n; j ++)
            if(i >> j & 1)
            {
                sign = sign * -1;
                a -= A[j] + 1;
            }
        res = (res + C(a, b) * sign) % mod;
    }
    cout << (res + mod) % mod << endl;
    return 0;
}


活动打卡代码 AcWing 1312. 序列统计

帝一
2天前
#include <iostream>

using namespace std;
const int mod = 1e6 + 3;
typedef long long LL;

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

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

    int down = 1, up = 1;
    for (int i = a, j = 1; j <= b; i --, j ++ )
    {
        up = (LL)up * i % mod;
        down = (LL)down * j % mod;
    }

    return (LL)up * qmi(down, mod - 2) % mod;
}

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

int main()
{
    int T;
    cin >> T;
    while(T --){
    int n, l, r;
    cin >> n >> l >> r;

    cout << (Lucas(r - l + n + 1, r - l + 1) - 1 + mod ) % mod << endl;
    }
    return 0;
}



帝一
2天前
#include <iostream>

using namespace std;
const int mod = 1e6 + 3;
typedef long long LL;

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

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

    int down = 1, up = 1;
    for (int i = a, j = 1; j <= b; i --, j ++ )
    {
        up = (LL)up * i % mod;
        up = (LL)up * qmi(j, mod - 2) % mod;//放在里面会超时
    }

    return up;
}
/*
int C(int a, int b)
{
    if (a < b) return 0;

    int down = 1, up = 1;
    for (int i = a, j = 1; j <= b; i --, j ++ )
    {
        up = (LL)up * i % p;
        down = (LL)down * j % p;
    }

    return (LL)up * qmi(down, p - 2) % p;
}
*/
int Lucas(int a, int b)
{
    if(a < mod && b < mod)return C(a, b);
    return (LL)C(a % mod, b % mod) * Lucas(a / mod, b / mod) % mod;
}

int main()
{
    int T;
    cin >> T;
    while(T --){
    int n, l, r;
    cin >> n >> l >> r;

    cout << (Lucas(r - l + n + 1, r - l + 1) - 1 + mod ) % mod << endl;
    }
    return 0;
}


活动打卡代码 AcWing 1310. 数三角形

帝一
2天前
#include <iostream>

using namespace std;
typedef long long LL;
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

LL C(int a, int b)
{
    return (LL)a * (a - 1) * (a - 2) / 6;
}

int main()
{
    int n, m;
    cin >> n >> m;
    n ++, m ++;
    LL res = C(m * n, 3) - n * C(m, 3) - m * C(n, 3);
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
         res -= 2ll * (gcd(i, j) - 1) * (n - i) * (m - j);
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 1309. 车的放置

帝一
2天前
#include <iostream>

using namespace std;
typedef long long LL;
const int mode = 100003;

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

int fact(int x)
{
    int res = 1;
    for(int i = 1; i <= x; i ++)
    res = (LL)res * i % mode;
    return res;
}

int infact(int x)
{
    int res = 1;
    for(int i = 1; i <= x; i ++)
    res = (LL)res * qmi(i, mode - 2) % mode;
    return res;
}

int C(int a, int b)
{
    if(a < b)return 0;
    return (LL)fact(a) * infact(a - b) % mode * infact(b) % mode;
}

int A(int a, int b)
{
    if(a < b)return 0;
    return (LL)fact(a) * infact(a - b) % mode;
}

int main()
{
    int a, b, c, d, k;
    cin >> a >> b >> c >> d >> k;

    int res = 0;

    for(int i = 0; i <= k; i ++)
    {
        res = (res + (LL)C(b, i) * A(a, i) % mode * (LL)C(d, k - i)% mode * A(a + c - i, k - i) % mode) % mode;

    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 1308. 方程的解

帝一
3天前
#include <iostream>

using namespace std;

const int N = 150;
int f[1000][100][N];

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

void add(int c[], int a[], int b[])
{
    int t = 0;
    for(int i = 0; i < N; i ++)
    {
        t += a[i] + b[i];
        c[i] = t % 10;
        t /= 10;
    }
}

int main()
{
    int k, x;
    cin >> k >> x;
    int n = qmi(x % 1000, x, 1000);

    for(int i = 0; i < n; i ++)
        for(int j = 0; j <= i && j < k; j ++)
            if(!j)f[i][j][0] = 1;
            else add(f[i][j], f[i - 1][j], f[i - 1][j - 1]);
    int *g = f[n - 1][k - 1];
    k = N - 1;
    while(!g[k])k --;
    for(; k >= 0; k --)cout << g[k];
    return 0;
}


活动打卡代码 AcWing 1307. 牡牛和牝牛

帝一
3天前
#include <iostream>

using namespace std;
const int N = 1e5 + 10, mod = 5000011;
int f[N], s[N];

int main()
{
    int n, m;
    cin >> n >> m;
    f[0] = s[0] = 1;
    for(int i = 1; i <= n; i ++)
    {
        f[i] = s[max(i - m - 1, 0)];
        s[i] = (s[i - 1] + f[i]) % mod;
    }
    cout << s[n] << endl;
    return 0;
}



帝一
4天前

菜逼一枚,看了一下午推导,最后果然死在了最后一步,不等为啥,会的大佬帮忙call我,谢谢!

证明

记一下,假如已经推导了出来,可能会存在b % p > a % p 那么它的系数直接为零,具体看代码。可以不加,但是加上速度会快一点。




帝一
4天前
#include <iostream>
#include <cstring>

using namespace std;
const int N = 5;
typedef long long LL;
int n, m;

void mul(int f[], int a[][N])
{
    int temp[N] = {0};
    for(int i = 0; i < N; i ++)
        for(int j = 0; j < N; j ++)
            temp[i] = (temp[i] + (LL)f[j] * a[j][i]) % m;
    memcpy(f, temp, sizeof temp);
}

void mul(int a[][N])
{
    int temp[N][N] = {0};
    for(int i = 0; i < N; i ++)
        for(int j = 0; j < N; j ++)
            for(int k = 0; k < N; k ++)
                temp[i][j] = (temp[i][j] + (LL)a[i][k] * a[k][j]) % m;
    memcpy(a, temp, sizeof temp);
}

int main()
{
    cin >> n >> m;
    int f[N] = {0, 1, 0, 1, 0};
    int a[N][N] = {
        {0, 1, 0, 2, 0},
        {1, 1, 0, 1, 0},
        {0, 0, 0, 1, 0},
        {0, 0, 1, 1, 1},
        {0, 0, 0, 0, 1},
    };

    while(n)
    {
        if(n & 1)mul(f, a);
        mul(a);
        n >>= 1;
    }

    cout << f[4] << endl;
    return 0;
}



帝一
4天前

记录一下踩的坑

#include <iostream>
#include <cstring>

using namespace std;
typedef long long LL;
const int N = 3;
int n, m;

void mul(int f[], int a[][N])
{
    int temp[N] = {0};
    for(int i = 0; i < 3; i ++)
        for(int j = 0; j < 3; j ++)
            temp[i] = (temp[i] + (LL)f[j] * a[j][i]) % m;
    memcpy(f, temp, sizeof temp); // 一定要是sizeof(temp)不能是f因为f传进来的是个指针大小就是指针的大小。
}

void mul(int a[][N], int b[][N])
{
    int temp[N][N] = {0};
    for(int i = 0; i < 3; i ++)
        for(int j = 0; j < 3; j ++)
            for(int k = 0; k < 3; k ++)
                temp[i][j] = (temp[i][j] + (LL)a[i][k] * b[k][j]) % m;
    memcpy(a, temp, sizeof temp);//一定要是sizeof(temp),不能上f因为f传进来的是指针大小就是指针的大小。
}

int main()
{
    cin >> n >> m;
    int f[N] = {0, 1, 0};
    int a[N][N] = {
        {0, 1, 0},
        {1, 1, 1},
        {0, 0, 1},
    };
    while(n)
    {
        if(n & 1)mul(f, a);
        mul(a, a);
        n >>= 1;
    }
    cout << f[2] << endl;
    return 0;
}