洛谷比赛-P5011 水の造题-题解

题目地址与题意见链接

暴力就是 $O(k^n)$ 吧，不过 $n$ 非常之大，有 $10^{10^6}$ （高精可怕.jpg）

但是我们发现，对于求期望，那么就是概率 $imes$ 权值，所以我们可以先求出每种动作的贡献：

每种动作出现在某个位置的概率为 $frac{1}{k}$ ，贡献为它的 $val$ ，总共有 $n$ 个可以出现的位置，所以贡献为 $sum_{i=0}^{k-1}frac{n imes val_i}{k}$

接下来就是组合技的多的贡献，每个组合技还会再贡献一次，所以我们这样来看：

每个组合技出现的概率为 $frac{1}{k^2}$ ，有 $n-1$ 个可以出现的位置，每一种的贡献为 $val_i+val_{(i+1)\%k}$ ，所以总贡献为 $sum_{i=0}^{k-1}frac{(n-1) imes (val_i+val_{(i+1)\%k})}{k^2}$

那么我们 $O(k)$ 的算一下就好啦，关于取模除法我们用费马小定理逆元就可以了，因为 $19491001$ 是个~~非常神奇且有巨大意义的~~质数，读入 $n$ 时直接取模就好啦。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int M=1e6+10;
const ll Mod=19491001;
char s[M];
ll k,A[M],n,w;
ll inv_k,inv_k2;
void readin(){
	scanf("%s",s);
	int len=strlen(s);
	for(int i=0;i<len;i++){
		n=(n*10ll%Mod+(s[i]&15))%Mod;
	}	w=(n-1+Mod)%Mod;
}
ll Sqr(ll a){return a*a%Mod;}
ll fpow(ll a,ll b){
	ll ans=1;
	for(;b;b>>=1,a=(a*a)%Mod)if(b&1)ans=(ans*a)%Mod;
	return ans;
}
ll ans,sum1,sum2;
int main(){
	readin();
	scanf("%lld",&k);
	for(int i=0;i<k;i++){
		scanf("%lld",&A[i]);
		sum1=(sum1+A[i])%Mod;
		if(i)sum2=(sum2+(A[i-1]+A[i])%Mod)%Mod;
	}	sum2=(sum2+(A[0]+A[k-1])%Mod)%Mod;
	inv_k=fpow(k,Mod-2);
	inv_k2=(Sqr(inv_k)%Mod*w)%Mod;inv_k=(inv_k*n)%Mod;
	ans=(sum1*inv_k%Mod+sum2*inv_k2%Mod)%Mod;
	printf("%lld
",ans);
	return 0;
}

下面还有一种解法，由 $m hdxrie$ |Orz|提供：

我们先不考虑开头结尾，那么每个数都有前后：

我们考虑，对于一个位置的动作，它前后都不是组合技，那么只会贡献一次，那么前面不是和它组合的概率为 $frac{k-1}{k}$ ，后面不是和它组合的概率为 $frac{k-1}{k}$ ，然后当前选这个的概率为 $frac{1}{k}$ ，有 $n-2$ 个位置可以这样选，那么贡献为 $(frac{k-1}{k})^2 imes frac{1}{k} imes val_i imes (n-2)$

对于可以形成组合技的（这里只考虑组成一个），那么就是后面和它组合，前面不组合；或者前面组合，后面不组合。那么贡献就为 $left(frac{k-1}{k} imes left(frac{1}{k} ight)^2 imes val_i imes 2 imes (n-2) ight) imes 2$ （这时 $val_i$ 要算两次贡献，同样还是有 $n-2$ 个可以的位置）

对于前后都可以组合的，概率为 $left(frac{1}{k} ight)^3$ ，所以贡献为 $left(frac{1}{k} ight)^3 imes val_i imes 3 imes (n-2)$ （这里要算前后三次）

然后对于开始和结尾两个单独的，我们考虑组不组合，那么组合贡献为 $frac{1}{k} imes frac{1}{k} imes val_i imes 2$ ，不组合的为 $frac{1}{k} imes frac{k-1}{k} imes val_i imes 2$ ，前后一样所以 $×2$ 。

下面上代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int N=1000010;
const LL mod=19491001;
char num[N];int len;
LL n,m,inv1,inv2,inv3,val,ans,sum;
LL power(LL a,LL p)
{
    LL v=1;
    for(;p;p>>=1,a=a*a%mod)
     if(p&1)v=v*a%mod;
    return v;
}
int main()
{
    scanf("%s%lld",num+1,&m);
    len=strlen(num+1);inv1=power(m,mod-2);
    inv2=inv1*inv1%mod;inv3=inv2*inv1%mod;
    for(int i=1;i<=len;i++)
     n=(n*10+num[i]-'0')%mod;
    for(int i=1;i<=m;i++)
     scanf("%lld",&val),(sum+=val)%=mod;
    (ans+=2ll*sum%mod*(m-1)%mod*inv2%mod)%=mod;
    (ans+=4ll*sum%mod*inv2%mod)%=mod;
    (ans+=(n-2)*sum%mod*(m*m%mod-2*m+1)%mod*inv3%mod)%=mod;
    (ans+=4ll*(n-2)%mod*sum%mod*(m-1)%mod*inv3%mod)%=mod;
    (ans+=3ll*(n-2)%mod*sum%mod*inv3%mod)%=mod;
    if(ans<0)ans+=mod;printf("%lld
",ans);
    return 0;
}

洛谷比赛-P5011 水の造题-题解

题目地址与题意见链接

End~