2018多校（第一场） F题 伯努利数

题意

题意屏幕快照 2018-07-20 22.20.23.png
给出n个数，求

数据范围：1<=n<=1000,1<=ai<=1e9

解法

子问题: 所有数都等于x的情况

设答案为$ f(x,n) $

数j为答案的次数应该是$ j^2-(j-1)^2，j^2 $意味着所有答案小于等于j的数量，(j-1)^2意味着所有答案小于等于j-1的数量，两者相减就得到了答案正好等于j的数量。
对所有数求总贡献，得到

$ x^{n+1} $用快速幂求，复杂度O(logn)，$ \sum_{i=1}^{x-1} i^n $用伯努利数求，复杂度O(n)。现在我们可以在O(n)时间内计算$ f(x,n) $。

伯努利数求和的公式是：

原问题转化为子问题

如果对原数组排序，那么就可以得到递增的ai数组

对于1...a1的答案之和，可以直接转化为f(a1,n)
现在考虑a1+1到a2的答案
同样是计算每个答案的次数，j的次数是$ a_1j^{n-1} - a_1(j-1)^{n-1} $，思路和上面是一样的。

求和得到$ a{i-1}+1$到$ a{i} $的答案是

分区间处理到an就得出了答案

代码

#include
using namespace std;
#define llp(i,x,y) for(int i=x;iy
#define REP llp
#define rlp(i,x,y) for(int i=y-1;i>=x;--i)  // [x,y) y->x
#define PER rlp
#define lp(i,x) for(int i=0;ix
#define mem(a,x) memset(a,x,sizeof a)
typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair pii;
typedef __int128 ull;
#define fi first
#define se second
#define pb push_back
const ll MOD=1e9+7;
const ll N=1e3+50;
const db eps=1e-9;
ll qpower(ll x,ll p,ll M = MOD){ll ans=1;while(p){if (p&1) ans=ans*x%M;p>>=1;x=x*x%M;}return ans;}
ll gcd(ll a,ll b){ll x;while(b){x = a%b;a = b;b = x;}return a;}
ll modp(ll x,ll p){return (x%p+p)%p;}
// std::ios::sync_with_stdio(false);
// srand((unsigned)time(NULL));
// C(m, n) m选n个
ll inv[1500];
void init2(){
  inv[1] = 1;
  for (int i = 2; i <= 1200; i++) inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
}
ll C[1200][1200];
void init() {
    C[0][0] = 1;
    for (int i = 1; i <= 1100; i++) {
        for (int j = 0; j <= i; j++) {
            C[i][j] = ((ll) C[i - 1][j - 1] + C[i - 1][j]) % MOD;
        }
    }
}
ll B[2000];
void init3(){
  B[0] = 1;
  llp(n,1,1050){
    B[n] = 0;
    llp(k,0,n) B[n] = (B[n] + C[n+1][k]*B[k]%MOD)%MOD;
    B[n] = modp(B[n]*(-inv[n+1]),MOD);
  }
}
ll Bi(ll n,ll k){
  ll ans = 0;
  llp(i,1,k+2) ans = ( ans + C[k+1][i]*B[k+1-i]%MOD*qpower(n+1,i)%MOD )%MOD;
  ans = ans * inv[k+1]%MOD;
  return ans;
}
ll f(ll x,ll n){
  return modp(qpower(x,n+1) - Bi(x-1,n),MOD);
}
ll a[1005];
int main(){
  // freopen("f.txt","r",stdin);
  init();
  init2();
  init3();
  int n;
  while(scanf("%d",&n)!=EOF){
    llp(i,0,n) scanf("%lld",a+i);
    sort(a,a+n);
    ll ans = 0;
    ans = f(a[0],n);
    ll pre = 1;
    llp(i,1,n){
      pre = pre*a[i-1]%MOD;
      ans = (ans + modp( f(a[i],n-i) - f(a[i-1],n-i) ,MOD)*pre%MOD) %MOD;
    }
    printf("%lld\n",modp(ans,MOD));
  }
}