QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#21421 | #2819. 摆家具 | gogo | WA | 519ms | 242868kb | C++20 | 3.7kb | 2022-03-04 22:57:40 | 2022-05-08 03:13:51 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i ++)
#define per(i, r, l) for(int i = (r); i >= (l); i --)
#define trv(i, u, v) for(int i = head[u], v = e[i].to; i; v = e[i = e[i].nxt].to)
#define fi first
#define se second
#define all(s) s.begin(), s.end()
#define sz(s) (int)(s.size())
#define lb(s) ((s) & -(s))
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
mt19937_64 hua(time(0));
template<typename T> inline bool chkmx(T &x, T y) {return x < y ? x = y, 1 : 0;}
template<typename T> inline bool chkmn(T &x, T y) {return y < x ? x = y, 1 : 0;}
template<int T> using A = array<int, T>;
inline ll read() {
ll x = 0, f = 1; char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = 0;
for(; isdigit(c); c = getchar()) x = x * 10 + c - '0';
return f ? x : -x;
}
const int maxn = 1e6;
const int maxk = 20;
//const int B = 1e5;
const int B = 3e3;
const int mod = 998244353;
int n, k, q, N, pw[maxk + 5], w[maxn + 5];
int fac[maxk + 5], ifac[maxk + 5], inv[maxk + 5];
int f[maxn + 5][maxk + 5], g[maxn + 5][maxk + 5], h[maxn + 5][maxk + 5];
inline int add(int a, int b) {return (a += b) >= mod ? a - mod : a;}
inline int sub(int a, int b) {return (a -= b) < 0 ? a + mod : a;}
inline int mul(int a, int b) {return 1ll * a * b % mod;}
inline void upd(int &a, int b) {a = add(a, b);}
inline int fpw(int a, int b) {
int ans = 1;
for(; b; b >>= 1, a = mul(a, a)) if(b & 1) ans = mul(ans, a);
return ans;
}
struct Mat {
int a[maxk + 1][maxk + 1];
int* operator [] (int x) {return a[x];}
Mat() {memset(a, 0, sizeof a);}
friend Mat operator * (Mat x, Mat y) {
Mat z;
rep(i, 0, k) rep(j, 0, k) rep(l, 0, k) {
upd(z[i][j], mul(x[i][l], y[l][j]));
}
return z;
}
}mpw1[B + 5], mpw2[B + 5], mpw3[B + 5];
void init() {
fac[0] = fac[1] = inv[0] = inv[1] = ifac[0] = ifac[1] = 1;
rep(i, 2, maxk) fac[i] = mul(fac[i - 1], i);
rep(i, 2, maxk) inv[i] = mul(inv[mod % i], mod - mod / i);
rep(i, 2, maxk) ifac[i] = mul(ifac[i - 1], inv[i]);
}
inline int c(int n, int m) {return mul(fac[n], mul(ifac[m], ifac[n - m]));}
int main() {
//freopen("in.txt", "r", stdin);
n = read(), k = read(), q = read();
N = fpw(n, k);
pw[0] = 1;
init();
rep(i, 1, k) pw[i] = pw[i - 1] * n;
rep(i, 0, N - 1) f[i][0] = w[i] = read();
rep(i, 0, k - 1) {
memcpy(g, f, sizeof g);
memcpy(h, f, sizeof h);
per(s, N - 1, 0) {
rep(j, 0, k) {
if(s / pw[i] % n != n - 1) {
upd(g[s][j], g[s + pw[i]][j]);
}
}
}
rep(s, 0, N - 1) {
rep(j, 0, k) {
if(s / pw[i] % n != 0) {
upd(h[s][j], h[s - pw[i]][j]);
}
}
}
rep(s, 0, N - 1) {
per(j, k, 0) {
f[s][j] = 0;
if(s / pw[i] % n != 0) upd(f[s][j], h[s - pw[i]][j]);
if(s / pw[i] % n != n - 1) upd(f[s][j], g[s + pw[i]][j]);
if(j) upd(f[s][j], f[s][j - 1]);
}
}
}
// rep(i, 0, N - 1) {
// rep(j, 0, k) {
// cout << g[i][j] << " \n"[j == k];
// }
// }
Mat bs;
rep(i, 0, k) {
bs[i][i] = mul(k - i, n - 2);
mpw1[0][i][i] = mpw2[0][i][i] = mpw3[0][i][i] = 1;
}
rep(i, 1, k) {
bs[i][i - 1] = mul(i, n - 1);
}
rep(i, 0, k - 1) {
bs[i][i + 1] = k - i;
}
rep(i, 1, B) {
mpw1[i] = mpw1[i - 1] * bs;
}
rep(i, 1, B) {
mpw2[i] = mpw2[i - 1] * mpw1[B];
}
rep(i, 1, B) {
mpw3[i] = mpw3[i - 1] * mpw2[B];
}
ll lstans = 1;
rep(i, 1, q) {
lstans = 1;
ll a = read(), t = read() * lstans % mod;
int x = t / B % B, y = t % B, z = t / B / B, ans = 0;
Mat cur = mpw3[z] * mpw2[x] * mpw1[y];
rep(i, 0, k) {
// cout << cur[k][i] << " \n"[i == k];
upd(ans, mul(mul(cur[k][i], f[a][i]), fpw(mul(c(k, i), fpw(n - 1, k - i)), mod - 2)));
}
cout << (lstans = ans) << '\n';
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 519ms
memory: 242868kb
input:
6 7 23333 691899807 511100503 969237388 938904792 350428599 320423686 227132681 288051232 833056445 128207711 81740114 850060462 194951182 130925016 505452669 304380595 703105541 640122112 75295756 128144693 482592240 835507949 68960843 807876145 6134269 259053259 386495729 193956365 370675670 12980...
output:
190581075 374703333 587592649 715036733 52205754 449970741 545834015 214656707 145174324 800587815 709056518 595269540 271435768 835779057 743667322 946351634 674562387 419542408 983151442 734708528 212528399 946300440 10857196 532879362 817266836 570660142 328506393 259008207 933922036 804666714 69...
result:
wrong answer 2nd lines differ - expected: '197794774', found: '374703333'