1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include <array>
#include <bitset>
#include <iostream>
#include <string>

using namespace std;

struct Kosc {
	int promien;
	string srodek;
};

const int L_KUL = 3;
const int L_PRZEDZ = 4;
const int MODULO = 1e9 + 7;

struct Tresc {
	int l_bitow;
	array< Kosc, L_KUL > kostki;
};

Tresc wczytaj_tresc( istream& istr ) {
	Tresc t;
	istr >> t.l_bitow;
	for ( int i = 0; i < L_KUL; ++i ) {
		istr >> t.kostki[i].promien;
		istr >> t.kostki[i].srodek;
	}
	return t;
}

int ustawione_bity(uint32_t i)
{
 	i = i - ((i >> 1) & 0x55555555);
	i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
	return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

int roznica_bitow( uint32_t const a, uint32_t b) {
	return ustawione_bity( a ^ b );
}

unsigned bity_na_liczbe( string const& s) {
	bitset< 32 > bs(s);
	return bs.to_ulong();
}

int kulo_brut( Tresc const& t ) {
	int wynik = 0;

	array< int, L_KUL > kulki;
	for( int i = 0; i < L_KUL; ++i ) {
		kulki[i] = bity_na_liczbe( t.kostki[i].srodek );
	}

	int maks = (1 << t.l_bitow);

	/* przejdz caly zakres */
	for( int i = 0; i < maks; ++i ) {
		/* sprawdz kazda kule */
		for( unsigned k = 0; k < L_KUL; ++k ) {
			int roznica = roznica_bitow( kulki[k], i );
			if( roznica <= t.kostki[k].promien ) {
				wynik += 1;
				k = L_KUL; // break
			}
		}
	}

	return wynik;
}

struct Dane {
	array< int, L_KUL > promienie = { 0, 0, 0 };
	array< int, L_PRZEDZ > przedzialy = { 0, 0, 0, 0 };
	int wymiary;
};

Dane uprosc_tresc( Tresc const& t ) {
	/*
		nastepujace operacje nie zmieniaja wyniku
		- przestawienie wybranego bitu we wszystkich kulach
		- zamiana pozycji dwoch wybranych bitow we wszystkich kulach

		to pozwala zapisac kule w postaci
		0000000000000000000000 (same zera)
		0000000000000111111111 (zera potem jedynki)
		0000000001111000001111 (zera jedynki zera jedynki)

		Mamy zatem
		4 liczby okreslajace dlugosci przedzialow
		3 liczby okreslajace promienie
	*/

	Dane dn;
	for( int i = 0; i < L_KUL; ++i ) {
		dn.promienie[i] = t.kostki[i].promien;
	}

	for( int i = 0; i < t.l_bitow; ++i ) {
		char zero = t.kostki[0].srodek[i];
		string mask = { t.kostki[1].srodek[i], t.kostki[2].srodek[i] };
		int p = bity_na_liczbe( mask );

		if( zero == '1' ) {
			p = (p ^ 0x3);
		}
		dn.przedzialy[p] += 1;
	}

	dn.wymiary = t.l_bitow;
	return dn;
};

long long niecala_silnia( long long k, long long n ) {
	long long w = 1;
	for ( long long i = max( k, 1LL); i <= n; ++i ) {
		w *= i;
		w %= MODULO;
	}
	return w;
};

long long n_po_k( long long n, long long k ) {
	return (
		niecala_silnia( n - k + 1, n )
		/
		niecala_silnia(1, k)
	);
}

long long suma_n_po_k( long long n, long long k ) {
	long long wynik = 0;
	for( long long i = 0; i <= k; ++i ) {
		wynik += n_po_k( n, i );
		wynik %= MODULO;
	}
	return wynik;
}

int ilo2( Dane const& dn, int skip ) {
	// to jeszcze bym wiedzial...
	return 0;
}

int ilo3( Dane const& dn ) {
	// ale tu utknalem...
	return 0;
}

long long objetosc_kuli( int wymiary, int r ) {
	return suma_n_po_k(wymiary, r);
}

int oblicz_ze_wzoru( Dane const& dn ) {
	int wynik = 0;

	for( int i = 0; i < L_KUL; ++i ) {
		wynik += objetosc_kuli( dn.wymiary, dn.promienie[i] );
	}

	for( int i = 0; i < L_KUL; ++i ) {
		wynik -= ilo2( dn, i );
	}

	wynik += ilo3( dn );

	return wynik;
}

int kulo_wzor( Tresc const& t ) {
	Dane dn = uprosc_tresc( t );
	return oblicz_ze_wzoru( dn );
}

int main() {
	Tresc t = wczytaj_tresc(cin);

	if( t.l_bitow <= 31 ) {
		cout << kulo_brut( t ) << "\n";
	}
	else {
		cout << kulo_wzor( t ) << "\n";
	}
}