Codeforces Round #209 (Div. 2) C - Prime Number - JavaScript

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

传送门

题意

给出n个数及x，求

\[\frac{\sum _{i=1}^n x^{a_1+a_2+...+a_{i-1}+a_{i+1}+...a_n}}{\prod_{i=1}^n x^{a_i}}
\]

分析

结果必然为$x^{sum}$,sum的值首先取所有数的和减去最大值

然后暴力合并，具体原因我不太懂，只能附上CF的标准题解

Obviously, the answer is $x^v$. Let $sum = a1 + a2 + ... + an$. Also let $si = sum - ai $(the array of degrees). After that let's find value $v$ by the following algorithm: Let's consider a sequence of degrees as decreasing sequence. Now we will perform the following operation until it's possible to perfom it. Take the minimum degree $v$ from the array of degrees and calculate the number of elements $cnt$, which have the same degree. If $cnt$ multiples of $x$, then replace all $cnt$ elements by $cnt / x$ elements of the form $v + 1$. Since the sequence of degrees is a decreasing sequence, we can simply assign them to the end. If $cnt$ is not a multiple of $x$, then we found the required value $v$. Also you need to check, that $v$ is not greater then sum. Otherwise, $v$ will be equals to sum.

详情见代码

代码

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <string>

#include <map>

#include <queue>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

#pragma comment(linker, "/STACK:102400000,102400000")

inline void read(int &x){x=0; char ch=getchar();while(ch<'0') ch=getchar();while(ch>='0'){x=x*10+ch-48; ch=getchar();}}

const ll mod=1e9+7;

int n,x,a[100100],num,t;

ll sum,cnt;

bool vis[100100];

ll mi(int x,ll cnt)

{

    ll ret=x,ans=1;

    while(cnt)

    {

        if(cnt&1) ans=(ans*ret)%mod;

        cnt>>=1,(ret*=ret)%=mod;

    }

    return ans;

}

int main()

{

    scanf("%d %d",&n,&x);

    F(i,1,n){ scanf("%d",a+i);sum+=(ll)a[i]; }

    sum-=a[n];t=a[n];

    num=0;

    F(i,1,n)

    {

        if(a[i]==a[n]) { num++;vis[i]=1; }

        a[i]=a[n]-a[i];

    }

    while(num%x==0&&t)

    {

            sum++;num/=x;t--;

            F(i,1,n) if(!vis[i])

            {

                a[i]--;

                if(a[i]==0) {num++;vis[i]=1;}

            }

        if(num==0) break;

    }

    //printf("%d\n",sum);

    printf("%lld\n",mi(x,sum));

    return 0;

}