比赛链接

2022 China Collegiate Programming Contest (CCPC) Guilin Site

C. Array Concatenation

给定一个长度为 \(n\) 的数组 \(b_i\)，有两种操作变换：

• \(b^{\prime}=\left\{b_1, b_2, \ldots, b_{|b|}, b_1, b_2, \ldots, b_{|b|}\right\}\)
• \(b^{\prime}=\left\{b_{|b|}, b_{|b-1|}, \ldots, b_1, b_1, b_2, \ldots, b_{|b|}\right\}\)

问 \(m\) 次操作后数组的所有前缀的和模 \(10^9+7\) 后的最大值

解题思路

思维

假设长度为 \(n\) 的数组，其和为 \(s\)，所有前缀和为 \(ss\)，所有后缀和为 \(sss\)
可以发现：当有操作 \(2\) 时，当前数组会变成回文数组，后面无论哪一种操作都不影响结果，且只要有操作 \(2\)，其结果都一定，操作 \(m\) 次，最终结果为 \(2^{m-1}\times (ss+sss)+\frac{2^m\times (2^m-1)}{2}\times n\times s\)，只有第一种操作的最终结果为 \(2^{m}\times ss+\frac{2^m\times (2^m-1)}{2}\times n\times s\)，两种结果取 max 即为答案
另外，这里很容易爆 long long，直接 __int128 了

• 时间复杂度：\(O(logm)\)

代码

// Problem: C. Array Concatenation
// Contest: Codeforces - 2022 China Collegiate Programming Contest (CCPC) Guilin Site
// URL: https://codeforces.com/gym/104008/problem/C
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
// #define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=1e5+5,mod=1e9+7;
__int128 n,m,a[N];
int ksm(int a,int b,int p)
{
	int res=1%p;
	while(b)
	{
		if(b&1)res=(LL)res*a%p;
		a=(LL)a*a%p;
		b>>=1;
	}
	return res;
}
int main()
{
    read(n),read(m);
    __int128 s=0,ss=0,sss=0;
    for(int i=1;i<=n;i++)
    {
    	read(a[i]);
    	s+=a[i];
    	ss=(ss+(LL)(n-i+1)*a[i]%mod)%mod;
    	sss=(sss+(LL)i*a[i]%mod)%mod;
    }
    int res[2];
    res[0]=((LL)ss*ksm(2,m,mod)%mod+(LL)ksm(2,m,mod)*(ksm(2,m,mod)-1)/2%mod*n%mod*s%mod)%mod;
    res[1]=((LL)ss*ksm(2,m-1,mod)%mod+(LL)sss*ksm(2,m-1,mod)%mod+(LL)ksm(2,m,mod)*(ksm(2,m,mod)-1)/2%mod*n%mod*s%mod)%mod;
    cout<<max(res[0],res[1]);
    return 0;
}