# RT
by IOI2021 @ 2019-09-30 08:18:56
这题不卡常T了四次 97'
```cpp
#include<bits/stdc++.h>
#define mod 998244353
#define ll long long
using namespace std;
void fwt(ll *a, int len, int opt){
for(int i = 2; i <= len; i <<= 1)
for(int p = i >> 1, j = 0; j + i <= len; j += i)
for(int k = j; k < j + p; k ++)
a[p + k] =(a[p + k] + opt * a[k] + mod) % mod;
}
ll qpow(ll x, int y){
ll ret = 1;
for(;y; y >>= 1, x = x * x % mod) if(y & 1) ret = ret * x % mod;
return ret;
}
int fa[25];
int get(int x){
return fa[x] == x? x:(fa[x] = get(fa[x]));
}
void merge(int x , int y){
x = get(x), y = get(y);
fa[x] = y;
}
int n, m, q, a[25][25], w[25], he[1 << 23], ok[1 << 23], du[25], U[1000005], V[1000005], bitcount[1 << 23];
ll f[23][(1 << 22)], g[23][1 << 22];
int main(){
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= m; i ++) scanf("%d%d", &U[i], &V[i]);
for(int i = 1; i <= n; i ++) scanf("%d", &w[i]);
for(int S = 0; S < (1 << n); S ++){
int bb = 0;
for(int i = 1; i <= n; i ++){
if((1 << (i - 1)) & S) he[S] += w[i], bb ++;
du[i] = 0, fa[i] = i;
}
bitcount[S] = bb;
for(int i = 1; i <= m; i ++){
if(((1 << (U[i] - 1)) & S) && ((1 << (V[i] - 1)) & S)){
if(get(U[i]) != get(V[i])) merge(U[i], V[i]), bb --;
du[U[i]] ++;
du[V[i]] ++;
}
}
if(bb != 1) ok[S] = 1;
int cnt = 0;
for(int i = 1; i <= n; i ++)
cnt += (du[i] & 1);
if(cnt) ok[S] = 1;
if(ok[S]) g[bitcount[S]][S] = qpow(he[S], q);
}
for(int i = 0; i <= n; i ++) fwt(g[i], 1 << n, 1);
f[0][0] = 1; fwt(f[0], 1 << n, 1);
for(int i = 1; i <= n; i ++){
for(int j = 0; j <= i - 1; j ++)
for(int k = 0; k < (1 << n); k ++)
f[i][k] += f[j][k] * g[i - j][k] % mod, f[i][k] %= mod;
fwt(f[i], 1 << n, -1);
for(int j = 0; j < (1 << n); j ++) f[i][j] = bitcount[j] == i? f[i][j] * qpow(qpow(he[j], mod - 2), q) % mod:0;
if(i != n) fwt(f[i], 1 << n, 1);
}
printf("%lld", f[n][(1 << n) - 1]);
return 0;
}
```
by IOI2021 @ 2019-09-30 08:19:56
后来吸了臭氧才卡过去
求助如何优化QWQ(不卡常)
by IOI2021 @ 2019-09-30 08:20:35
qndmx
by k1saki @ 2019-09-30 08:22:36
qndmx
by lygmh @ 2019-09-30 08:22:55
QNDMX
by Provicy @ 2019-09-30 08:26:52
突然发现没有预处理inv导致多了一个log
但为什么还是T \快哭了
```cpp
#include<bits/stdc++.h>
#define mod 998244353
#define ll long long
using namespace std;
void fwt(ll *a, int len, int opt){
for(int i = 2; i <= len; i <<= 1)
for(int p = i >> 1, j = 0; j + i <= len; j += i)
for(int k = j; k < j + p; k ++)
a[p + k] =(a[p + k] + opt * a[k] + mod) % mod;
}
ll qpow(ll x, int y){
ll ret = 1;
for(;y; y >>= 1, x = x * x % mod) if(y & 1) ret = ret * x % mod;
return ret;
}
int fa[25];
int get(int x){
return fa[x] == x? x:(fa[x] = get(fa[x]));
}
void merge(int x , int y){
x = get(x), y = get(y);
fa[x] = y;
}
int n, m, q, a[25][25], w[25], he[1 << 23], ok[1 << 23], du[25], U[1000005], V[1000005], bitcount[1 << 23];
ll f[23][1 << 22], g[23][1 << 22], inv[1 << 22];
int main(){
scanf("%d%d%d", &n, &m, &q);
int len = 1 << n;
for(int i = 1; i <= m; i ++) scanf("%d%d", &U[i], &V[i]);
for(int i = 1; i <= n; i ++) scanf("%d", &w[i]);
for(int S = 0; S < len; S ++){
int bb = 0;
for(int i = 1; i <= n; i ++){
if((1 << (i - 1)) & S) he[S] += w[i], bb ++;
du[i] = 0, fa[i] = i;
}
bitcount[S] = bb;
for(int i = 1; i <= m; i ++){
if(((1 << (U[i] - 1)) & S) && ((1 << (V[i] - 1)) & S)){
if(get(U[i]) != get(V[i])) merge(U[i], V[i]), bb --;
du[U[i]] ++;
du[V[i]] ++;
}
}
if(bb != 1) ok[S] = 1;
int cnt = 0;
for(int i = 1; i <= n; i ++)
cnt += (du[i] & 1);
if(cnt) ok[S] = 1;
if(ok[S]) g[bitcount[S]][S] = qpow(he[S], q);
inv[S] = qpow(qpow(he[S], mod - 2), q);
}
for(int i = 0; i <= n; i ++) fwt(g[i], 1 << n, 1);
f[0][0] = 1; fwt(f[0], 1 << n, 1);
for(int i = 1; i <= n; i ++){
for(int j = 0; j <= i - 1; j ++)
for(int k = 0; k < len; k ++)
f[i][k] += f[j][k] * g[i - j][k] % mod, f[i][k] %= mod;
fwt(f[i], 1 << n, -1);
for(int j = 0; j < len; j ++) f[i][j] = bitcount[j] == i? f[i][j] * inv[j] % mod:0;
if(i != n) fwt(f[i], 1 << n, 1);
}
printf("%lld", f[n][len - 1]);
return 0;
}
```
by IOI2021 @ 2019-09-30 08:28:44
也不是多了log，就是常数大了
但还是T QWQ
by IOI2021 @ 2019-09-30 08:29:17
qndmx
by 谢谢_对不起 @ 2019-09-30 08:34:59
萌新就切黑题%%%
by JBLee @ 2019-09-30 08:56:57