先思考n个数字相同的情况,即
对每个数最为最大值的数量打表会发现每个数为最大值的数量刚好与自然数有关,有这样的关系
我们设num[i]为i为最大值出现的数量,那么我们再记作S[i]为出现的数的数量的和
即有
那么我们再看看原来的ans就可以变为
同样的我们也可以发现一个规律
同样的有,最后的答案和我们一开始的推出的形式是一样的即
现在要解决的问题就是如何快速求出S[j]
我们可以分段求和处理,,,
举个例子就可以理解了,如求解
那么就有
可以用两个自然数幂次和相减来得到
剩下的就是如何快速求出自然数次幂和了,有一个基于伯努利数的自然数求和公式
给出求解自然数和的模版
typedef long long LL;
const LL mod = 1000000007;
const int N = 1005;
LL C[N][N];
LL B[N],Inv[N];
LL Tmp[N];
LL n;
void Init()
{
//预处理组合数
for(int i=0; i<N; i++)
{
C[i][0] = C[i][i] = 1;
if(i == 0) continue;
for(int j=1; j<i; j++)
C[i][j] = (C[i-1][j] % mod + C[i-1][j-1] % mod) % mod;
}
//预处理逆元
Inv[1] = 1;
for(int i=2; i<N; i++)
Inv[i] = (mod - mod / i) * Inv[mod % i] % mod;
//预处理伯努利数
B[0] = 1;
for(int i=1; i<N; i++)
{
LL ans = 0;
if(i == N - 1) break;
for(int j=0; j<i; j++)
{
ans += C[i+1][j] * B[j];
ans %= mod;
}
ans *= -Inv[i+1];
ans = (ans % mod + mod) % mod;
B[i] = ans;
}
}
LL sum(int n,int k)
{
Tmp[0] = 1;
for(int i=1; i<N; i++)
Tmp[i] = Tmp[i-1] * (n + 1) % mod;
LL ans = Inv[k+1];
LL sum = 0;
for(int i=1; i<=k+1; i++)
{
sum += C[k+1][i] * Tmp[i] % mod * B[k+1-i] % mod;
sum %= mod;
}
ans *= sum;
ans %= mod;
return ans;
}
也就有代码
#include <iostream> #include <string.h> #include <stdio.h> #include <algorithm> using namespace std; typedef long long LL; const LL mod = 1000000007; const int N = 1005; LL C[N][N]; LL B[N],Inv[N]; LL Tmp[N]; LL n; void Init() { //预处理组合数 for(int i=0; i<N; i++) { C[i][0] = C[i][i] = 1; if(i == 0) continue; for(int j=1; j<i; j++) C[i][j] = (C[i-1][j] % mod + C[i-1][j-1] % mod) % mod; } //预处理逆元 Inv[1] = 1; for(int i=2; i<N; i++) Inv[i] = (mod - mod / i) * Inv[mod % i] % mod; //预处理伯努利数 B[0] = 1; for(int i=1; i<N; i++) { LL ans = 0; if(i == N - 1) break; for(int j=0; j<i; j++) { ans += C[i+1][j] * B[j]; ans %= mod; } ans *= -Inv[i+1]; ans = (ans % mod + mod) % mod; B[i] = ans; } } LL sum(int n,int k) { Tmp[0] = 1; for(int i=1; i<N; i++) Tmp[i] = Tmp[i-1] * (n + 1) % mod; LL ans = Inv[k+1]; LL sum = 0; for(int i=1; i<=k+1; i++) { sum += C[k+1][i] * Tmp[i] % mod * B[k+1-i] % mod; sum %= mod; } ans *= sum; ans %= mod; return ans; } long long a[1005]; int main() { Init(); int n; while(scanf("%d",&n)!=EOF) { for(int i=0;i<n;i++) scanf("%lld",&a[i]); if(n==1) { printf("%lld\n",sum(a[0],1)); continue; } sort(a,a+n); long long ans=a[n-1],s=1; for(int i=0;i<n;i++) ans=ans*a[i]%mod; for(int i=0;i<n;i++) { if(i==0) ans=(ans-s*(sum(a[i],n-i)))%mod; else if(a[i]!=a[n-1]) { ans=(ans-s*(sum(a[i],n-i)-sum(a[i-1],n-i)))%mod; } else if(i==n-1&&a[i-1]!=a[n-1]) { ans=(ans-s*(sum(a[i]-1,n-i)-sum(a[i-1],n-i)))%mod; } s=s*a[i]%mod; } printf("%lld\n",(ans+mod)%mod); } return 0; }
全部评论
(0) 回帖