头像

只想白嫖

xs




离线:1小时前


最近来访(130)
用户头像
rd0
用户头像
wKingYu
用户头像
阿飘
用户头像
Lansong
用户头像
Shanjw
用户头像
ohh_0
用户头像
绯取世间一笑
用户头像
OI
用户头像
美琴
用户头像
815741912
用户头像
codewin
用户头像
听雨.无尘明月夜
用户头像
BT7274
用户头像
wwdxwjl
用户头像
光風霽月
用户头像
77777777777
用户头像
TongX_5c
用户头像
月明星稀
用户头像
Joey就是小许
用户头像
.Alex.

活动打卡代码 AcWing 221. 龙哥的问题

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

int n;

int main()
{
    cin >> n;

    LL ans = n;
    for(int i = 2; i <= n / i; i ++)
    {
        if(n % i == 0)
        {
            int p = i, cnt = 0;
            while(n % p == 0) cnt ++, n /= p;

            ans = ans * (p +  1ll * cnt * p - cnt) / p;
        }
    }

    if(n != 1) ans = ans * (n + 1ll * n - 1) / n;
    cout << ans << endl;

    return 0;

}


活动打卡代码 AcWing 3125. 扩展BSGS

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath> 
using namespace std;

int a, p, b;

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

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

int bsgs(int a, int p, int b)
{
    if(1 % p == b % p) return 0;

    int k = sqrt(p) + 1;
    unordered_map<int, int> hash;
    for(int i = 0, w = b % p; i < k; i ++, w = 1ll * w * a % p)
        hash[w] = i;

    int ak = 1;
    for(int i = 1; i <= k; i ++) ak = 1ll * ak * a % p;

    for(int i = 1, w = ak % p; i <= k; i ++, w = 1ll * w * ak % p)
        if(hash.count(w)) return k * i - hash[w];
    return -1e9;
}

int exbsgs(int a, int p, int b)
{
    //逆元x可能为负,这里的b也可能是负数
    b = (b % p + p) % p;
    if(1 % p == b % p) return 0;

    int x, y;
    int d = exgcd(a, p, x, y);
    if(d == 1) return bsgs(a, p, b);

    if(b % d) return -1e9;
    //x是(a/d) 关于 (p/d)的逆元,可能为负数
    exgcd(a / d, p / d, x, y);
    return 1 + exbsgs(a, p / d, 1ll * b / d * x % (p / d));
}

int main()
{
    while(cin >> a >> p >> b , a || p || b)
    {
        int res = exbsgs(a, p, b);
        if(res < 0) puts("No Solution");
        else cout << res << endl;
    }

    return 0;
}


活动打卡代码 AcWing 2526. 随机数生成器

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
int p, a, b, x1, t;

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

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

int qmi(int x, int k)
{
    int res = 1 % p;
    while(k)
    {
        if(k & 1) res = 1ll * res * x % p;
        x = 1ll * x * x % p;
        k >>= 1;
    }

    return res % p;
}

int BSGS(int a, int b, int p)
{
    if(1 == b % p) return 0;

    int k = sqrt(p) + 1;
    //y:[0 ~ k-1];x:[1 ~ k]; t = xk - y
    unordered_map<int, int> hash;
    for(int i = 0, res = b % p; i < k; i ++, res = 1ll * res * a % p)
        hash[res] = i;

    int ak = 1;
    for(int i = 1; i <= k; i ++)
        ak = 1ll * ak * a % p;

    for(int i = 1, res = ak; i <= k; i ++, res = 1ll * res * ak % p)
        if(hash.count(res)) return i * k - hash[res];
    return -2;
}

