神仙 dp
测试点 1,2
暴力之。
A性质
A性质说的是全部的 \(a\) 都是 \(1\)，发现一个性质就是一定就是两个 \(1\) 之间一定相邻偶数个 \(0\)，直接大力 dp 就做完了。
测试点 3-12 的第一问
我们思考一个事情就是最后有数的位置一定是从左右两边一直操作到一个点，然后还是考虑大力 dp，同时预处理两个东西分别表示从 \(l\) 一直操作到 \(r\) 最后的数，和从 \(r\) 操作的 \(l\) 最后剩下的数，然后 dp 状态还是前 \(i\) 个最大的数，然后我们思考怎么转移，发现直接枚举右端点和中间集合的点，然后直接看能不能操作过来，然后就做完了。
拼上之前的可以有 \(38\) 分，link。
B性质的第二问
我们发现这个东西为什么过不去第二问呢？
因为可以能会有很多一段操作完是相同的，而数据随机生成我们可以认为不会有这种情况，所以写一个类似的转移，并且稍加减枝，预处理出来肯定转移不到的位置，然后减掉就行了。
拼上之前的可以有 \(63\) 分，link。
全部的第一问
我们发现一个事情，就是对于可以转移到的区间，他一定是奇数的加/减，偶数的减/加，然后发现这个和的绝对值是固定的，于是相当于有三种情况：
-
和为零：只能从中间转移来，相当于全是 \(0\)。
-
奇数的和大：只能从奇数位置转移来，选那个 \(b_i\) 最小的就行了。
-
偶数的和大：同上。
然后就可以过全部的第一问。
正解
我们还是思考为什么过不去，我们发现可能会出现前面的 \(0\) 跟后面的 \(0\) 合并上了，于是我们钦定操作过程中不能有 \(0\)，然后反向操作遇到第一个 \(0\) 停下就行了。
点击查看代码
//これも運命じゃないか
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define double long double
#define uint unsigned long long
#define Air
namespace io{inline int read(){int f = 1, t = 0; char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}while(ch >= '0' && ch <= '9'){t = t * 10 + ch - '0'; ch = getchar();}return t * f;}inline void write(int x){if(x < 0){putchar('-'); x = -x;}if(x >= 10){write(x / 10);}putchar(x % 10 + '0');}
}
using namespace io;
int n;
int ICS;
const int N = 5010, MOD = 1e9 + 7;
int a[N], b[N], c[N];
ll quick_pow(ll a, int b){if(!b) return 1;if(b & 1){return a * quick_pow(a, b - 1) % MOD;}else{ll tmp = quick_pow(a, b / 2);return tmp * tmp % MOD;}
}
namespace Sub1{map<vector<int>, bool>mp;ll ta, tb;void dfs(vector<int> x){if(mp[x]) return ;mp[x] = 1;ll vala = 0, valb = 1;for(int i = 1; i <= n; i++){if(x[i] == 0){vala += b[i];valb *= c[i];valb %= MOD;}}ta = max(ta, vala);tb += valb; tb %= MOD;for(int i = 1; i < n; i++){vector<int> tmp;tmp = x;if(tmp[i] <= tmp[i + 1]){tmp[i + 1] -= tmp[i];tmp[i] = 0;dfs(tmp);tmp = x;}if(tmp[i + 1] <= tmp[i]){tmp[i] -= tmp[i + 1];tmp[i + 1] = 0;dfs(tmp);tmp = x;}}}void solve(){mp.clear();ta = -1e18;tb = 0;vector<int> bg;bg.clear();bg.push_back(-1);for(int i = 1; i <= n; i++){bg.push_back(a[i]);}// cerr << "\n";dfs(bg);cout << ta << ' ' << tb << '\n';}
}
namespace SubA{ll f[N];ll g[N];ll pre[N], mul[N];ll inv[N];void solve(){g[0] = 1;f[0] = 0;for(int i = 1; i <= n; i++){pre[i] = pre[i - 1] + b[i];}mul[0] = 1;inv[0] = 1;for(int i = 1; i <= n; i++){mul[i] = mul[i - 1] * c[i] % MOD;inv[i] = quick_pow(mul[i], MOD - 2);}pre[n + 1] = pre[n];mul[n + 1] = mul[n];inv[n + 1] = inv[n];for(int i = 1; i <= n + 1; i++){f[i] = -1e18;g[i] = 0;for(int j = i - 1; j >= 0; j -= 2){f[i] = max(f[i], f[j] + pre[i - 1] - pre[j]);g[i] += g[j] * mul[i - 1] % MOD * inv[j] % MOD;g[i] %= MOD;}}cout << f[n + 1] << ' ' << g[n + 1] << '\n';}
}
namespace Sub2_P1{ll dp[N];ll gt[N];ll pre[N][N];ll suf[N][N];int tpre[N], tsuf[N];ll sum[N];ll mul[N], inv[N];// int iiv[N];ll piv[N];int minn[2][N][N];ll vala[2][N][N];int valc[2][N][N];bool fpre[N][N];bool fsuf[N][N];void solve(){for(int len = 1; len <= n; len ++){for(int l = 1; l + len - 1 <= n; l++){int r = l + len - 1;fpre[l][r] = fsuf[l][r] = 1;if(a[r] >= pre[l][r - 1] && (!fpre[l][r - 1])){pre[l][r] = a[r] - pre[l][r - 1];fpre[l][r] = 0;}if(a[l] >= suf[l + 1][r] && (!fsuf[l + 1][r])){suf[l][r] = a[l] - suf[l + 1][r];fsuf[l][r] = 0;}}}// cerr << fpre[1][4] << ' ' << fsuf[6][8] << '\n';sum[0] = 0;for(int i = 1; i <= n; i++){int j = i;while(j < n && !fpre[i][j + 1] && pre[i][j + 1]) j++;tpre[i] = j;j = i;while(j > 1 && !fsuf[j - 1][i] && suf[j][i]) j--;tsuf[i] = j;// cout << tpre[i] << ' ' << tsuf[i] << '\n';sum[i] = sum[i - 1] + b[i];}sum[n + 1] = sum[n];mul[0] = 1;inv[0] = 1;for(int i = 1; i <= n; i++){mul[i] = mul[i - 1] * c[i] % MOD;piv[i] = quick_pow(c[i], MOD - 2);inv[i] = quick_pow(mul[i], MOD - 2);}for(int i = 1; i <= n; i++){minn[0][i][i] = b[i];minn[1][i][i] = 1e9;vala[0][i][i] = a[i];vala[1][i][i] = 0;valc[0][i][i] = piv[i];valc[1][i][i] = 0;for(int j = i + 1; j <= n; j++){minn[0][i][j] = minn[0][i][j - 1];minn[1][i][j] = minn[1][i][j - 1];vala[0][i][j] = vala[0][i][j - 1];vala[1][i][j] = vala[1][i][j - 1];valc[0][i][j] = valc[0][i][j - 1];valc[1][i][j] = valc[1][i][j - 1];int op = ((j - i) & 1);minn[op][i][j] = min(minn[op][i][j], b[j]);vala[op][i][j] += a[j];valc[op][i][j] += piv[j];valc[op][i][j] %= MOD;}}dp[0] = 0;gt[0] = 1;for(int j = 1; j <= n; j++){dp[j] = -1e18;gt[j] = 0;}for(int i = 0; i <= n; i++){for(int j = i + 1; j <= n; j++){int tr = min(tpre[i + 1], j), tl = max(tsuf[j], i + 1);if(tl > tr) continue;ll val0 = vala[0][i + 1][j], val1 = vala[1][i + 1][j];bool flag = ((tl & 1) == (i & 1));if(val0 == val1){gt[j] += gt[i] * mul[j] % MOD * inv[i] % MOD;gt[j] %= MOD;dp[j] = max(dp[j], dp[i] + sum[j] - sum[i]);continue;}if(val0 > val1){gt[j] += gt[i] * mul[j] % MOD * inv[i] % MOD * valc[flag][tl][tr] % MOD;gt[j] %= MOD;dp[j] = max(dp[j], dp[i] + sum[j] - sum[i] - minn[flag][tl][tr]);}else{gt[j] += gt[i] * mul[j] % MOD * inv[i] % MOD * valc[flag ^ 1][tl][tr] % MOD;gt[j] %= MOD;dp[j] = max(dp[j], dp[i] + sum[j] - sum[i] - minn[flag ^ 1][tl][tr]);}// for(int k = tl; k <= tr; k++){// // if(fpre[i + 1][k - 1] || fsuf[k + 1][j]) continue;// int val1 = pre[i + 1][k - 1], val2 = suf[k + 1][j];// if(val1 + val2 > a[k]) continue;// // cerr << k << ' ';// if(a[k] == val1 + val2){// // if(ICS >= 8 && ICS <= 10)// // assert(0);// gt[j] += gt[i] * mul[j] % MOD * inv[i] % MOD;// gt[j] %= MOD;// dp[j] = max(dp[j], dp[i] + sum[j] - sum[i]);// break;// }// else{// gt[j] += gt[i] * mul[j] % MOD * inv[i] % MOD * piv[k] % MOD;// gt[j] %= MOD;// dp[j] = max(dp[j], dp[i] + sum[j] - sum[i] - b[k]);// }// }// // if(tl <= tr)// cerr << '\n';}}cout << dp[n] << ' ' << gt[n] << '\n';}
}
void work(){n = read();// n = 8;for(int i = 1; i <= n; i++){a[i] = read();// a[i] = rand() % 10;}for(int i = 1; i <= n; i++){b[i] = read();// b[i] = rand() % 10;}for(int i = 1; i <= n; i++){c[i] = read();// c[i] = rand() % 10;}if(ICS <= 2){Sub1::solve();return ;}if(ICS == 7 || ICS == 13){SubA::solve();return ;}if(ICS <= 20){Sub2_P1::solve();return ;}
}
signed main() {
#ifndef Airfreopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);
#endifios::sync_with_stdio(false);cin.tie(0);cout.tie(0);ICS = read();// ICS = 8;int TCS;TCS = read();// TCS = 100;while(TCS --){work();}return 0;
}