题解：AT_arc114_c [ARC114C] Sequence Scores

· · 题解

1. 前言

你谷新人第二篇题解qwq。

2. 做法

根据其他题解可得 （其实是因为我懒得再打一遍了），答案显然，推一下柿子得：

\sum_{i=1}^n \sum_{j=1}^m m^{n-i}(m^{i-1}-\sum_{k=1}^{i-1}m^{k-1}(m-j)^{i-k-1}) \\ =nm^n- \sum_{i=1}^n \sum_{j=1}^m \sum_{k=1}^{i-1} m^{n-i+k-1} (m-j)^{i-k-1} \\ =nm^n- \sum_{i=1}^n \sum_{k=1}^{i-1} m^{n-i+k-1} \sum_{j=0}^{m-1} j^{i-k-1} \\ =nm^n- \sum_{i=1}^{n-1} (n-i) m^{n-i+1} \sum_{j=0}^{m-1}j^{i-1} \\ =nm^n- m^{n-2} \sum_{j=0}^{m-1} \sum_{i=1}^{n-1} (\frac{j}{m})^{i-1} (n-i)

直接做就可以 O(nm) 了，但是其实可以再推一下。

设 p=\frac{j}{m}。

\sum_{i=1}^{n-1} p^{i-1}(n-i) \\ =\sum_{i=1}^{n-1} p^{i-1} \sum_{j=1}^{n-i} 1 \\ =\sum_{j=1}^{n-1} \sum_{i=0}^{n-j-1} p^i \\ =\sum_{j=1}^{n-1} \frac{p^{n-j}-1}{p-1} \\ =\frac{\sum\limits_{j=1}^{n-1} p^j-(n-1)}{p-1} \\ =\frac{\frac{p^n-p}{p-1}-(n-1)}{p-1}

那么我们就得到了 O(n\log n) 的做法。

扔个代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define mod 998244353
int n,m;
int qmi(int a,int b=mod-2)
{
    int ans=1;
    while(b){
        if(b&1)ans=(LL)ans*a%mod;
        a=(LL)a*a%mod,b>>=1;
    }return ans;
}
int main()
{
    int i,ans=0;
    cin>>n>>m;
    if(n==1)return cout<<m,0;
    int t=qmi(m);
    for(i=0;i<m;i++){
        int x=(LL)i*t%mod,s=qmi(x+mod-1);
        ans=(ans+(LL)s*((LL)(qmi(x,n)+mod-x)*s%mod+mod-n+1))%mod;
    }
    ans=((LL)m*m%mod*n+mod-ans)%mod;
    cout<<(LL)ans*qmi(m,n-2)%mod;
}

可不可以做到 O(n) 呢，答案是肯定的。

我们发现要在 O(n) 复杂度内解决这个问题只需要快速求出 (\frac{k}{m})^n 和 (\frac{k}{m} -1)^{-1} 即可。

然后就不出意外的抢了 Atcoder 的最优解。