QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#90321#5827. 异或图infinities20 982ms258444kbC++146.5kb2023-03-22 17:49:262023-03-22 17:49:27

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-22 17:49:27]
  • 评测
  • 测评结果：20
  • 用时：982ms
  • 内存：258444kb
查看
  • [2023-03-22 17:49:26]
  • 提交

answer

#include<bits/stdc++.h>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
namespace infinities{
	#define fint register int
	#define ls(i) (i << 1)
	#define rs(i) ((i << 1) | 1)
	#define pii pair<int, int>
	#define im int mid = (l + r) >> 1
	#define INT __int128
	#define ll long long
	#define ui unsigned int
	#define ull unsigned long long
	#define lc ch[now][0]
	#define rc ch[now][1]
	const int mod = 998244353, INF = 998244353, maxn = 5e5 + 7;
	namespace FastIO{//10M
		const int SS = 1e7; char num_[50]; int cnt_;
		inline int xchar(){static char buf[SS]; static int len = 0, pos = 0; if(pos == len)pos = 0, len = fread(buf, 1, SS, stdin); if(pos == len)exit(0); return buf[pos++];}
		inline int read(){fint x = 0, f = 1, ch = getchar(); while(ch < '0' || ch > '9'){if(ch == '-')f = -1; ch = getchar();}while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();} return x * f;}
		inline void write(int x){if(x == 0){putchar('0'); return;}if(x < 0)putchar('-'), x = -x; while(x)num_[++cnt_] = x % 10 ^ 48,x /= 10; while(cnt_)putchar(num_[cnt_--]);}
		inline void write(int x, char c){write(x), putchar(c);}
	}
	using namespace __gnu_pbds;
	gp_hash_table<int, int>D[(1 << 15) + 7];
	void file(){freopen("a.in", "r", stdin), freopen("a.out", "w", stdout);}
	using namespace std;
	using namespace FastIO;
	namespace mystd{
		inline void chkmin(int &a, int b){a = min(a, b); return;} inline void chkmax(int &a, int b){a = max(a, b); return;}
		inline void qk(int &a, int b){a = a + b; a = (a >= mod) ? a - mod : a;}
		inline void sub(int &a, int b){a = a - b + mod; a = (a >= mod) ? a - mod : a;}
		inline int qpow(int x, int k){fint res = 1; for(; k; k = (k >> 1), x = 1ll * x * x % mod)if(k & 1)res = 1ll * res * x % mod; return res;}
	}
	using namespace mystd;
	const int M = 17e6 + 7;
	ll a[maxn], c;
	int n, m, ed[(1 << 15) + 7], g[(1 << 15) + 7], f3[M], f[M], f2[M], dp[(1 << 15) + 7];
	int id[(1 << 15) + 7], sum[(1 << 15) + 7];
	int p[20], tot;
	#define int long long
	int solve(int s){
	    vector<ll>b; b.clear();
	    fint ans = 0;
	    ll sum = 0;
	    for(fint i = 0; i < n; i++)
	        if((s >> i) & 1)b.push_back(a[i]), sum ^= a[i];
	    if(sum == c)++ans;
	    for(fint i = 60; i >= 0; i--){
	        fint sum = 0;
	        for(fint x : b)sum ^= ((x >> (i + 1)));
	        if(sum == (c >> (i + 1))){
	            static int f[2][2], g[2][2];
	            memset(f, 0, sizeof(f));
	            f[0][0] = 1;
	            for(fint x : b){
	                if((x >> i) & 1){
	                    fint v0 = (1ll << i) % mod;
	                    fint v1 = ((x & ((1ll << i) - 1)) + 1) % mod;
	                    g[0][0] = 1ll * f[0][1] * v1 % mod;
	                    g[0][1] = 1ll * f[0][0] * v1 % mod;
	                    g[1][0] = 1ll * f[1][0] * v0 % mod + 1ll * f[1][1] * v1 % mod + f[0][0];
	                    g[1][1] = 1ll * f[1][1] * v0 % mod + 1ll * f[1][0] * v1 % mod + f[0][1];
	                    f[0][1] = g[0][1] % mod;
		                f[1][1] = g[1][1] % mod;
		                f[0][0] = g[0][0] % mod;
		                f[1][0] = g[1][0] % mod;
	                }else{
	                    fint now = ((x & ((1ll << i) - 1)) + 1) % mod;
	                    f[0][1] = 1ll * f[0][1] * now % mod;
		                f[1][1] = 1ll * f[1][1] * now % mod;
		                f[0][0] = 1ll * f[0][0] * now % mod;
		                f[1][0] = 1ll * f[1][0] * now % mod;
	                }
	            }
		        ans += f[1][(c >> i) & 1];
		        ans %= mod;
	        }
	    }
		return (ans % mod + mod) % mod;
	}
	#undef int
	pair<ll, int>qq[233]; int poss[233], ctz[(1 << 15) + 7], ppc[(1 << 15) + 7];
	signed main(){
		n = read(), m = read(), c = read();
		for(fint i = 0; i < n; i++)a[i] = read(), qq[i] = {a[i], i};
		sort(qq, qq + n);
		for(fint i = 0; i < n; i++)a[i] = qq[i].first, poss[qq[i].second] = i;
		for(fint i = 1; i <= m; i++){fint u = poss[read() - 1], v = poss[read() - 1]; ed[(1 << u) + (1 << v)] = 1;}
		for(fint i = 0; i < n; i++)for(fint j = 0; j < (1 << n); j++)if(j & (1 << i))ed[j] |= ed[j ^ (1 << i)];
		g[0] = 1;
		for(fint S = 1; S < (1 << n); S++){
			ctz[S] = __builtin_ctz(S), ppc[S] = __builtin_popcount(S);
			fint res = 0;
			if(ed[S] == 0)res = 1;
			for(fint T = S; T; T = (T - 1 & S)){
				if(T == S || T == 0)continue;
				if(__builtin_ctz(T) != __builtin_ctz(S))continue;
				if(ed[S ^ T] == 0)sub(res, g[T]);
			}
			g[S] = res;
		}
		for(fint S = 1; S < (1 << n); S++){
			id[S] = -1;
			for(fint i = 0; i < n; i++){
				if(!(S & (1 << i)))continue;
				if(id[S] < 0){id[S] = i; break;}
			}
		}
		fint mx = pow(3, n), all = (1 << n) - 1;
		f[0] = 1;
		auto calc = [&](int S){fint S1 = 0, S2 = 0; for(fint i = 0; i < n; i++){p[i] = S % 3, S /= 3; if(p[i] == 2)S1 |= (1 << i), S2 |= (1 << i); if(p[i] == 1)S1 |= (1 << i);} return pii{S1, S2};};
		auto getT = [&](int S1, int S2){fint S = 0; for(fint i = n - 1; i >= 0; i--){S *= 3; if(S1 & (1 << i)){if(S2 & (1 << i))S += 2;else S += 1;}} return S;};
		auto getS = [&](int S1, int S2){return D[S1][S2];};
		for(fint S1 = 0; S1 < (1 << n); S1++){
			for(fint S2 = S1; ; S2 = (S2 - 1) & S1){
				D[S1][S2] = getT(S1, S2);
				if(S2 == 0)break;
			}
		}
		for(fint qwq = 0; qwq < mx; qwq++){
			if(f[qwq] == 0)continue;
			pii X = calc(qwq); fint S1 = X.first, S2 = X.second;
			for(fint T = all ^ S1; T; T = (T - 1 & (all ^ S1))){
				fint k = id[T];
				if(S2 && k >= ctz[S2])continue;
				if(ppc[T] & 1)qk(f[getS(S1 | T, S2 | (1 << id[T]))], 1ll * f[qwq] * g[T] % mod);
			}
		}
		f2[0] = 1;
		for(fint qwq = 0; qwq < mx; qwq++){
			if(f2[qwq] == 0)continue;
			pii X = calc(qwq); fint S1 = X.first, S2 = X.second;
			for(fint T = all ^ S1; T; T = (T - 1 & (all ^ S1))){
				fint k = id[T];
				if(S2 && k >= ctz[S2])continue;
				if(ppc[T] % 2 == 0)qk(f2[getS(S1 | T, S2 | (1 << id[T]))], 1ll * f2[qwq] * g[T] % mod * (a[id[T]] % mod + 1) % mod);
			}
		}
		for(fint S1 = 0; S1 < (1 << n); S1++){
			for(fint S2 = S1; S2; S2 = (S2 - 1 & S1)){
				fint qwq = getS(S1, S2);
				if(f[qwq] == 0)continue;
				fint T1 = all ^ S1, qwq2 = getS(all, S2);
				for(fint T2 = T1; T2 >= 0; T2 = (T2 - 1 & T1)){
					qk(f3[qwq2], 1ll * f[qwq] * f2[getS(T1, T2)] % mod);
					if(T2 == 0)break;
				}
			}
		}
		fint ans = 0;
		for(fint S = 0; S < (1 << n); S++){
			qk(ans, 1ll * f3[getS(all, S)] * solve(S) % mod);
		}
		cout << ans;
		return 0;
	}
}
signed main(){
    return infinities::main();
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 8ms
memory: 11712kb

input:

4 6 2
7 11 14 0
1 2
1 3
2 3
2 4
4 1
4 3

output:

44

result:

ok 1 number(s): "44"

Test #2:

score: 0
Accepted
time: 3ms
memory: 12088kb

input:

4 4 6
12 14 14 5
4 2
1 4
3 2
1 2

output:

798

result:

ok 1 number(s): "798"

Test #3:

score: 0
Accepted
time: 3ms
memory: 10532kb

input:

3 3 2
10 4 11
2 1
3 2
1 3

output:

33

result:

ok 1 number(s): "33"

Test #4:

score: 0
Accepted
time: 4ms
memory: 10448kb

input:

4 0 4
9 8 5 2

output:

148

result:

ok 1 number(s): "148"

Test #5:

score: 0
Accepted
time: 0ms
memory: 11716kb

input:

5 6 14
12 15 13 13 12
3 1
2 4
2 5
2 1
5 3
4 5

output:

21337

result:

ok 1 number(s): "21337"

Test #6:

score: 0
Accepted
time: 5ms
memory: 11672kb

input:

4 5 5
5 2 4 13
2 1
3 4
1 4
4 2
3 2

output:

42

result:

ok 1 number(s): "42"

Test #7:

score: 0
Accepted
time: 2ms
memory: 12356kb

input:

4 4 3
13 7 8 12
4 1
3 1
2 4
4 3

output:

552

result:

ok 1 number(s): "552"

Test #8:

score: 0
Accepted
time: 3ms
memory: 10724kb

input:

4 2 12
1 12 4 11
2 1
3 1

output:

70

result:

ok 1 number(s): "70"

Test #9:

score: 0
Accepted
time: 3ms
memory: 11676kb

input:

5 5 6
10 7 8 2 13
1 5
1 3
2 1
4 3
5 3

output:

1231

result:

ok 1 number(s): "1231"

Test #10:

score: 0
Accepted
time: 4ms
memory: 10652kb

input:

5 7 9
6 7 13 15 12
1 3
5 3
5 2
4 5
4 3
4 1
3 2

output:

6223

result:

ok 1 number(s): "6223"

Test #11:

score: 0
Accepted
time: 3ms
memory: 12408kb

input:

3 0 3
15 7 12

output:

104

result:

ok 1 number(s): "104"

Test #12:

score: 0
Accepted
time: 3ms
memory: 12152kb

input:

3 2 9
10 6 5
1 2
1 3

output:

17

result:

ok 1 number(s): "17"

Test #13:

score: 0
Accepted
time: 0ms
memory: 12180kb

input:

5 5 11
7 9 15 9 9
5 4
5 1
5 2
1 3
3 4

output:

5224

result:

ok 1 number(s): "5224"

Test #14:

score: 0
Accepted
time: 1ms
memory: 11964kb

input:

5 0 12
9 8 14 11 2

output:

3006

result:

ok 1 number(s): "3006"

Test #15:

score: 0
Accepted
time: 0ms
memory: 11672kb

input:

3 1 1
6 10 4
3 1

output:

30

result:

ok 1 number(s): "30"

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #16:

score: 0
Wrong Answer
time: 6ms
memory: 12400kb

input:

9 27 705410105529944560
929827299070190972 733413770730537329 473007347105710981 190062421504120247 918561152768663129 196040702922254016 981530663192980241 203295856357272834 337150461958783092
2 8
7 9
8 9
2 3
9 2
2 7
9 5
9 4
4 8
1 7
6 3
6 1
4 1
6 5
2 4
2 1
9 3
9 6
7 3
7 5
5 2
4 5
2 6
3 1
3 8
4 3
8 6

output:

-1927956042

result:

wrong answer 1st numbers differ - expected: '5392583', found: '-1927956042'

Subtask #3:

score: 0
Wrong Answer

Test #47:

score: 0
Wrong Answer
time: 982ms
memory: 258444kb

input:

14 0 731833687287532167
157552918690640051 900457311668526045 111217720157614956 84140984111060473 814012186135880499 784848789620248379 958953377683017264 105083874298571687 104921429970878846 44983041675142735 871013110538758030 686733907990421995 98063590462078176 495161493555059993

output:

856699729

result:

wrong answer 1st numbers differ - expected: '231790380', found: '856699729'

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%
English 繁體中文 简体中文

Server Time: 2024-12-02 18:24:32 | OpenSource Project