joxj 模拟赛 2019年9月3日

比赛题目来源：2018qbxt合肥Day1

T1 最小公倍数

题意：已知正整数n，求n与246913578的最小公倍数，结果对1234567890取模

数据范围：1<=n<=10¹⁰⁰⁰⁰⁰

由lcm = a * b / gcd(a,b) (mod 1234567890)

发现除数巨大，需要取模，考虑乘法逆元，但b,1234567890不一定互质，因此不能用乘法逆元

但由于gcd的性质，gcd(a,b) = gcd(a%b , b) , 又发现模数是b的倍数，

所以直接在用高精度a时边读边取模即可：gcd(a,b) = gcd(a%1234567890,b)

(然而考试的时候没想那么多，直接猜想到用结论求解，太不严谨了)

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define ll long long

ll mol;

ll gcd(ll a, ll b)

{

    return (b == 0)? a : gcd(b,a%b);

}

ll lcm(ll a, ll b)

{

    return ((a * b)  / gcd(a,b)) % mol;

}

char ch[100100];

int main()

{

    mol = 1234567890;

    ll n = 0, m = 246913578; scanf("%s",ch + 1);

    ll len = strlen(ch + 1); ll rest = 0;

    ll alen = len; ll x = 1e9;

    while(len > 8)

    {

        ll now = 0;

        for(int i = alen - len + 1; i <= alen - len + 8; i++)

        {

            now = now * 10 + ch[i] - '0';

        }

        rest = (now + ((rest * x)% mol)) % mol;

        len -= 8;

    }

    for(int i = alen - len + 1; i <= alen; i++)

    {

        n = n * 10 + (ch[i] - '0');

    }

    n = n % mol;

    n = ((rest * x) % mol + n) % mol;

    printf("%lld\n", lcm(n, m));

    return 0;

}

T2 不可逆转

洛谷上也有这道题：题目链接

题意：求有多少1~n的排列满足该排列是波动的，答案对m取模。

数据范围：1<=n<=1000 m<=10⁹

看到这道题第一眼感觉和用LCIS求解的波浪序列有点像，但很快发现区别很大，这道题只有一个序列，而波浪序列那道题是两个序列。我一开始的思路是打表，看看这道题有没有公式，然而找了半天还是没找到规律，于是我就换了一下思路，发现这道题可能是道dp，但我想了半天还是没想到这道题的用来dp的特殊性质，于是打了个暴搜了事。

果然，所有的难写dp方程都与题目的性质有关，这道题的性质如下:

1.对于一个普通的序列，可以通过离散化使序列变成1到n的排列。

2.序列的“波动“程度是描数序列性质时常用的参数之一。

当考虑1到n的排列时，可以考虑最大的数的位置来表示序列的”波动“程度。

我们又发现，对于先降后升的序列和先升后降的序列，可以把其中的一个序列的每个数x换成n+1-x来将两种序列互换。

所以，我们只需要算其中一种序列的方案数，然后再*2即可。

计算f[i]时，枚举数i的位置j，j把序列分成了两个部分，计算该位置的方案数时，由于性质1，我们只需要先乘选左边数的组合数（左边选哪些数确定了，右边选哪些数也就确定了），然后再用C(i-1,j-1) * f[j-1] * f[i-j]即可。

对于空间，可以采用动态数组的方式进行优化。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

int n, m;

long long C[1010][1010]={},f[1010]={};

int main()

{

    scanf("%d%d", &n, &m);

    C[0][0] = 1;

    for(int i = 1; i <= n; i++)

    {

        C[i][0] = 1;

        for(int j = 1; j <= i; j++)

        {

            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % m;

        }

    }

    f[0] = 1; f[1] = 1;

    for(int i = 2; i <= n; i++)

    {

        for(int j = 1; j <= i; j++)

        {

            if(j&1) f[i] = (f[i] + (((f[j - 1] % m) * (f[i - j] % m)) % m) * C[i - 1][j - 1]) % m;

        }

    }

    printf("%d\n",f[n] * 2 % m);

    return 0;

}

数值微分

题意：\(f[0](x) = f(x)\) \(f[i](0) = 0\) \(f[i](x) = f[i-1](x) - f[i-1](x-1)\)

输入第一行为n,m 第二行为n个数f(i) , 输出为fm , 结果对100007取模

数据范围：1<=n<=1000 1<=m<=10⁹ 0<=f[i]<100007

这道题我在考试时找到了杨辉三角，但却没时间做了，而且也没想到用组合数算杨辉三角。

首先我们猜想存在数组a使得fm = a[0] * f[i-0] + a[1] * f[i-1] + ... + a[i-1] * f[i-(i-1)]

发现a=(-1)^j*C(m,j)，问题来了，当n>m时怎么办，我们发现当n>m时当前数只会被前m个数影响，所以在这之前的数直接用组合数的初始值0来相乘即可，并不会影响答案，所以，我们只需要将n和m去最小值即可。

这道题还有一个坑点是100007不是质数，故不能用卢卡斯定理，只能用扩展卢卡斯定理

我们将组合数的分子和分母分解质因数（这一步也有很多细节），然后直接计算即可。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

#define mol 100007

#define ll long long

int n, m;

ll C[1010];

int fac[1010]={};

ll f[1010];

ll rest = 1;

void dvd(int x,int k)

{

    for(int i = 2; i <= n; i++)//

    {

        while(x % i == 0)

        {

            fac[i] += k; x /= i;

        }

    }

    if(x != 1)rest = (rest * (x % mol)) % mol;//

}

ll quickpow(ll a, int b)

{

    ll ret = 1;

    while(b != 0)

    {

        if(b&1) ret = ret * a % mol;

        a = a * a % mol;

        b >>= 1;

    }

    return ret;

}

int main()

{

    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i++)scanf("%lld", &f[i]);

    C[0] = 1;

    for(int i = 1; i <= min(m, n); i++)

    {

        C[i] = 1;

        dvd(m - i + 1, 1); dvd(i, -1);

        C[i] = C[i] * rest % mol;

        for(ll j = 2; j <= n; j++)

        {

            if(fac[j] != 0)

            {

                C[i] = (C[i] * quickpow(j, fac[j])) % mol;

            }

        }

        //printf("C[%d] = %d\n", i, C[i]);

        //for(int i = 1; i <= min(m, n); i++)printf("fac[%d] = %d\n", i, fac[i]);

    }

    for(int i = 1; i <= n; i++)

    {

        ll ans = 0;

        for(int j = 0; j < i; j++)

        {

            if(j&1)

            ans = ((ans + (f[i - j] * C[j]) % mol * (-1)) % mol + mol) % mol;

            else

            ans = (ans + (f[i - j] * C[j]) % mol) % mol;

        }

        printf("%lld\n", ans);

    }

    return 0;

}

巴特西

joxj 模拟赛 2019年9月3日

T1 最小公倍数

T2 不可逆转

数值微分

最新文章

热门文章