问题标题: @余天泽

WOC,什么东东

PS:这验证码...

• #include <bits/stdc++.h> #define rep(i, a, b) for (int i = (a); i <= int(b); i++) #define per(i, a, b) for (int i = (a); i >= int(b); i--) using namespace std; typedef long long ll; const int maxn = 5e5, mod = 1e9 + 7; int n, k, w[10], c[maxn + 5], d[maxn + 5], dt[10], res, S[11][11], inv[12]; struct foo { int z[10], l[10], r[10]; void reset() { memset(z, 0, k << 2); memset(l, 0, k << 2); memset(r, 0, k << 2); } foo() { reset(); } int walk(int c, int d) { z[c] += d; if (z[c] < l[c] || z[c] > r[c]) { l[c] = min(l[c], z[c]); r[c] = max(r[c], z[c]); return d; } return 0; } } F, B; inline void red(int &x) { x += x >> 31 & mod; } void prework(int n) { S[0][0] = 1; rep(i, 1, n) rep(j, 1, i) { S[i][j] = (S[i - 1][j - 1] + ll(S[i - 1][j]) * j) % mod; } inv[1] = 1; rep(i, 2, n + 1) { inv[i] = ll(mod - mod / i) * inv[mod % i] % mod; } } int calc(int k, int n) { int s = 0, c = 1; rep(i, 0, k) { c = ll(c) * max(0, n - i) % mod; s = (s + ll(c) * inv[i + 1] % mod * S[k][i]) % mod; } return s; } int work(int a[]) { int lim = mod; rep(i, 0, k - 1) if (dt[i]) { lim = min(lim, (a[i] + dt[i] - 1) / dt[i]); } int dp[11] = { 1 }; rep(i, 0, k - 1) { per(j, i, 0) { dp[j + 1] = (dp[j + 1] + ll(mod - dt[i]) * dp[j]) % mod; dp[j] = ll(a[i]) * dp[j] % mod; } } int res = 0; rep(i, 0, k) { res = (res + ll(dp[i]) * calc(i, lim)) % mod; } return res; } int main() { // freopen("walk.in", "r", stdin); // freopen("walk.out", "w", stdout); scanf("%d %d", &n, &k); prework(k); rep(i, 0, k - 1) { scanf("%d", &w[i]); } rep(i, 1, n) { scanf("%d %d", &c[i], &d[i]), c[i]--; if (F.walk(c[i], d[i]) && F.r[c[i]] - F.l[c[i]] <= w[c[i]]) { int x = 1; rep(j, 0, k - 1) if (j != c[i]) { x = ll(x) * max(0, w[j] - F.r[j] + F.l[j]) % mod; } res = (res + ll(i) * x) % mod; } } rep(i, 1, n) if (F.z[c[i]] < 0) { d[i] = -d[i]; } rep(i, 0, k - 1) if (F.z[i] < 0) { F.z[i] = -F.z[i]; swap(F.l[i], F.r[i]); F.l[i] = -F.l[i]; F.r[i] = -F.r[i]; } B = F; bool chk = true; rep(i, 0, k - 1) { dt[i] = B.z[i]; chk &= dt[i] == 0; } if (chk) { bool ok = false; rep(i, 0, k - 1) { ok |= B.r[i] - B.l[i] >= w[i]; } printf("%d\n", ok ? res : -1); exit(0); } int a[10] = {}; rep(i, 1, n) { if (F.walk(c[i], d[i]) && F.r[c[i]] - F.l[c[i]] <= w[c[i]]) { bool ok = true; rep(j, 0, k - 1) if (j != c[i]) { ok &= w[j] - F.r[j] + F.l[j] > 0; } if (!ok) { continue; } rep(j, 0, k - 1) if (j != c[i]) { a[j] = w[j] - F.r[j] + F.l[j]; } a[c[i]] = w[c[i]] - F.r[c[i]] + F.l[c[i]] + 1, res = (res + ll(i) * work(a)) % mod; a[c[i]] = w[c[i]] - F.r[c[i]] + F.l[c[i]], res = (res + ll(mod - i) * work(a)) % mod; } } rep(i, 0, k - 1) { a[i] = max(0, w[i] - B.r[i] + B.l[i]); } res = (res + ll(n) * work(a)) % mod; printf("%d\n", res); return 0; }

https://blog.csdn.net/e12435/article/details/123939083?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522169935201416800192241303%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=169935201416800192241303&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-1-123939083-null-null.142^v96^pc_search_result_base9&utm_term=7169%E5%BE%AE%E4%BF%A1%E6%AD%A5%E6%95%B0%EF%BC%88walk%EF%BC%89&spm=1018.2226.3001.4187

