QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #67986 | #5169. 夹娃娃 | yllcm | Compile Error | / | / | C++17 | 13.0kb | 2022-12-13 20:21:43 | 2022-12-13 20:21:46 |
Judging History
你现在查看的是最新测评结果
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2022-12-13 20:21:46]
- 评测
- 测评结果：Compile Error
- 用时：0ms
- 内存：0kb
- [2022-12-13 20:21:43]
- 提交
answer
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define FR first
#define SE second
#define il inline
#define re register
using namespace std;
inline int read() {
int x = 0; bool op = 0;
char c = getchar();
while(!isdigit(c))op |= (c == '-'), c = getchar();
while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return op ? -x : x;
}
const int N = 5e3 + 10;
const int M = 2080;
int n, Q, p;
namespace S1 {
const int P = 998244353;
int B, T;
il void add(int &a, int b) {a += b; a >= P ? a -= P : 0;}
il void sub(int &a, int b) {a -= b; a < 0 ? a += P : 0;}
il int ksm(int x, int k) {
int res = 1;
for(int pw = x; k; (k & 1) ? res = 1ll * res * pw % P : 0, pw = 1ll * pw * pw % P, k >>= 1);
return res;
}
int f[20][N], L[10], R[10], st[N][N], pd[N], tmp[N];
struct Poly {
int f[N];
il Poly operator * (const int &x) {
Poly res;
for(re int i = 0; i <= M; i++) {
res.f[i] = 1ll * f[i] * x % P;
}
return res;
}
il Poly operator * (const Poly &x) {
Poly res;
for(re int i = 0; i <= M; i++) {
res.f[i] = 1ll * f[i] * x.f[i] % P;
}
return res;
}
il Poly operator + (const Poly &x) {
Poly res;
for(re int i = 0; i <= M; i++) {
res.f[i] = (f[i] + x.f[i]) % P;
}
return res;
}
}g[20], h[20], pg[5][600][1 << 4], th[5][1 << 4];
char str[N];
void MAIN() {
for(re int i = 1; i <= n; i++) {
int k = read();
f[i][0] = 1;
for(re int j = 1; j <= k; j++) {
int b = read(), c = read();
for(re int t = 520; ~t; t--) {
if(f[i][t] == 0)continue;
for(re int p = 1; p <= c && t + p * b <= 520; p++) {
add(f[i][t + p * b], f[i][t]);
}
}
}
// for(int t = 0; t <= 520; t++) {
// if(f[i][t])printf("f:%d %d %d\n", i, t, f[i][t]);
// }
}
for(re int i = 1; i <= n; i++) {
for(re int j = 0; j <= M; j++) {
int w = 1;
for(re int k = 0; k <= 520; k++) {
add(h[i].f[j], 1ll * f[i][k] * w % P);
w = 1ll * w * j % P;
}
}
}
pd[0] = 1;
for(re int i = 0; i <= M; i++) {
for(re int j = i; j >= 0; j--) {
add(pd[j + 1], pd[j]);
pd[j] = (P - 1ll * pd[j] * i % P) % P;
}
}
for(re int i = 0; i <= M; i++) {
int coef = 1;
for(re int j = 0; j <= M; j++) {
if(j != i)coef = 1ll * coef * ((i - j + P) % P) % P;
}
coef = ksm(coef, P - 2);
memcpy(st[i], pd, sizeof(pd));
for(re int j = M + 1; j; j--)add(st[i][j - 1], 1ll * i * st[i][j] % P);
for(re int j = 0; j <= M; j++)st[i][j] = st[i][j + 1]; st[i][M + 1] = 0;
for(re int j = 0; j <= M; j++)st[i][j] = 1ll * st[i][j] * coef % P;
// for(re int j = 1; j <= M; j++)add(st[i][j], st[i][j - 1]);
}
B = 3;
for(re int i = 1; i <= n; i += B)L[++T] = i, R[T] = min(n, i + B - 1);
for(int i = 1; i <= T; i++) {
int l = R[i] - L[i] + 1;
for(int j = 0; j < (1 << l); j++) {
for(int k = 0; k <= M; k++)th[i][j].f[k] = 1;
for(int k = 0; k < l; k++) {
if(j >> k & 1)continue;
th[i][j] = th[i][j] * h[k + L[i]];
}
for(int t = 0; t <= 520; t++) {
tmp[t] = 0;
for(int p = 0; p <= M; p++) {
add(tmp[t], 1ll * th[i][j].f[p] * st[p][t] % P);
}
}
for(int p = 0; p <= M; p++) {
int w = 1; th[i][j].f[p] = 0;
for(int t = 0; t <= 520; t++) {
add(th[i][j].f[p], 1ll * w * tmp[t] % P);
w = 1ll * w * p % P;
}
}
}
}
for(re int i = 0; i <= 520; i++) {
for(re int j = 0; j <= M; j++) {
int w = ksm(j, i);
for(re int k = 1; k <= n; k++) {
add(g[k].f[j], 1ll * f[k][i] * w % P);
}
}
for(re int j = 1; j <= T; j++) {
int l = R[j] - L[j] + 1;
for(re int s = 0; s < (1 << l); s++) {
if((i + 1) * __builtin_popcount(s) > 520)continue;
pg[j][i][s] = th[j][s];
for(re int k = 0; k < l; k++) {
if(s >> k & 1)pg[j][i][s] = pg[j][i][s] * g[k + L[j]];
}
if(__builtin_popcount(s) & 1)pg[j][i][s] = pg[j][i][s] * (P - 1);
}
for(re int k = 0; k < l; k++) {
for(re int s = 0; s < (1 << l); s++) {
if(s >> k & 1) {
pg[j][i][s] = pg[j][i][s] + pg[j][i][s ^ (1 << k)];
}
}
}
}
}
for(int i = 0; i <= M; i++) {
for(int j = 1; j <= M; j++) {
add(st[i][j], st[i][j - 1]);
}
}
// int _TIME = 0;
while(Q--) {
scanf("%s", str + 1);
int m = read(), d = read(), sum = 0, res = 0;
for(re int i = 1; i <= n; i++)if(str[i] == '1')sum += d;
if(sum > m) {printf("0\n"); continue;}
Poly now;
for(re int i = 0; i <= M; i++)now.f[i] = 1;
for(re int j = 1; j <= T; j++) {
int s = 0, l = R[j] - L[j] + 1;
for(re int k = 0; k < l; k++) {
if(str[k + L[j]] == '1')s |= (1 << k);
}
now = now * pg[j][d - 1][s];
}
// _TIME -= clock();
for(re int i = 0; i <= M; i++) {
// add(res, 1ll * now.f[i] * st[i][m] % P);
add(res, 1ll * now.f[i] * st[i][m] % P);
}
// _TIME += clock();
printf("%d\n", res);
}
// cerr << 1.0 * _TIME / CLOCKS_PER_SEC << endl;
return ;
}
};
namespace S1 {
const int P = 1e9 + 7;
int B, T;
il void add(int &a, int b) {a += b; a >= P ? a -= P : 0;}
il void sub(int &a, int b) {a -= b; a < 0 ? a += P : 0;}
il int ksm(int x, int k) {
int res = 1;
for(int pw = x; k; (k & 1) ? res = 1ll * res * pw % P : 0, pw = 1ll * pw * pw % P, k >>= 1);
return res;
}
int f[20][N], L[10], R[10], st[N][N], pd[N], tmp[N];
struct Poly {
int f[N];
il Poly operator * (const int &x) {
Poly res;
for(re int i = 0; i <= M; i++) {
res.f[i] = 1ll * f[i] * x % P;
}
return res;
}
il Poly operator * (const Poly &x) {
Poly res;
for(re int i = 0; i <= M; i++) {
res.f[i] = 1ll * f[i] * x.f[i] % P;
}
return res;
}
il Poly operator + (const Poly &x) {
Poly res;
for(re int i = 0; i <= M; i++) {
res.f[i] = (f[i] + x.f[i]) % P;
}
return res;
}
}g[20], h[20], pg[5][600][1 << 4], th[5][1 << 4];
char str[N];
void MAIN() {
for(re int i = 1; i <= n; i++) {
int k = read();
f[i][0] = 1;
for(re int j = 1; j <= k; j++) {
int b = read(), c = read();
for(re int t = 520; ~t; t--) {
if(f[i][t] == 0)continue;
for(re int p = 1; p <= c && t + p * b <= 520; p++) {
add(f[i][t + p * b], f[i][t]);
}
}
}
// for(int t = 0; t <= 520; t++) {
// if(f[i][t])printf("f:%d %d %d\n", i, t, f[i][t]);
// }
}
for(re int i = 1; i <= n; i++) {
for(re int j = 0; j <= M; j++) {
int w = 1;
for(re int k = 0; k <= 520; k++) {
add(h[i].f[j], 1ll * f[i][k] * w % P);
w = 1ll * w * j % P;
}
}
}
pd[0] = 1;
for(re int i = 0; i <= M; i++) {
for(re int j = i; j >= 0; j--) {
add(pd[j + 1], pd[j]);
pd[j] = (P - 1ll * pd[j] * i % P) % P;
}
}
for(re int i = 0; i <= M; i++) {
int coef = 1;
for(re int j = 0; j <= M; j++) {
if(j != i)coef = 1ll * coef * ((i - j + P) % P) % P;
}
coef = ksm(coef, P - 2);
memcpy(st[i], pd, sizeof(pd));
for(re int j = M + 1; j; j--)add(st[i][j - 1], 1ll * i * st[i][j] % P);
for(re int j = 0; j <= M; j++)st[i][j] = st[i][j + 1]; st[i][M + 1] = 0;
for(re int j = 0; j <= M; j++)st[i][j] = 1ll * st[i][j] * coef % P;
// for(re int j = 1; j <= M; j++)add(st[i][j], st[i][j - 1]);
}
B = 3;
for(re int i = 1; i <= n; i += B)L[++T] = i, R[T] = min(n, i + B - 1);
for(int i = 1; i <= T; i++) {
int l = R[i] - L[i] + 1;
for(int j = 0; j < (1 << l); j++) {
for(int k = 0; k <= M; k++)th[i][j].f[k] = 1;
for(int k = 0; k < l; k++) {
if(j >> k & 1)continue;
th[i][j] = th[i][j] * h[k + L[i]];
}
for(int t = 0; t <= 520; t++) {
tmp[t] = 0;
for(int p = 0; p <= M; p++) {
add(tmp[t], 1ll * th[i][j].f[p] * st[p][t] % P);
}
}
for(int p = 0; p <= M; p++) {
int w = 1; th[i][j].f[p] = 0;
for(int t = 0; t <= 520; t++) {
add(th[i][j].f[p], 1ll * w * tmp[t] % P);
w = 1ll * w * p % P;
}
}
}
}
for(re int i = 0; i <= 520; i++) {
for(re int j = 0; j <= M; j++) {
int w = ksm(j, i);
for(re int k = 1; k <= n; k++) {
add(g[k].f[j], 1ll * f[k][i] * w % P);
}
}
for(re int j = 1; j <= T; j++) {
int l = R[j] - L[j] + 1;
for(re int s = 0; s < (1 << l); s++) {
if((i + 1) * __builtin_popcount(s) > 520)continue;
pg[j][i][s] = th[j][s];
for(re int k = 0; k < l; k++) {
if(s >> k & 1)pg[j][i][s] = pg[j][i][s] * g[k + L[j]];
}
if(__builtin_popcount(s) & 1)pg[j][i][s] = pg[j][i][s] * (P - 1);
}
for(re int k = 0; k < l; k++) {
for(re int s = 0; s < (1 << l); s++) {
if(s >> k & 1) {
pg[j][i][s] = pg[j][i][s] + pg[j][i][s ^ (1 << k)];
}
}
}
}
}
for(int i = 0; i <= M; i++) {
for(int j = 1; j <= M; j++) {
add(st[i][j], st[i][j - 1]);
}
}
// int _TIME = 0;
while(Q--) {
scanf("%s", str + 1);
int m = read(), d = read(), sum = 0, res = 0;
for(re int i = 1; i <= n; i++)if(str[i] == '1')sum += d;
if(sum > m) {printf("0\n"); continue;}
Poly now;
for(re int i = 0; i <= M; i++)now.f[i] = 1;
for(re int j = 1; j <= T; j++) {
int s = 0, l = R[j] - L[j] + 1;
for(re int k = 0; k < l; k++) {
if(str[k + L[j]] == '1')s |= (1 << k);
}
now = now * pg[j][d - 1][s];
}
// _TIME -= clock();
for(re int i = 0; i <= M; i++) {
// add(res, 1ll * now.f[i] * st[i][m] % P);
add(res, 1ll * now.f[i] * st[i][m] % P);
}
// _TIME += clock();
printf("%d\n", res);
}
// cerr << 1.0 * _TIME / CLOCKS_PER_SEC << endl;
return ;
}
};
int main() {
n = read(); Q = read(); p = read();
if(p == 998244353)S1::MAIN();
else S2::MAIN();
return 0;
}
详细
answer.code: In member function ‘S1::Poly S1::Poly::operator*(const int&)’:
answer.code:39:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
39 | for(re int i = 0; i <= M; i++) {
| ^
answer.code: In member function ‘S1::Poly S1::Poly::operator*(const S1::Poly&)’:
answer.code:46:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
46 | for(re int i = 0; i <= M; i++) {
| ^
answer.code: In member function ‘S1::Poly S1::Poly::operator+(const S1::Poly&)’:
answer.code:53:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
53 | for(re int i = 0; i <= M; i++) {
| ^
answer.code: In function ‘void S1::MAIN()’:
answer.code:61:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
61 | for(re int i = 1; i <= n; i++) {
| ^
answer.code:64:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
64 | for(re int j = 1; j <= k; j++) {
| ^
answer.code:66:28: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
66 | for(re int t = 520; ~t; t--) {
| ^
answer.code:68:32: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
68 | for(re int p = 1; p <= c && t + p * b <= 520; p++) {
| ^
answer.code:77:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
77 | for(re int i = 1; i <= n; i++) {
| ^
answer.code:78:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
78 | for(re int j = 0; j <= M; j++) {
| ^
answer.code:80:28: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
80 | for(re int k = 0; k <= 520; k++) {
| ^
answer.code:87:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
87 | for(re int i = 0; i <= M; i++) {
| ^
answer.code:88:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
88 | for(re int j = i; j >= 0; j--) {
| ^
answer.code:93:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
93 | for(re int i = 0; i <= M; i++) {
| ^
answer.code:95:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
95 | for(re int j = 0; j <= M; j++) {
| ^
answer.code:100:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
100 | for(re int j = M + 1; j; j--)add(st[i][j - 1], 1ll * i * st[i][j] % P);
| ^
answer.code:101:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
101 | for(re int j = 0; j <= M; j++)st[i][j] = st[i][j + 1]; st[i][M + 1] = 0;
| ^
answer.code:102:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
102 | for(re int j = 0; j <= M; j++)st[i][j] = 1ll * st[i][j] * coef % P;
| ^
answer.code:106:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
106 | for(re int i = 1; i <= n; i += B)L[++T] = i, R[T] = min(n, i + B - 1);
| ^
answer.code:130:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
130 | for(re int i = 0; i <= 520; i++) {
| ^
answer.code:131:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
131 | for(re int j = 0; j <= M; j++) {
| ^
answer.code:133:28: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
133 | for(re int k = 1; k <= n; k++) {
| ^
answer.code:137:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
137 | for(re int j = 1; j <= T; j++) {
| ^
answer.code:139:28: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
139 | for(re int s = 0; s < (1 << l); s++) {
| ^
answer.code:142:32: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
142 | for(re int k = 0; k < l; k++) {
| ^
answer.code:147:28: warni...