int main()
{
    int tt;
    cin >> tt;
    while(tt --)
    {
        cin >> p >> a >> b >> x1 >> t;
        if(a == 0)
        {
            if (x1 == t) puts("1");
            else if (b == t) puts("2");
            else puts("-1");
        }
        else if(a == 1)
        {
            if (b == 0) puts(t == x1 ? "1" : "-1");
            else
            {
                int x, y;
                exgcd(b, p, x, y);
                x = ((LL)x * (t - x1) % p + p) % p;
                cout << x + 1 << endl;
            }
        }
        else
        {
            int C = (LL)b * qmi(a - 1, p - 2) % p;
            int A = (x1 + C) % p;
            if(A == 0)
            {
                int u = (-C + p) % p;
                puts(u == t ? "1" : "-1");
            }
            else
            {
                int B = (t + C) % p;
                cout << BSGS(a, (LL)B * qmi(A, p - 2) % p, p) + 1 << endl;
            }
        }

    }

    return 0;
}



多组输入时如何初始化字典树

void add(int x)
{
    int cnt = 0;
    for(int i = 17; i >= 0; i --)
    {
        int t = ((x >> i) & 1);
        if(!son[cnt][t])
        {
            //在插入时更新字典树。
            son[idx + 1][0] = son[idx + 1][1] = 0; 
            son[cnt][t] = ++ idx;
        }
        cnt = son[cnt][t];
    }
    val[cnt] = x;
}


活动打卡代码 AcWing 3123. 高精度乘法II

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 5e5 + 10;
const double PI = acos(-1);

struct Complex 
{
    double x, y;
    Complex operator + (const Complex &t) const 
    {
        return {x + t.x, y + t.y};
    }
    Complex operator - (const Complex &t) const
    {
        return {x - t.x, y - t.y};
    }
    Complex operator * (const Complex &t) const
    {
        return {x * t.x - y * t.y, x * t.y + y * t.x};
    }
}a[N], b[N];
int tot, bit, tra[N];

void FFT(Complex a[], int type)
{
    for(int i = 0; i < tot; i ++) 
        if(i < tra[i]) swap(a[i], a[tra[i]]);

    for(int mid = 1; mid < tot; mid *= 2)
    {
        Complex w1 = {cos(PI / mid), type * sin(PI / mid)};
        for(int pos = 0, len = mid * 2; pos < tot; pos += len)
        {
            Complex wk = {1, 0};
            for(int k = 0; k < mid; k ++, wk = wk * w1)
            {
                auto x = a[k + pos], y = wk * a[k + pos + mid];
                a[k + pos] = x + y, a[k + pos + mid] = x - y;
            }
        }
    }

    if(type == 1) return;
    for(int i = 0; i < tot; i ++ ) a[i].x /= tot;
}


int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    int n = s1.size(), m = s2.size();
    n --, m --;

    while((1 << bit) <= n + m) bit ++;
    tot = 1 << bit;

    for(int i = 0; i < tot; i ++) 
        tra[i] = (tra[i >> 1] >> 1) | ((i & 1) << (bit - 1));

    reverse(s1.begin(), s1.end());
    reverse(s2.begin(), s2.end());

    for(int i = 0; i <= n; i ++) a[i].x = s1[i] - '0';
    for(int i = 0; i <= m; i ++) b[i].x = s2[i] - '0';



    FFT(a, 1), FFT(b, 1);
    for(int i = 0; i < tot; i ++) a[i] = a[i] * b[i];
    FFT(a, -1);

    vector<int> ans(n + m + 1);
    for(int i = 0; i <= n + m; i ++) ans[i] = (int)(a[i].x + 0.5);

    vector<int> t;
    for(int i = 0, tt = 0; (i <= n + m) || tt; i ++)
    {
        if(i <= n + m)
            tt += ans[i];
        t.push_back(tt % 10);
        tt /= 10;
    }

    int idx = n + m + 1;
    while(t[idx] == 0 && idx >= 1) idx --;
    for(int i = idx; i >= 0; i --) cout << t[i];

    return 0;
}



活动打卡代码 AcWing 3122. 多项式乘法

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 5e5 + 10;
const double PI = acos(-1);

struct Complex
{
    double x, y;
    Complex operator + (const Complex &t) const 
    {
        return {x + t.x, y + t.y};
    }
    Complex operator - (const Complex &t) const 
    {
        return {x - t.x, y - t.y};
    }
    Complex operator * (const Complex &t) const 
    {
        return {x * t.x- y * t.y, y * t.x + x * t.y};
    }
}a[N], b[N];