https://blog.csdn.net/haker12345/article/details/129695537?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522169935201416800192241303%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=169935201416800192241303&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-2-129695537-null-null.142^v96^pc_search_result_base9&utm_term=7169%E5%BE%AE%E4%BF%A1%E6%AD%A5%E6%95%B0%EF%BC%88walk%EF%BC%89&spm=1018.2226.3001.4187

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= int(b); i++)
#define per(i, a, b) for (int i = (a); i >= int(b); i--)
 using namespace std;

 typedef long long ll;
 const int maxn = 5e5, mod = 1e9 + 7;

 int n, k, w[10], c[maxn + 5], d[maxn + 5], dt[10], res, S[11][11], inv[12];

 struct foo {
 int z[10], l[10], r[10];
 void reset() {
 memset(z, 0, k << 2);
 memset(l, 0, k << 2);
 memset(r, 0, k << 2);
 }
 foo() {
 reset();
 }
 int walk(int c, int d) {
 z[c] += d;
 if (z[c] < l[c] || z[c] > r[c]) {
 l[c] = min(l[c], z[c]);
 r[c] = max(r[c], z[c]);
 return d;
 }
 return 0;
 }
 } F, B;

 inline void red(int &x) {
 x += x >> 31 & mod;
 }

 void prework(int n) {
 S[0][0] = 1;
 rep(i, 1, n) rep(j, 1, i) {
 S[i][j] = (S[i - 1][j - 1] + ll(S[i - 1][j]) * j) % mod;
 }
 inv[1] = 1;
 rep(i, 2, n + 1) {
 inv[i] = ll(mod - mod / i) * inv[mod % i] % mod;
 }
 }

 int calc(int k, int n) { int s = 0, c = 1;
 rep(i, 0, k) {
 c = ll(c) * max(0, n - i) % mod;
 s = (s + ll(c) * inv[i + 1] % mod * S[k][i]) % mod;
 }
 return s;
 }

 int work(int a[]) {
 int lim = mod;
 rep(i, 0, k - 1) if (dt[i]) {
 lim = min(lim, (a[i] + dt[i] - 1) / dt[i]);
 }
 int dp[11] = { 1 };
 rep(i, 0, k - 1) {
 per(j, i, 0) {
 dp[j + 1] = (dp[j + 1] + ll(mod - dt[i]) * dp[j]) % mod;
 dp[j] = ll(a[i]) * dp[j] % mod;
 }
 }
 int res = 0;
 rep(i, 0, k) {
 res = (res + ll(dp[i]) * calc(i, lim)) % mod;
 }
 return res;
 }

 int main() {
 // freopen("walk.in", "r", stdin);
 // freopen("walk.out", "w", stdout);
 scanf("%d %d", &n, &k);
 prework(k);
 rep(i, 0, k - 1) {
 scanf("%d", &w[i]);
 }
 rep(i, 1, n) {
 scanf("%d %d", &c[i], &d[i]), c[i]--;
 if (F.walk(c[i], d[i]) && F.r[c[i]] - F.l[c[i]] <= w[c[i]]) {
 int x = 1;
 rep(j, 0, k - 1) if (j != c[i]) {
 x = ll(x) * max(0, w[j] - F.r[j] + F.l[j]) % mod;
 }
 res = (res + ll(i) * x) % mod;
 }
 }
 rep(i, 1, n) if (F.z[c[i]] < 0) {
 d[i] = -d[i];
 }
 rep(i, 0, k - 1) if (F.z[i] < 0) {
 F.z[i] = -F.z[i];
 swap(F.l[i], F.r[i]);
 F.l[i] = -F.l[i];
 F.r[i] = -F.r[i];
 }
 B = F;
 bool chk = true;
 rep(i, 0, k - 1) {
 dt[i] = B.z[i];
 chk &= dt[i] == 0;
 }
if (chk) {
 bool ok = false;
 rep(i, 0, k - 1) {
ok |= B.r[i] - B.l[i] >= w[i];
 }
 printf("%d\n", ok ? res : -1);
exit(0);
}
 int a[10] = {};
 rep(i, 1, n) {
 if (F.walk(c[i], d[i]) && F.r[c[i]] - F.l[c[i]] <= w[c[i]]) {
 bool ok = true;
rep(j, 0, k - 1) if (j != c[i]) {
 ok &= w[j] - F.r[j] + F.l[j] > 0;
 }
 if (!ok) {
 continue;
 }
 rep(j, 0, k - 1) if (j != c[i]) {
 a[j] = w[j] - F.r[j] + F.l[j];
 }

 a[c[i]] = w[c[i]] - F.r[c[i]] + F.l[c[i]] + 1, res = (res + ll(i) * work(a)) % mod;
 a[c[i]] = w[c[i]] - F.r[c[i]] + F.l[c[i]], res = (res + ll(mod - i) * work(a)) % mod;

} 
} rep(i, 0, k - 1) {
a[i] = max(0, w[i] - B.r[i] + B.l[i]);
}
 res = (res + ll(n) * work(a)) % mod;
 printf("%d\n", res);
 return 0;
}