QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#586883 | #9380. Match | MiniLong | AC ✓ | 136ms | 4460kb | C++17 | 4.2kb | 2024-09-24 16:22:14 | 2024-09-24 16:22:15 |
Judging History
answer
#include <bits/stdc++.h>
#define _rep(i, x, y) for(int i = x; i <= y; ++i)
#define _req(i, x, y) for(int i = x; i >= y; --i)
#define _rev(i, u) for(int i = head[u]; i; i = e[i].nxt)
#define pb push_back
#define fi first
#define se second
#define mst(f, i) memset(f, i, sizeof f)
using namespace std;
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
typedef long long ll;
typedef pair<int, int> PII;
namespace fastio{
#ifdef ONLINE_JUDGE
char ibuf[1 << 20],*p1 = ibuf, *p2 = ibuf;
#define get() p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++
#else
#define get() getchar()
#endif
template<typename T> inline void read(T &t){
T x = 0, f = 1;
char c = getchar();
while(!isdigit(c)){
if(c == '-') f = -f;
c = getchar();
}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
t = x * f;
}
template<typename T, typename ... Args> inline void read(T &t, Args&... args){
read(t);
read(args...);
}
template<typename T> void write(T t){
if(t < 0) putchar('-'), t = -t;
if(t >= 10) write(t / 10);
putchar(t % 10 + '0');
}
template<typename T, typename ... Args> void write(T t, Args... args){
write(t), putchar(' '), write(args...);
}
template<typename T> void writeln(T t){
write(t);
puts("");
}
template<typename T> void writes(T t){
write(t), putchar(' ');
}
#undef get
};
using namespace fastio;
#define multitest() int T; read(T); _rep(tCase, 1, T)
namespace Calculation{
const ll mod = 998244353;
ll ksm(ll p, ll h){ll base = p % mod, res = 1; while(h){if(h & 1ll) res = res * base % mod; base = base * base % mod, h >>= 1ll;} return res;}
void dec(ll &x, ll y){x = ((x - y) % mod + mod) % mod;}
void add(ll &x, ll y){x = (x + y) % mod;}
void mul(ll &x, ll y){x = x * y % mod;}
ll sub(ll x, ll y){return ((x - y) % mod + mod) % mod;}
ll pls(ll x, ll y){return ((x + y) % mod + mod) % mod;}
ll mult(ll x, ll y){return x * y % mod;}
}
using namespace Calculation;
const int N = 205;
ll n, k, C[N][N], fac[N];
vector<ll> solve(vector<ll> a, vector<ll> b, ll d){
int siz = min(a.size(), b.size());
vector<ll> res(siz + 1, 0);
if(!siz){res[0] = 1; return res;};
if(d == -1){
int x = a.size(), y = b.size();
_rep(i, 0, siz) res[i] = C[x][i] * C[y][i] % mod * fac[i] % mod;
return res;
}
vector<ll> A[2], B[2];
for(auto &i : a) A[i >> d & 1ll].pb(i);
for(auto &i : b) B[i >> d & 1ll].pb(i);
if(k >> d & 1ll){
vector<ll> L = solve(A[0], B[1], d - 1), R = solve(A[1], B[0], d - 1);
_rep(i, 0, min(A[0].size(), B[1].size())) _rep(j, 0, min(A[1].size(), B[0].size())){
add(res[i + j], L[i] * R[j]);
}
}else{
vector<ll> L = solve(A[0], B[0], d - 1), R = solve(A[1], B[1], d - 1);
_rep(i, 0, min(A[0].size(), B[0].size())) _rep(j, 0, min(A[1].size(), B[1].size())){
int x[2] = {(int)A[0].size() - i, (int)A[1].size() - j}, y[2] = {(int)B[0].size() - i, (int)B[1].size() - j};
_rep(p, 0, min(x[0], y[1])) _rep(q, 0, min(x[1], y[0])){
ll cur = C[x[0]][p] * C[y[1]][p] % mod * C[x[1]][q] % mod * C[y[0]][q] % mod;
mul(cur, fac[p] * fac[q] % mod);
add(res[i + j + p + q], L[i] * R[j] % mod * cur % mod);
}
}
}
// debug("d:%d\n", d);
// for(auto &i : a) debug("%d ", i); debug("\n");
// for(auto &i : b) debug("%d ", i); debug("\n");
// _rep(i, 0, siz) debug("%d ", res[i]);
// debug("\n");
// debug("==============\n");
return res;
}
int main(){
read(n, k);
_rep(i, 0, n) _rep(j, 0, i) C[i][j] = !j ? 1 : pls(C[i - 1][j], C[i - 1][j - 1]);
fac[0] = 1; _rep(i, 1, n) fac[i] = fac[i - 1] * i % mod;
vector<ll> a(n, 0), b(n, 0);
_rep(i, 1, n) read(a[i - 1]);
_rep(i, 1, n) read(b[i - 1]);
vector<ll> res = solve(a, b, 59);
_rep(i, 1, n) writeln(res[i]);
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3668kb
input:
9 5 1 7 2 8 4 9 2 5 10 1 3 2 4 5 8 8 8 9
output:
51 1034 10768 62195 200965 348924 294444 97344 7200
result:
ok 9 lines
Test #2:
score: 0
Accepted
time: 136ms
memory: 3972kb
input:
200 569102225177443347 1103663383682482176 1103381908705771520 1099441259031822336 1098878309078401024 1089871109823660032 1080863910568919040 1074108511127863296 1071856711314178048 1069041961547071488 1068479011593650176 1067353111686807552 1062849512059437056 1049338713177325568 10448351135499550...
output:
20506 208107723 47878304 53020813 972282728 933586852 658157196 670189811 957980024 366179738 217980591 967482558 833450149 987731802 260904367 5263881 600332344 906061351 658256294 93700706 421323952 178075016 219871690 986880524 848776106 191185484 641917326 576497440 908609746 349728876 606714342...
result:
ok 200 lines
Test #3:
score: 0
Accepted
time: 9ms
memory: 4012kb
input:
200 1098723432450995412 972777519512027136 936748722493063168 864691128455135232 860187528827764736 857935729014079488 856246879153815552 855683929200394240 851180329573023744 848928529759338496 847802629852495872 847310048643252224 847239679899074560 846676729945653248 828662331436171264 8280993814...
output:
8320 34035512 428014253 916072411 696504298 748377440 32424677 188402417 233587075 130639672 759476380 546285625 187068736 159002787 131866334 381530906 133126344 373727612 923311054 725293681 718162548 39511135 322320638 44709653 156884882 285926751 787179409 282967016 153092344 615721347 950855850...
result:
ok 200 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 4396kb
input:
200 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
3072 4412928 940025853 665370743 752672705 581549490 41990996 541401698 170451802 26584141 220983766 844620126 64506869 137621326 418866920 351049174 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 200 lines
Test #5:
score: 0
Accepted
time: 2ms
memory: 4460kb
input:
200 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
40000 792020000 319908096 286630939 515085548 95626140 472749362 800008042 594973486 139901984 847967250 125664877 254232250 419486325 204481923 979660340 41873095 540955890 585129047 205968776 196086667 674391130 737319172 669580034 973843015 207125612 331414909 119844754 24879477 990932807 8476927...
result:
ok 200 lines
Extra Test:
score: 0
Extra Test Passed