题解 P11029 『DABOI Round 1』A Simple Problem

· · 题解

验题人题解。

出题人标程一开始写错了，所以我重写了 std 并造了数据。

题意

\left( \prod\limits^n_i\prod\limits^i_j\prod\limits^j_k k^k \right) \bmod 998244353

分析

观察到 k 是最不好求的，且答案和 i,j 没有关系。

现在的问题是求 k^k 相乘了多少次，也就是求 k \le i \le j \le n 的 (i,j) 对数，问题也就转化成了 n-k+1 个数中选两个数（可选两个相同的数）的方案数，即：

\begin{aligned} \dbinom{n-k+1}{2} + (n-k+1) & = \dfrac{(n-k+1)(n-k)} 2 + (n-k+1)\\ & = \dfrac{(n-k+1)(n-k+2)} 2 \end{aligned}

因此我们所求答案：

\prod\limits^n_i\prod\limits^i_j\prod\limits^j_k k^k = \prod\limits^n_k (k^k)^{\frac{(n-k+1)(n-k+2)} 2} = \prod\limits^n_k k^{\frac 1 2 k(n-k+1)(n-k+2)}

做到这里其实可以直接求了，但是进一步由费马小定理 a^{p-1} \equiv 1 \pmod p 推导可以得到：

\left( \prod\limits^n_k k^{\frac 1 2 k(n-k+1)(n-k+2)} \right) \bmod 998244353 = \left( \prod\limits^n_k k^{\frac 1 2 k(n-k+1)(n-k+2) \bmod 998244352} \right) \bmod 998244353

然后就可以愉快的枚举 k 再快速幂了，时间复杂度 O(n \log n)，有点小卡常。

最大点在 C++14 O2 下跑了 \text{236ms}，但是有些选手被卡常了，建议自行优化常数。

//the code is from chenjh
#include<cstdio>
using namespace std;
typedef long long LL;
const int mod=998244353;
int qpow(int a,int b){
    int ret=1;
    for(;b;b>>=1,a=(LL)a*a%mod)if(b&1)ret=(LL)ret*a%mod;
    return ret%mod;
}
int n;
int main(){
    scanf("%d",&n);
    int ans=1;
    for(int i=1;i<=n;i++) ans=(LL)ans*qpow(i,(LL)i*((LL)(n-i+1)*(n-i+2)/2%(mod-1))%(mod-1))%mod;
    printf("%d\n",ans);
    return 0;
}

Update on 2024/9/9：

用 PyPy 3 写了个解法，可以通过，请不要再说卡常了。

n=int(input())
s=1
for i in range(1,n+1):
    s=s*pow(i,i*(n-i+1)*(n-i+2)//2%998244352,998244353)%998244353
print(s)