题解 P5011 【水の造题】

· · 题解

很显然每个数在求和时出现的次数相等，设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;
}