洛谷 P3702 [SDOI2017] 序列计数 题解代码 动态规划

[SDOI2017] 序列计数

题目描述

Alice 想要得到一个长度为 $n$ 的序列，序列中的数都是不超过 $m$ 的正整数，而且这 $n$ 个数的和是 $p$ 的倍数。

Alice 还希望，这 $n$ 个数中，至少有一个数是质数。

Alice 想知道，有多少个序列满足她的要求。

输入格式

一行三个数，$n,m,p$。

输出格式

一行一个数，满足 Alice 的要求的序列数量，答案对 $20170408$ 取模。

样例 #1

样例输入 #1

3 5 3

样例输出 #1

33

提示

对 $20\%$ 的数据，$1\le n,m\le 100$。

对 $50\%$ 的数据，$1\le m\le 100$。

对 $80\%$ 的数据，$1\le m\le 10^6$。

对 $100\%$ 的数据，$1\le n\le 10^9,1\le m\le 2\times 10^7,1\le p\le 100$。

原题

洛谷P3702——传送门

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int mod = 20170408;
const int maxm = 2e7 + 6;
int n, m, p;
ll x[100]; // 对不超过m的所有正整数模p的值计数
ll y[100]; // 对不超过m的所有非质数模p的值计数
// 对于枚举到第i个位置的dp，采用滚动数组
ll dp_x[100]; // 取不超过m的所有正整数时和为i的序列数量
ll dp_y[100]; // 取不超过m的所有非质数时和为i的序列数量
// 因此，答案就为dp_x[p%p]-dp_y[p%p]
bool not_prime[maxm];

void mul(ll a[], ll b[])
{
    vector<ll> c(2 * p, 0);
    for (int i = 0; i < p; i++)
    {
        for (int j = 0; j < p; j++)
        {
            c[i + j] += a[i] * b[j];
            c[i + j] % mod;
        }
    }
    for (int i = 0; i < p; i++)
    {
        a[i] = (c[i] + c[i + p]) % mod;
    }
    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> p;
    // 质数筛
    not_prime[1] = 1;
    for (int i = 2; i <= m; i++)
    {
        if (!not_prime[i])
        {
            for (int j = i * 2; j <= m; j += i)
            {
                not_prime[j] = 1;
            }
        }
    }
    // 在x和y数组中计数
    for (int i = 1; i <= m; i++)
    {
        x[i % p]++;
        if (not_prime[i])
            y[i % p]++;
    }
    // 和为0的序列数量为1
    dp_x[0] = 1;
    dp_y[0] = 1;
    // 快速幂计算序列数量
    while (n)
    {
        if (n & 1)
        {
            mul(dp_x, x);
            mul(dp_y, y);
        }
        mul(x, x);
        mul(y, y);
        n >>= 1;
    }
    // dp_x[p%p]-dp_y[p%p]即dp_x[0]-dp_y[0]
    cout << (dp_x[0] - dp_y[0] + mod) % mod << '\n';

    return 0;
}