恶心的题目

P10791 『SpOI - R1』强大到让你们所有人注视

code

#include <bits/stdc++.h>
using namespace std;
using llt=long long;
const llt mod=20070720ll;
llt t,n,k,a[500001],ans=0ll,p[500001],q[500001];
int main()
{
	scanf("%lld",&t);
	while(t--)
	{
		ans=0ll;
		memset(p,0,sizeof(p));
		memset(q,0,sizeof(q));
		p[1]=1ll;
		scanf("%lld%lld",&n,&k);
		for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
		for(int i=2;i<=max(30ll,n);i++) p[i]=(p[i-1]*(k%mod))%mod;
		for(int i=1;i<=n;i++) q[i]=(q[i-1]+p[i])%mod;
		for(int i=1;i<=n;i++) ans=(ans+((((a[i]%mod)*q[n-i+1])%mod)*i)%mod)%mod;
		if(k>mod) printf("%lld\n",ans);
		else
		{
			int pos;
			for(int i=2,tmp=1;i<=max(30ll,n);i++)
			{
				if(ans<p[i]||p[i]<=tmp)
				{
					pos=i-1;
					break;
				}
				tmp=p[i];
			}
			for(int i=pos;i>=1;i--)
			{
				printf("%lld ",ans/p[i]);
				ans%=p[i];
			}
			printf("\n");
		}
	}
	return 0;
}