自动搬运

查看原文

来自洛谷，原作者为

	diltraser **

搬运于2025-08-24 22:06:09，当前版本为作者最后更新于2018-11-08 18:12:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

很显然每个数在求和时出现的次数相等，设$d[i]$为动作总数为$i$个时某个数求和时的贡献，则

$ans=d[n]*sum/k^n( mod$ $19491001)$

试图递推$d[n]$，首先放式子

$d[i]=k^{i-1}+2*k^{i-2}+d[i-1]*k$

第一项$k^{i-1}$表示动作总数为$i$时排列数量，在之后可以放$x$使计数++；

第二项$2*k^{i-2}$表示排列中以$x$/$x-1$结尾的数量，在此之后会产生组合技效果；

第三项$d[i-1]*k$表示排列前$i-1$位中$x$的贡献；

然后经过找规律归纳推理，可得

$d[n]=n*k^{n-1}+2*(n-1)*k^{n-2}$

代入进$ans$中，得

$ans=sum*(n*k+2*(n-1))/k^2$

求出$sum$%$mod$,$k$的逆元,$n$%$mod$即可AC

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype> 
using namespace std;
typedef long long ll;
ll mod = 19491001;
int n;
char s[1000010];
int len; 
ll N; 
ll k;
ll tot;


ll quick_pow(ll x, int k) {
    ll res = 1;
    while(k) {
        if(k & 1) res = res * x % mod;
        x = x * x % mod;
        k >>= 1;
    }
    return res;
}

ll inv(long long x) {
    return quick_pow(x, mod - 2);
}

 
int main(){
    char ch=getchar();
    while(isdigit(ch)){
        s[++len]=ch;
        N=(10*N+ch-'0')%mod;
        ch=getchar();
    }
    scanf("%lld",&k);
    int i,val;
    for(i=1;i<=k;i++){
        scanf("%d",&val);
        tot=(tot+val)%mod;
    }
    ll invk=inv(k);
    printf("%d",(N*k%mod+2*N-2)%mod*tot%mod*invk%mod*invk%mod);
    return 0;
}