[CodeForces891E] 루스트 - 생성 함수 - 확률과 기대

Lust

A false witness that speaketh lies!
You are given a sequence containing n integers. There is a variable res that is equal to 0 initially. The following process repeats k times.
Choose an index from 1 to n uniformly at random. Name it x. Add to res the multiply of all ai’s such that 1 ≤ i ≤ n, but i ≠ x. Then, subtract ax by 1.
You have to find expected value of res at the end of the process. It can be proved that the expected value of res can be represented as an irreducible fraction . You have to find .

Input

The first line contains two integers n and k (1 ≤ n ≤ 5000, 1 ≤ k ≤ 109) — the number of elements and parameter k that is specified in the statement.
The second line contains n space separated integers a1, a2, …, an (0 ≤ ai ≤ 109).

Output

Output a single integer — the value .

Examples

input

2 1
5 5

output

5

input

1 10
80

output

10

input

2 2
0 0

output

500000003

input

9 4
0 11 12 9 20 7 8 18 2

output

169316356

신문제 하나.. 너무 약해서 문제를 보면서 한참을 미루었는데..
생각:
우선, 만약에 현재 어떤 조작 서열을 얻었다면, ai가 조작된 횟수를 bi로 설정하면 기대치에 대한 기여는 다음과 같다.
cont=∏i=1nai−∏i=1n(ai−bi)
이게 순서가 상관없다는 걸 알 수 있어요.
그래서 답안을 계산하는 방식을 얻을 수 있다.
ans=∏i=1nai−∑∑ni=1bi==k1nkk!∏ni=1bi!∏i=1n(ai−bi)
그중, k!∏ni=1bi! 불완전 상이원소의 선택 배열 공식입니다.
앞부분은 너무 간단해서 잠시 고려하지 않고 뒷부분, 즉
∑∑ni=1bi==k1nkk!∏ni=1bi!∏i=1n(ai−bi)
단순화 단순화:
k!nk∑∑ni=1bi==k∏i=1nai−bibi!
구문 및 기호와 그 후방 내용의 생성 함수를 작성하는 것을 고려합니다.
F(x)=∏i=1n∑j⩾0ai−jj!xj
그러면 F(x)의 k 항목이 원하는 답입니다.
구화 기호를 관찰하면 ex의 테일러 전개 형식과 비슷하다는 것을 알 수 있다. 그래서 다음과 같다.
F(x)=∏i=1nex(ai−x)
약간:
F(x)=enx∏i=1n(ai−x)
연승 기호 후의 식에 대해 O(n2) 폭력 다항식 곱셈 계수를 고려하다.(이 단계는 분명히 FFT를 나눌 수 있음) 그래서 ∑i=0ncixi=∏i=1n(ai−x)을 설정했는데 그 중에서 ci가 구한 계수는 다음과 같다.
F(x)=enx∑i=0ncixi
enx를 다시 테일러로 전개하여 방금 얻은 다항식과 곱하여 F(x)의 k차항계수의 표현식을 얻는다.
[xk]F(x)=∑i=0ncink−i(k−i)!
원식으로 다시 가져옵니다.
ans=∏i=1nai−k!nk∑i=0ncink−i(k−i)!
최종 형식을 얻기 위해 간소화:
ans=∏i=1nai−∑i=0nciki−ni
O(n) 이 식으로 계산하면 돼요~
총 복잡도 O(n2), 병목은 분치 FFT로 최적화할 수 있는 곳에 있다. 즉, 이 문제는 모델을 바꾸거나 아예 바꾸지 않고 더 큰 범위로 낼 수 있다는 것이다.

#include
using namespace std;

typedef long long ll;
const ll md=1e9+7;
const int N=5009;

int n,k,m;
ll a[N],b[N],c[N];

inline ll read()
{
    ll x=0;char ch=getchar();
    while(ch<'0' || '9'while('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getchar();
    return x;
}

inline ll qpow(ll a,ll b)
{
    ll ret=1;
    while(b)
    {
        if(b&1)ret=ret*a%md;
        a=a*a%md;b>>=1;
    }
    return ret;
}

inline int mult(ll *a,int n,ll *b,int m,ll *c)
{
    static ll d[N];
    memset(d,0,sizeof(d[0])*(n+m+5));
    for(int i=0;ifor(int j=0;jfor(int i=0;i1;i++)
        c[i]=d[i]%md;
    return n+m-1;
}

int main()
{
    n=read();k=read();
    for(int i=1;i<=n;i++)
        a[i]=read();

    c[0]=1;m=1;
    for(int i=1;i<=n;i++)
    {
        b[0]=a[i];b[1]=-1;
        m=mult(b,2,c,m,c);
    }

    ll ans=1,powk=1;
    ll invn=qpow(n,md-2),inv=1;
    for(int i=1;i<=n;i++)
        ans=ans*a[i]%md;
    for(int i=0;i<=n && i<=k;i++)
    {
        ans=(ans-c[i]*powk%md*inv%md+md)%md;
        powk=powk*(k-i)%md;inv=inv*invn%md;
    }

    printf("%I64d
",ans);
    return 0;
}