想趁着大家都有空的时间多练几场，队友上来就挑了一场ec-final，只能说与我的水平不太符合
尽力补题中。
I Misunderstood … Missing
挺有意思的签到题，一个人还没想出来。
因为前面的状态会对后面的状态产生影响，后面的状态不会对前面的决策产生影响，所以倒着dp。
考虑将答案组成的形式拆开，设(f(i, j))表示第(i)轮结束之后后面还要攻击(j)轮的答案，如果我们进行一个攻击力(+b_i)的操作，后面会有(jb_i)的贡献；如果我们进行一次攻击，后面会有(a_i)的贡献。
最后考虑这个加差值的操作，如果后面是在(x_{p_1}, x_{p_2}, cdots, x_{p_j})的位置攻击，贡献为(sum (x_{p_k} - i) = sum x - j * i)。于是再增加一维，设(f(i, j, k))表示第(i)轮结束之后，后面攻击了(j)次，后面攻击的回合数标号之和为(k)的最大伤害。枚举状态需要(O(n^4))，转移(O(1))。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair <int, int> pin;
#ifndef ONLINE_JUDGE
bool MEMORY_ST;
#endif
const int N = 105;
const int M = 5050 + 5;
const ll P = 998244353LL;
int T, n;
ll a[N], b[N], c[N], f[2][N][M];
namespace Fread {
const int L = 1 << 15;
char buffer[L], *S, *T;
inline char Getchar() {
if(S == T) {
T = (S = buffer) + fread(buffer, 1, L, stdin);
if(S == T) return EOF;
}
return *S++;
}
template <class T>
inline void read(T &X) {
char ch; T op = 1;
for(ch = Getchar(); ch > '9' || ch < '0'; ch = Getchar())
if(ch == '-') op = -1;
for(X = 0; ch >= '0' && ch <= '9'; ch = Getchar())
X = (X << 1) + (X << 3) + ch - '0';
X *= op;
}
} using Fread::read;
inline void chkMax(ll &x, ll y) {
if (y > x) x = y;
}
#ifndef ONLINE_JUDGE
bool MEMORY_ED;
#endif
int main() {
#ifndef ONLINE_JUDGE
freopen("sample.in", "r", stdin);
clock_t st_clock = clock();
#endif
read(T);
for (; T--; ) {
read(n);
for (int i = 1; i <= n; i++) read(a[i]), read(b[i]), read(c[i]);
int sum = (n + 1) * n / 2;
for (int i = 0; i < 2; i++)
for (int j = 0; j <= n; j++)
for (int k = 0; k <= sum; k++)
f[i][j][k] = -1;
f[n & 1][0][0] = 0;
for (int i = n; i >= 1; i--) {
int cur = i & 1, suc = cur ^ 1;
for (int j = 0; j <= n; j++)
for (int k = 0; k <= sum; k++)
f[suc][j][k] = -1;
for (int j = 0; i + j <= n; j++) {
for (int k = 0; k <= sum; k++) {
if (f[cur][j][k] == -1) continue;
chkMax(f[suc][j + 1][k + i], f[cur][j][k] + a[i]);
chkMax(f[suc][j][k], f[cur][j][k] + b[i] * (k - i * j));
chkMax(f[suc][j][k], f[cur][j][k] + c[i] * j);
}
}
}
ll ans = 0;
for (int j = 0; j <= n; j++)
for (int k = 0; k <= sum; k++)
ans = max(ans, f[0][j][k]);
printf("%lld
", ans);
}
#ifndef ONLINE_JUDGE
clock_t ed_clock = clock();
printf("time = %f ms
", (double)(ed_clock - st_clock) / CLOCKS_PER_SEC * 1000);
printf("memory = %.2f MB
", (&MEMORY_ED - &MEMORY_ST) / 1024.0 / 1024.0);
#endif
return 0;
}
jls说这就是slay the spire的力量战，恶魔形态是不是太拉了一点……
C Heretical … Möbius
很好玩的题，感觉那个年代的人都很喜欢出这种风格的题目。
题目中的(|mu(n)|)只跟(n)是否含有平方因子有关，我们不妨考虑一个最小的完全平方数(4)，那么(4)的倍数所在的位置一定是(0)，据此我们可以进行可行性检验，先枚举(ans mod 4)的位置，然后看看这些位数是不是都是(0)。
如果某个余数(r)可行，那么相当于我们得到了一个可选的同余方程：
[ans equiv -r mod p
]
为什么是可选的？因为对于模数(4)我们可能可以找到多个位置可行。
同理，考虑(200)以内的质数的平方，可以用的有(6)个(4, 9, 25, 49, 121, 169)，分别检验出可行的余数，然后我们考虑枚举一下这些余数，根据中国剩余定理，我们可以合并出一个在([0, 901800900))的满足条件的数(x)，然后我们考虑检验这个(x)和(x + 901800900)是否可以作为答案。
怎么检验呢？枚举([1, sqrt{10^9}])以内的质数，用这些质数暴力地去这个区间里面分解质因子，一次检验的时间为(O(frac{sqrt{Maxn}}{log Maxn} + 200 log n))，后面那个大概是一个区间内因子总数。
卡时出解即可。
对于做题的人来说，工作到这里已经结束了；但是对于出题人来说，还需要保证自己造出来的数据是正确的，也不知道jls是怎么完成这项工作的，好在这个(10^9)也不是很大。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair <int, int> pin;
#ifndef ONLINE_JUDGE
bool MEMORY_ST;
#endif
const int N = 205;
const int M = 35005;
const int Maxm = 35000;
const int P[] = {4, 9, 25, 49, 121, 169};
const int inf = 1e9;
int ans = inf + 5, a[N], pcnt, pri[M];
bool vis[M], returnFlag = 0;
char s[N];
vector <int> vec[6], rest;
clock_t stClock;
inline void sieve() {
for (int i = 2; i <= Maxm; i++) {
if (!vis[i]) {
pri[++pcnt] = i;
}
for (int j = 1; j <= pcnt && i * pri[j] <= Maxm; j++) {
vis[i * pri[j]] = 1;
if (i % pri[j] == 0) break;
}
}
}
inline bool chk(int p, int len) {
for (int i = p; i < 200; i += len)
if (a[i] != 0)
return 0;
return 1;
}
ll exgcd(ll ca, ll cb, ll &x, ll &y) {
if (!cb) {
x = 1, y = 0;
return ca;
}
ll d = exgcd(cb, ca % cb, y, x);
y -= ca / cb * x;
return d;
}
inline int mergeCrt() {
ll prod = 1, res = 0;
for (int i = 0; i < 6; i++) prod = prod * (1LL * P[i]);
// printf("%lld
", prod);
for (int i = 0; i < 6; i++) {
ll t = prod / P[i], it, y;
exgcd(t, P[i], it, y);
res = (res + 1LL * rest[i] * t % prod * it % prod) % prod;
}
return (res % prod + prod) % prod;
}
inline bool chkAns(int cur) {
if (cur == 0) return 0;
vector <int> b(200), c(200);
for (int i = 0; i < 200; i++) {
b[i] = cur + i;
c[i] = 1;
}
for (int i = 1; i <= pcnt; i++) {
int cp = pri[i];
int st = (cur + cp - 1) / cp * cp;
if (st - cur > 199) continue;
for (int j = st; j < cur + 200; j += cp) {
assert(b[j - cur] % cp == 0);
int cnt = 0;
for (; b[j - cur] % cp == 0; b[j - cur] /= cp, ++cnt);
if (cnt >= 2) c[j - cur] = 0;
}
}
for (int i = 0; i < 200; i++)
if (c[i] != a[i])
return 0;
return 1;
}
inline void up() {
int cur = mergeCrt();
// assert(cur >= 1);
if (cur + 200 - 1 > inf) return;
if (chkAns(cur)) ans = min(ans, cur);
if (1LL * cur + 901800900LL + 200 - 1 > inf) return;
cur += 901800900;
if (chkAns(cur)) ans = min(ans, cur);
}
void dfs(int p) {
if (returnFlag) return;
clock_t curClock = clock();
if ((db) (curClock - stClock) > 0.9 * CLOCKS_PER_SEC) {
returnFlag = 1;
return;
}
if (p == 6) {
up();
return;
}
if (vec[p].empty()) return;
for (int i = 0; i < vec[p].size(); i++) {
rest.emplace_back(vec[p][i]);
dfs(p + 1);
rest.pop_back();
}
}
#ifndef ONLINE_JUDGE
bool MEMORY_ED;
#endif
int main() {
#ifndef ONLINE_JUDGE
freopen("sample.in", "r", stdin);
clock_t st_clock = clock();
#endif
stClock = clock();
sieve();
// for (int i = 1; i <= 20; i++)
// printf("%d
", pri[i]);
int cnt = 0;
for (int i = 1; i <= 10; i++) {
scanf("%s", s);
for (int j = 0; j < 20; j++) a[cnt++] = s[j] - '0';
}
for (int i = 0; i < 6; i++) {
for (int j = 0; j < P[i]; j++) {
if (chk(j, P[i])) {
vec[i].emplace_back((P[i] - j) % P[i]);
}
}
}
dfs(0);
printf("%d
", ans == inf + 5 ? -1 : ans);
#ifndef ONLINE_JUDGE
clock_t ed_clock = clock();
printf("time = %f ms
", (double)(ed_clock - st_clock) / CLOCKS_PER_SEC * 1000);
printf("memory = %.2f MB
", (&MEMORY_ED - &MEMORY_ST) / 1024.0 / 1024.0);
#endif
return 0;
}