一两眼题（oneortwo）

题目描述

给出n个整数，依次为a1,a2,...an。n<=50000.

你要进行K次操作,0 <= k < =1,414,213,562

每次操作你算出sum=a1+a2+a3+...an，再将每个数替换为sum-ai.

求最后一次操作后a1,a2,....an的值

输入

第一行两个整数n,k

接下来n行每行一个整数ai.

输出

输出n行。依次为k次操作后的a1,a2....an。模 98,765,431

样例输入

样例输出

提示

40%的数据满足n<=20,k<=2000

solution

通过手模发现

对于第i轮操作

$Sumi=sum*(n-1)^i$

$Ai=sum*(n-1)^i-sum(n-1)^{i-1}+sum*(n-1)^{i-2}+---(\pm a)$

正负由i的奇偶性决定

等比数列求和一下，就是快速幂了

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#define maxn 50005

#define mod 98765431

using namespace std;

int n;

long long s[maxn],sum;

long long k;

long long lian(long long k,long long num)

{

    long long ans=1,p=k;

    while(num>0){

        if(num&1)ans=ans*p;

        p=p*p;p%=mod;ans%=mod;num>>=1;

    }

    return ans;

}

int main()

{

    freopen("oneortwo.in","r",stdin);

    freopen("oneortwo.out","w",stdout);

    cin>>n>>k;

    for(int i=1;i<=n;i++){

        scanf("%lld",&s[i]);

        sum+=s[i];sum%=mod;

    }

    long long ny=lian(n,mod-2);

    long long a=n-1;

    long long tmp=lian(a,k);

    if(k&1)tmp++;else tmp--;

    long long ans=tmp*ny;ans%=mod;

    ans=ans*sum;ans%=mod;

    int op;

    if(k&1)op=-1;else op=1;

    for(int i=1;i<=n;i++){

        long long t=ans+s[i]*op;

        t=(t%mod+mod)%mod;

        printf("%lld\n",t);

    }

    return 0;

}

巴特西

一两眼题（oneortwo）

一两眼题（oneortwo）

题目描述

输入

输出

样例输入

样例输出

提示

最新文章

热门文章