ამოხსნების სტატუსი

ამ გვერდზე თქვენ იხილავთ გაგზავნილი ამოხსნების სტატუსს.


გაგზავნის თარიღი: 25.07.2019 15:49:07

ამოცანა: ლამაზი მწკრივი

მომხმარებელი: lukamosiashvili

ვერდიქტი: სრული ამოხსნა

შეფასება: 100.0 ქულა







#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,dp[(1<<20)+5][20],f[20],z[24],zi,i,j;
bool bo[23][23];
pair <long long, long long> p[(1<<20)+5];
long long fun2(long long q){
	long long w=0;
	while(q>0){
		if(q%2==1) w++;
		q/=2;
	}
	return w;
}
long long fun3(long long q){
	long long w=0;
	while(q>0){
		if(q%3==1) w++;
		q/=3;
	}
	return w;
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;
	for(b=0; b<a; b++) cin>>f[b];
	for(b=1; b<(1<<a); b++){
		p[b].second=b;
		for(c=0; c<a; c++){
			if((b&(1<<c))!=0) p[b].first++;
		}
	}
	for(b=0; b<a; b++){
		for(c=b+1; c<a; c++){
			if(fun2(f[b])==fun2(f[c])||fun3(f[b])==fun3(f[c])){
				bo[b][c]=1;
				bo[c][b]=1;
			}
		}
	}
	sort(p+1,p+a+1);
	for(b=1; b<(1<<a); b++){
		zi=0;e=p[b].second;
		for(i=0; i<a; i++){
			if((e&(1<<i))!=0){
				zi++;
				z[zi]=i;
			}
		}
		if(p[b].first==1){
		    dp[p[b].second][z[1]]=1;
		}
		for(i=1; i<=zi; i++){
			d=e-(1<<z[i]);
			for(j=1; j<=zi; j++){
				if(z[i]==z[j]||bo[z[i]][z[j]]==0) continue;
				dp[e][z[i]]+=dp[d][z[j]];
			}
		}
	}
	d=0;
	for(i=0; i<a; i++){
		d+=dp[(1<<a)-1][i];
	}
	cout<<d;
	return 0;
}

ტესტები

შემავალი მონაცემები
2
1 2
გამომავალი მონაცემები
2
თქვენი პასუხი
2
ჩეკერის პასუხი
YES
შემავალი მონაცემები
3
100 3 6
გამომავალი მონაცემები
0
თქვენი პასუხი
0
ჩეკერის პასუხი
YES
შემავალი მონაცემები
4
1 2 3 4
გამომავალი მონაცემები
4
თქვენი პასუხი
4
ჩეკერის პასუხი
YES
შემავალი მონაცემები
4
1 2 4 8
გამომავალი მონაცემები
24
თქვენი პასუხი
24
ჩეკერის პასუხი
YES
შემავალი მონაცემები
4
1 3 8 12
გამომავალი მონაცემები
2
თქვენი პასუხი
2
ჩეკერის პასუხი
YES
შემავალი მონაცემები
10
605 848 765 201 111 462 572 596 329 41
გამომავალი მონაცემები
5712
თქვენი პასუხი
5712
ჩეკერის პასუხი
YES
შემავალი მონაცემები
10
616 921 861 976 870 37 920 251 972 478
გამომავალი მონაცემები
40
თქვენი პასუხი
40
ჩეკერის პასუხი
YES
შემავალი მონაცემები
10
1 2 4 8 16 32 64 128 256 512
გამომავალი მონაცემები
3628800
თქვენი პასუხი
3628800
ჩეკერის პასუხი
YES
შემავალი მონაცემები
10
263 615 49 686 279 465 945 229 945 186
გამომავალი მონაცემები
1904
თქვენი პასუხი
1904
ჩეკერის პასუხი
YES
შემავალი მონაცემები
10
17564002 134267298 153749520 235931780 294453256 33570834 419441168 272911104 4243561 167839268
გამომავალი მონაცემები
1209600
თქვენი პასუხი
1209600
ჩეკერის პასუხი
YES
შემავალი მონაცემები
14
17305765 252182912 152573984 18187296 311601 265236 134258801 13680657 9601059 338067520 8536835 206635056 273776708 737428
გამომავალი მონაცემები
5748019200
თქვენი პასუხი
5748019200
ჩეკერის პასუხი
YES
შემავალი მონაცემები
14
272777408 67672068 4211284 77856928 42205195 33571025 67649603 101222401 68166673 39846658 18878499 8429792 136323174 134365222
გამომავალი მონაცემები
958003200
თქვენი პასუხი
958003200
ჩეკერის პასუხი
YES
შემავალი მონაცემები
16
134480040 69476416 16860161 51118084 16982020 802945 4272192 67403968 4360256 8798212 10764296 17154048 69210400 790816 268534788 77611008
გამომავალი მონაცემები
1046139494400
თქვენი პასუხი
1046139494400
ჩეკერის პასუხი
YES
შემავალი მონაცემები
18
44367872 142884868 134218836 4458240 11016192 76812288 407896080 2130116 796164 6307857 134743584 2132097 65641 235159552 272762912 218398784 2168960 301992449
გამომავალი მონაცემები
50214695731200
თქვენი პასუხი
50214695731200
ჩეკერის პასუხი
YES
შემავალი მონაცემები
18
71827720 140548 35734016 2105617 134498816 268440081 1116736 67181056 37224450 37748836 16785929 140509441 73400848 38273033 269746436 134250593 9716736 8421984
გამომავალი მონაცემები
6402373705728000
თქვენი პასუხი
6402373705728000
ჩეკერის პასუხი
YES
შემავალი მონაცემები
18
33816580 140525568 285212673 75628544 132608 65584 66080 1081472 134483968 524416 589825 276824065 1065984 67108884 33554440 150994952 20987904 4718596
გამომავალი მონაცემები
1879602278400
თქვენი პასუხი
1879602278400
ჩეკერის პასუხი
YES
შემავალი მონაცემები
18
18087936 74368 262657 2098312 75497504 37756928 134221828 6815744 67158016 2129924 2115584 2130944 68190208 2106368 528384 10248 16908800 2621504
გამომავალი მონაცემები
63965873664000
თქვენი პასუხი
63965873664000
ჩეკერის პასუხი
YES
შემავალი მონაცემები
18
135274496 2131969 2088 3277312 270536704 100794368 10493952 33688064 327824 131232 12320 134218880 17072128 136314912 134217802 1065088 4325384 134742080
გამომავალი მონაცემები
255786854400
თქვენი პასუხი
255786854400
ჩეკერის პასუხი
YES
შემავალი მონაცემები
20
68681728 2097200 2065 54525952 1048612 4195584 167772168 13631504 270549056 16656 51200 272384 301991936 34603136 42008592 4176 4211200 5632 8464 2084
გამომავალი მონაცემები
18840972294144000
თქვენი პასუხი
18840972294144000
ჩეკერის პასუხი
YES
შემავალი მონაცემები
20
34604032 83886084 268763136 134758400 1568 75505664 9224 85983232 45056 4210704 526848 34078722 51200 34603520 268697604 75513856 134219777 134348808 33554512 1097728
გამომავალი მონაცემები
2432902008176640000
თქვენი პასუხი
2432902008176640000
ჩეკერის პასუხი
YES