int tot, bit, tra[N];
int n, m;

void FFT(Complex a[], int type)
{
    for(int i = 0; i < tot; i ++) 
        if(i < tra[i]) swap(a[i], a[tra[i]]);

    for(int mid = 1; mid < tot; mid <<= 1)
    {
        auto w1 = Complex ({cos(PI / mid), type * sin(PI / mid)});
        for(int len = mid * 2, pos = 0; pos < tot; pos += len)
        {
            auto wk = Complex ({1, 0});
            for(int k = 0; k < mid; k ++, wk = wk * w1)
            {
                auto x = a[pos + k], y = a[pos + k + mid];
                a[pos + k] = x + wk * y;
                a[pos + k + mid] = x - wk * y;
            }
        }
    }

    if(type == 1) return;
    for(int i = 0; i < tot; i ++ ) a[i].x /= tot;
}

int main()
{
    scanf("%d%d", &n, &m);
    // cout << n << m << endl;
    for(int i = 0; i <= n; i ++) scanf("%lf", &a[i].x);
    for(int i = 0; i <= m; i ++) scanf("%lf", &b[i].x);

    while((1 << bit) <= n + m) bit ++;
    tot = 1 << bit;

    //1101 0110 0110 1011(处理蝴蝶变化数组)
    for(int i = 0; i < tot; i ++) tra[i] = (tra[i >> 1] >> 1) | ((i & 1) << (bit - 1));

    FFT(a, 1), FFT(b, 1);//将系数表示转换为点表示
    for(int i = 0; i < tot; i ++) a[i] = a[i] * b[i];//a * b
    FFT(a, -1);//将点表达在转换为系数表示

    for(int i = 0; i <= n + m; i ++)    
        printf("%d ", (int)(a[i].x + 0.5));


    return 0;
}


活动打卡代码 AcWing 3132. 食物

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

using namespace std;
typedef long long LL;
const int P = 10007;

int main()
{
    string s;
    cin >> s;
    int n = 0;
    //秦九韶算法,将一个n次多项式,一直提取x将其变为:n次乘法和n次加法。
    for(auto x : s)
        n = (n * 10 + (x - '0')) % P;
    cout << 1ll * n * (n + 1) * (n + 2)  / 6 % P << endl; 

    return 0;
}


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

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5e4 + 10, M = 210, P = 1e9 + 7;
LL s[N][M];
LL c[M][M];

void init()
{
    s[0][0] = 1;
    for(int i = 1; i < N; i ++)
        for(int j = 1; j < M; j ++) s[i][j] = (s[i - 1][j - 1] + 1ll * (i - 1) * s[i - 1][j]) % P;

    c[0][0] = 1;
    for(int i = 1; i < M; i ++)
        for(int j = 0; j < M; j ++) 
            if(!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % P;
}

int main()
{
    init();
    int tt;
    cin >> tt;
    while(tt --)
    {
        int n, a, b;
        cin >> n >> a >> b;
        // cout << s[n - 1][a + b - 2] << ' ' << c[a + b - 2][a - 1] << endl;
        cout << 1ll * s[n - 1][a + b - 2] * c[a + b - 2][a - 1] % P << '\n';
    }
}



#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 1010, P = 1e9 + 7;
int S[N][N];
int n, m;

void init()
{
    S[0][0] = 1;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            S[i][j] = (S[i - 1][j - 1] + 1ll * j * S[i - 1][j]) % P;
}

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

    cout << S[n][m] << endl;
    return 0;
}



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

using namespace std;
const int N = 1010, mod = 1e9 + 7;
int s[N][N];

void init()
{
    s[0][0] = 1;
    for(int i = 1; i < N; i ++)
        for(int j = 1; j < N; j ++) 
            s[i][j] = (s[i - 1][j - 1] + 1ll * (i - 1) * s[i - 1][j]) % mod;
}

int main()
{
    init();
    int n, k;
    cin >> n >> k;
    cout << s[n][k] << endl;


    return 0;
}