5.7xrT2

发表于 更新于 本文字数： 3.7k 阅读时长 ≈ 3 分钟

对自然数 xx 定义 U(x)={0,1,2,...,x}U(x)=\{0,1,2,...,x\}，给定正整数 n,mn,m，求：

∑r=0n−1(∑S⊆U(nm−1)[(∑x∈Sx) mod n=r])2\sum_{r=0}^{n-1}(\sum_{S\subseteq U(nm-1)}[(\sum_{x\in S}x)\bmod n=r])^2

答案对 998244353998244353 取模，n,m≤1012n,m\le 10^{12} 。

多组数据，T≤50T\le 50 。

一个 rr 的方案是：

∑i=0nm[i mod n=r][xi]∏j=0n−1(1+xj)m\sum_{i=0}^{nm}[i\bmod n=r][x^i]\prod_{j=0}^{n-1}(1+x^j)^m

指数上有取模，非常难搞，但是可以联想到单位根可以做这个。

赛时想法，一个 rr 的答案是：

[ωnrx]∏i=0n−1(1+ωnxi)m[\omega_n^{rx}]\prod_{i=0}^{n-1}(1+\omega_n^{xi})^m

然后我的想法是，xx 乘上一个与 nn 互质的数后，右边的多项式是不会变的，这样说明 gcd⁡(r,n)\gcd(r,n) 相同的 rr 的答案是相同的。

然后带入 xx 为一些具体的值可以得到一些 rr 的答案的组合，不过似乎不太可做。

正解没有用这样的生成函数推导，直接绕开了「求出每个 rr 的答案」这一步。

令 ∑x=s\sum x=s 的方案数为 asa_s，然后直接单位根反演：

∑i=0nm−1ai[i mod n=r]=1n∑i=0nm−1ai∑j=0n−1ωnj(i−r)=1n∑j=0n−1ωn−jr∑i=0nm−1aiωnij=1n∑j=0n−1ωn−jr∏i=0n−1(1+ωnij)m\sum_{i=0}^{nm-1}a_i[i\bmod n=r]=\frac{1}{n}\sum_{i=0}^{nm-1}a_i\sum_{j=0}^{n-1}\omega_n^{j(i-r)}\\ =\frac{1}{n}\sum_{j=0}^{n-1}\omega_n^{-jr}\sum_{i=0}^{nm-1}a_i\omega_{n}^{ij}\\ =\frac{1}{n}\sum_{j=0}^{n-1}\omega_n^{-jr}\prod_{i=0}^{n-1}(1+\omega_n^{ij})^m\\

设 W(j)=∏i=0n−1(1+ωnij)mW(j)=\prod_{i=0}^{n-1}(1+\omega_n^{ij})^m，然后直接写答案的式子：

1n2∑r=0n−1∑u=0n−1∑v=0n−1ωn−(u+v)rW(u)W(v)=1n2∑u=0n−1∑v=0n−1W(u)W(v)∑r=0n−1ωn−(u+v)r\frac{1}{n^2}\sum_{r=0}^{n-1}\sum_{u=0}^{n-1}\sum_{v=0}^{n-1} \omega_{n}^{-(u+v)r}W(u)W(v)\\ = \frac{1}{n^2}\sum_{u=0}^{n-1}\sum_{v=0}^{n-1} W(u)W(v)\sum_{r=0}^{n-1}\omega_{n}^{-(u+v)r}

此时直接写答案的关键一步：右边 ∑r=0n−1ωn−(u+v)r\sum_{r=0}^{n-1}\omega_{n}^{-(u+v)r} 只有当 u+v∣nu+v|n 时不为 00 。

=1n∑u=0n−1W(u)W(n−u)=\frac{1}{n}\sum_{u=0}^{n-1} W(u)W(n-u)

只要算 W(u)W(u) 就行了，容易发现 W(u)W(u) 的取值只和 gcd⁡(u,n)\gcd(u,n) 有关，因此直接求 d∣nd|n 的 W(d)W(d)。

W(d)=∏i=0n/d−1(1+ωn/di)mdW(d)=\prod_{i=0}^{n/d-1}(1+\omega_{n/d}^{i})^{md}

此时需要解决的是 F(p)=∏i=0p−1(1+ωpi)F(p)=\prod_{i=0}^{p-1}(1+\omega_{p}^i)。

我赛时的神秘做法也是需要这个的，因此打表之后发现 F(p)=1+(−1)p+1F(p)=1+(-1)^{p+1}。

也有很优雅的证明，考虑单位根本质是 xn=1x^n=1 的根。

xn−1=∏i=0n−1(x−ωni)x^n-1=\prod_{i=0}^{n-1}(x-\omega_{n}^i)

带入 x=−1x=-1 。

(−1)n−1=(−1)n∏i=0n−1(1+ωni)(-1)^n-1=(-1)^n \prod_{i=0}^{n-1} (1+\omega_{n}^i)

移项就证完了。

又因为上面的 gcd⁡(u,n)=gcd⁡(n−u,n)\gcd(u,n)=\gcd(n-u,n)，因此得到：

1n∑u=0n−1W(u)W(n−u)=1n∑u=0n−1W(u)2=1n∑d∣nφ(d)W(n/d)2=1n∑d∣nφ(d)F(d)2mn/d=1n∑2∤d,d∣nφ(d)22mn/d\frac{1}{n}\sum_{u=0}^{n-1} W(u)W(n-u)\\ =\frac{1}{n}\sum_{u=0}^{n-1} W(u)^2\\ =\frac{1}{n}\sum_{d|n}\varphi(d)W(n/d)^2\\ =\frac{1}{n}\sum_{d|n}\varphi(d)F(d)^{2mn/d}\\ =\frac{1}{n}\sum_{2\nmid d,d|n}\varphi(d)2^{2mn/d}

因此直接搜索出所有因数，同时求出其欧拉函数，复杂度 O(T(n+d(n)log⁡n))\mathcal O(T(\sqrt n+d(n)\log n))。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void Yui_Yagi() {
  ll n, m;
  cin >> n >> m;

  V<Int> vec;
  ll T = n;
  for (int i = 2; 1ll * i * i <= T; i++) {
    int s = 0;
    for (; T % i == 0; s++) T /= i;
    if (s && i > 2) vec.pb({i, s});
  }
  while (T % 2 == 0) T /= 2;
  if (T > 1) vec.pb({T, 1});

  mint res = 0;
  auto dfs = [&](auto lf, int x, ll d, ll ph) -> void {
    if (x == sz(vec)) {
      res +=
          (mint)ph * (2_m).pow(2 * m % (P - 1) * (n / d % (P - 1)) % (P - 1));
      return;
    }
    For(i, 0, vec[x].se) {
      lf(lf, x + 1, d, ph);
      if (i < vec[x].se) {
        d *= vec[x].fi, ph *= vec[x].fi;
        if (!i) ph = ph / vec[x].fi * (vec[x].fi - 1);
      }
    }
  };
  dfs(dfs, 0, 1, 1);
  cout << res / n << endl;
}