题意
题意屏幕快照 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)); } }
全部评论
(1) 回帖