在 2022 年的最后一天，和大神 stO Jerry__Jiang Orz 开了一场 CodeForces 的 vp，顺便来水一下博客。

前言：前两题的输出为 actual answer \(\times 2022\)

CodeForces Round #841 (Div. 2) vp记

Problem A

这道题没啥难度吧，由小学知识“积一定，差越大，和越大”可以推出，我们将其它数都变为 1，就是最优决策。

#include<bits/stdc++.h>
#define int long long
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define FOR(i,r,l) for(int (i)=r;(i)>=l;(i)--)
#define INF 0x3f3f3f
#define pii pair<int,int>
#define mpr make_pair
#define pb push_back
#define ALL(v) (v).begin(),(v).end()
#define rsort(v) sort(ALL(v),greater<int>())
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
void out(int x){if(x<0){x=-x;putchar('-');}if(x>=10)out(x/10);putchar(x%10+'0');}
template <typename T>void die(T s){cout<<s<<endl;exit(0);}
int fast(int a,int b,int P){int res=1;if(P<=0){while(b){if(b&1)res=res*a;a=a*a;b>>=1;}}else{while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}}return res;}
template <typename T>void chkmax(T& a,T b){if(a<b)a=b;return;}
template <typename T>void chkmin(T& a,T b){if(a>b)a=b;return;}
int T,a[55],n,res;
void solve(){
	res=1;n=read();
	rep(i,n)a[i]=read(),res=res*a[i];
	cout<<(res+n-1)*2022<<endl;
	return;
}
signed main(){
	T=read();
	while(T--)solve();
	return 0;
}

Problem B

这道题有一小点难度，具体结论我们可以感性证明一下：

我们可以假设现在我们在坐标 \((i,j)\) ，并且从 \((1,1)\) 到 \((i,j)\) 都采取了最优策略，我们思考下一步往哪边走更优

• 若 \(i \operatorname{<} j\) ，不难看出，此时我们向下走是更优的
• 若 \(i \operatorname{>} j\) ，此时向右走更优
• 最后一种情况 \(i \operatorname{=} j\) ，两者皆可

随后我们就可以想出 \((1,1)\rightarrow(1,2)\rightarrow(2,2)\dots\rightarrow(n,n)\) 是最优方案。

答案即为 $$\sum_{i=1}^{n} i^2 + \sum_{i=1}^{n-1} i^2 + \sum_{i=1}^{n-1} i$$

#include<bits/stdc++.h>
#define int long long
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define FOR(i,r,l) for(int (i)=r;(i)>=l;(i)--)
#define INF 0x3f3f3f
#define pii pair<int,int>
#define mpr make_pair
#define pb push_back
#define ALL(v) (v).begin(),(v).end()
#define rsort(v) sort(ALL(v),greater<int>())
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
void out(int x){if(x<0){x=-x;putchar('-');}if(x>=10)out(x/10);putchar(x%10+'0');}
template <typename T>void die(T s){cout<<s<<endl;exit(0);}
int fast(int a,int b,int P){int res=1;if(P<=0){while(b){if(b&1)res=res*a;a=a*a;b>>=1;}}else{while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}}return res;}
template <typename T>void chkmax(T& a,T b){if(a<b)a=b;return;}
template <typename T>void chkmin(T& a,T b){if(a>b)a=b;return;}
const int P=1e9+7;
int n,T;
int Sum(int x){
	return x*(x+1)%P*(2*x+1)%P*fast(6,P-2,P)%P;
}
void solve(){
	n=read();
	int ans=Sum(n)+Sum(n-1);
	ans=ans%P;
	ans=ans+(n-1)*n%P*fast(2,P-2,P)%P;
	ans=ans%P;
	cout<<ans*2022%P<<endl;
	return;
}
signed main(){
	T=read();
	while(T--)solve();
	return 0;
}