A. Joey Takes Money
题意：
给定 n 个整数，每次操作可以选择两个整数，获得两数之积，再构造一组 (x,y) 使得 x * y 等于两数之积，并将原来的数替换为 x, y ，求操作若干次后 n 个数的最大和。
分析：
考虑最终情况：只有一个 n 个数的乘积 k 与 n - 1 个 1 组成，sum = k + n - 1
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define x first
#define y second
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 200010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
typedef unordered_map<int, int> Ump;
int T;
int n;
int a[N];
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
int t = 1;
for (int i = 1; i <= n; i++)
{
t *= a[i];
}
cout << (t + n - 1) * 2022 << endl;
}
signed main()
{
FAST;
cin >> T;
while (T--)
solve();
return 0;
}
B. Kill Demodogs
题意：
在 n * n 的网格，每个格子上存在 行号 * 列号 个怪物，你从 (1, 1) 出发，只能向下和向右走，走到 (n, n) 一路上最多击杀多少怪物。
分析：
找规律即可发现：右/下交替走即可保证 sum 最大，下面处理如何求 sum ：
列出式子：$$0 * 1 + 1 * 1 + 1 * 2 + 2 * 2 + 3 * 2 + 3 * 3 + ...... + n * (n - 1) + n * n$$
即:
即：
\[2 * (1^2 + 2^2 + 3^2 + ...... + n^2 ) - (1 + 2 + 3 + 4 + ...... + n) \]即:
\[2 * \frac{n * (n + 1) * (2 * n + 1)}{6} - \frac{n*(n + 1)}{2} \]平方和
这里由于答案还要 ×2022 可以化简后直接运算或者求乘法逆元计算
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define x first
#define y second
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 200010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
typedef unordered_map<int, int> Ump;
int T;
int n;
int qmi(int a, int k, int p) // 求a^k mod p
{
int res = 1 % p;
while (k)
{
if (k & 1)
res = res * a % p;
a = a * a % p;
k >>= 1;
}
return res;
}
void solve()
{
cin >> n;
int res = n * (n + 1) % MOD * (2 * n + 1) % MOD * qmi(6, MOD - 2, MOD) % MOD;
res = 2 * res % MOD - (n + 1) * n % MOD * qmi(2, MOD - 2, MOD) % MOD;
res = (res % MOD + MOD) % MOD;
res = res * 2022 % MOD;
cout << res << endl;
}
signed main()
{
FAST;
cin >> T;
while (T--)
solve();
return 0;
}