22/8/3(板子)树状dp板子+中国剩余定理+求组合数3，4+容斥原理

 

目录

1.树状dp--没有上司的舞会

2. 中国剩余定理——表达整数的奇怪方式

3. 求组合数3

 4.求组合数4

 5.满足条件的01序列（实质仍然是组合数）

6.容斥原理--能被整除的数 

---

有点多，但是都很重要，慢慢看

1.树状dp--没有上司的舞会

Ural 大学有 NN 名职员，编号为 1∼N1∼N。

他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

每个职员有一个快乐指数，用整数 HiHi 给出，其中 1≤i≤N1≤i≤N。

现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

输入格式

第一行一个整数 NN。

接下来 NN 行，第 ii 行表示 ii 号职员的快乐指数 HiHi。

接下来 N−1N−1 行，每行输入一对整数 L,KL,K，表示 KK 是 LL 的直接上司。

输出格式

输出最大的快乐指数。

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
bool if_happy[N];
int he[N],ne[N],ed[N],idx;
int happy[N];
int f[N][3];
void add(int a,int b)
{
    ed[idx]=b;
    ne[idx]=he[a];
    he[a]=idx++;
}
void dfs(int u)
{
    f[u][1]=happy[u];
    f[u][0]=0;
    for(int i=he[u];i!=-1;i=ne[i])
    {
        int j=ed[i];
        dfs(j);
        f[u][0]+=max(f[j][1],f[j][0]);
        //cout<<f[j][1]<<" "<<f[j][0]<<endl;
        f[u][1]+=f[j][0];
    }
}
int main()
{
    int n,i,root,a,b;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    scanf("%d",&happy[i]);
    memset(he,-1,sizeof(he));
    for(i=1;i<=n-1;i++)
    {
        scanf("%d%d",&a,&b);
        add(b,a);
        if_happy[a]=true;
    }
    for(i=1;i<=n;i++)
    {
        if(if_happy[i]==false)
        {
            root=i;
            break;
        }
    }
    dfs(root);
    printf("%d\n",max(f[root][0],f[root][1]));
    return 0;
}

2. 中国剩余定理——表达整数的奇怪方式

给定 2n2n 个整数 a1,a2,…,ana1,a2,…,an 和 m1,m2,…,mnm1,m2,…,mn，求一个最小的非负整数 xx，满足 ∀i∈[1,n],x≡mi(mod ai)∀i∈[1,n],x≡mi(mod ai)。

输入格式

第 11 行包含整数 nn。

第 2…n+12…n+1 行：每 i+1i+1 行包含两个整数 aiai 和 mimi，数之间用空格隔开。

输出格式

输出最小非负整数 xx，如果 xx 不存在，则输出 −1−1。
如果存在 xx，则数据保证 xx 一定在 6464 位整数范围内。

#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;

    LL x = 0, m1, a1;
    cin >> m1 >> a1;
    for (int i = 0; i < n - 1; i ++ )
    {
        LL m2, a2;
        cin >> m2 >> a2;
        LL k1, k2;
        LL d = exgcd(m1, m2, k1, k2);
        if ((a2 - a1) % d)
        {
            x = -1;
            break;
        }

        k1 *= (a2 - a1) / d;
        k1 = (k1 % (m2/d) + m2/d) % (m2/d);

        x = k1 * m1 + a1;

        LL m = abs(m1 / d * m2);
        a1 = k1 * m1 + a1;
        m1 = m;
    }

    if (x != -1) x = (a1 % m1 + m1) % m1;

    cout << x << endl;

    return 0;
}

3. 求组合数3

给定 nn 组询问，每组询问给定三个整数 a,b,pa,b,p，其中 pp 是质数，请你输出 CbamodpCabmodp 的值。

输入格式

第一行包含整数 nn。

接下来 nn 行，每行包含一组 a,b,pa,b,p。

输出格式

共 nn 行，每行输出一个询问的解。

数据范围

1≤n≤201≤n≤20,
1≤b≤a≤10181≤b≤a≤1018,
1≤p≤1051≤p≤105,

 

#include <iostream>
#include <algorithm>

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 (b > a) 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;
    cin >> n;

    while (n -- )
    {
        LL a, b;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a, b, p) << endl;
    }

    return 0;
}

 4.求组合数4

输入 a,ba,b，求 CbaCab 的值。

注意结果可能很大，需要使用高精度计算。

输入格式

共一行，包含两个整数 aa 和 bb。

输出格式

共一行，输出 CbaCab 的值。

数据范围

1≤b≤a≤50001≤b≤a≤5000

输入样例：

#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;
    cin >> a >> b;

    get_primes(a);

    for (int i = 0; i < cnt; i ++ )
    {
        int p = primes[i];
        sum[i] = get(a, p) - get(a - b, p) - get(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]);
    puts("");

    return 0;
}

         5.满足条件的01序列（实质仍然是组合数）

这个得说道说道，思路是将问题转化成一张图，0是向右走，1是向上走，求合法的路径数

给定 nn 个 00 和 nn 个 11，它们将按照某种顺序排成长度为 2n2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 00 的个数都不少于 11 的个数的序列有多少个。

输出的答案对 109+7109+7 取模。

输入格式

共一行，包含整数 nn。

输出格式

共一行，包含一个整数，表示答案。

数据范围

1≤n≤1051≤n≤105

输入样例：

3

输出样例：

5

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010, mod = 1e9 + 7;


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 main()
{
    int n;
    cin >> 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;

    cout << res << endl;

    return 0;
}

6.容斥原理--能被整除的数 

很巧妙的思想，多看看

给定一个整数 nn 和 mm 个不同的质数 p1,p2,…,pmp1,p2,…,pm。

请你求出 1∼n1∼n 中能被 p1,p2,…,pmp1,p2,…,pm 中的至少一个数整除的整数有多少个。

输入格式

第一行包含整数 nn 和 mm。

第二行包含 mm 个质数。

输出格式

输出一个整数，表示满足条件的整数的个数。

数据范围

1≤m≤161≤m≤16,
1≤n,pi≤1091≤n,pi≤109

输入样例：

10 2
2 3

输出样例：

7

#include <bits/stdc++.h>
using namespace std;
typedef long long int 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;
}

明天上午学博弈论和记忆化搜索