【做题】SRM704 Div1 Median - ModEquation—

原文链接 https://www.cnblogs.com/cly-none/p/SRM704Div1B.html

给出$n$和模数$P$。$q$次询问，每次给出一个$[0,P-1]$范围内的整数$v$，求有多少长度为$n$的序列$\{x\}$满足$x_i$都是$[0,P-1]$范围内的整数且$\prod x_i \equiv v \pmod P$，答案对$10^9 + 7$取模。

$n \leq 50 , \ q \leq 10^3, \ P \leq 10^9$

注意：$P$不是质数。

这题大概就是道结论题。

首先，我们容易得到$O(n P^2)$的dp。

考虑$P$为质数的情况。我们发现，对于所有$a \neq 1$，$\{a, 2a, \cdots, (P-1)a\}$都是互不相等的，即它在模$P$意义下就是$\{1, 2, \cdots , P-1\}$。那么，在dp中$1$到$P-1$的所有数的转移都是相同的，那它们的答案也应当是相等的。

尝试把这个结论拓展到$P$为正整数的情况下。我们设模$P$意义下的每个数 $v = v' \times d $ ，其中 $d=gcd(v,P)$ 。同样地，$\{ v', 2v', \cdots , (P-1)v' \}$互不相等，于是 $v$ 乘以$1$到$P-1$的所有数就是$\{d, 2d, \cdots , (P-1)d \}$。于是，我们发现$gcd(x,P)$相同的$x$在dp中有相同的转移，那就可以把它们的状态合并在一起。这样这个dp就优化到了$O(n \sigma (n)^2)$的了，已经可以通过本题。

但我们还可以套路地对$P$做质因数分解，得到$P = p_1^{a_1} p_2^{a_2} \cdots p_n^{a_n}$，然后以每个$p_i^{a_i}$为模数，分别求一次答案。考虑所有模$P$意义下的数和模$p_i^{a_i}$得到的序列是一一对应的，所以我们可知答案就是以每个$p_i^{a_i}$为模数的答案的积。那么，就能$O(n \log^2 P + q \log P)$地解决本题。（这里的$\log P$分析并不准确）

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

typedef double db;

#define fir first

#define sec second

class ModEquation {

public:

    vector <int> count( int n, int K, vector <int> query ) ;

};

const int MAX = 100000, MP = 30, N = 60, MOD = (int)(1e9 + 7);

int isp[MAX + 10], pri[MAX], pcnt, fac[MP], fcnt, num[MP];

int power(int a,int b) {

  int ret = 1;

  while (b) {

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

    a = 1ll * a * a % MOD;

    b >>= 1;

  }

  return ret;

}

void prework() {

  for (int i = 2 ; i <= MAX ; ++ i) {

    if (!isp[i]) pri[++pcnt] = i;

    for (int j = 1 ; pri[j] * i <= MAX ; ++ j) {

      isp[pri[j] * i] = 1;

      if (i % pri[j] == 0) break;

    }

  }

}

int dp[MP][N][MP];

void init() {

  pcnt = fcnt = 0;

  memset(isp,0,sizeof isp);

  memset(dp,0,sizeof dp);

}

vector <int> ModEquation::count(int n, int K, vector <int> query) {

  init();

  prework();

  for (int i = 1 ; i <= pcnt ; ++ i) {

    if (K % pri[i]) continue;

    fac[++fcnt] = pri[i];

    num[fcnt] = 0;

    while (K % pri[i] == 0)

      ++ num[fcnt], K /= pri[i];

  }

  if (K != 1) {

    ++ fcnt;

    fac[fcnt] = K;

    num[fcnt] = 1;

  }

  for (int i = 1 ; i <= fcnt ; ++ i) {

    dp[i][0][0] = 1;

    for (int j = 0 ; j < n ; ++ j) {

      for (int a = 0 ; a <= num[i] ; ++ a)

        for (int b = num[i], t = 1 ; b >= 0 ; -- b, t *= fac[i]) {

          (dp[i][j+1][min(num[i], a + b)] += 1ll * dp[i][j][a] * (t - t / fac[i]) % MOD) %= MOD;

        }

    }

    for (int a = num[i], t = 1 ; a >= 0 ; -- a, t *= fac[i]) {

      dp[i][n][a] = 1ll * dp[i][n][a] * power(t - t / fac[i], MOD - 2) % MOD;

    }

  }

  vector<int> ans = vector<int>();

  for (int id = 0 ; id < (int)query.size() ; ++ id) {

    int v = query[id], ret = 1;

    for (int i = 1 ; i <= fcnt ; ++ i) {

      int tmp = v, rec = 0;

      for (int j = 1 ; j <= num[i] ; ++ j)

				if (tmp % fac[i] == 0) tmp /= fac[i], ++ rec;

      ret = 1ll * ret * dp[i][n][rec] % MOD;

    }

    ans.push_back(ret);

  }

  return ans;

}

#undef fir

#undef sec

小结：数论题有一些基本结论和套路还是非常重要的。

巴特西

【做题】SRM704 Div1 Median - ModEquation——数论

最新文章

热门文章