#include <cstdio> const int max_n = 10001; long long int p = 1000000007LL; long long int brute_force_check(int n, unsigned long long int s1, unsigned long long int s2, unsigned long long int s3, int r1, int r2, int r3) { long long int result = 0LL; for (unsigned long long int i = 0ULL; i < (1ULL << n); i++) { int d1 = n - (__builtin_popcount(i & s1) + __builtin_popcount((~i) & (~s1) & ((1 << n) - 1))); int d2 = n - (__builtin_popcount(i & s2) + __builtin_popcount((~i) & (~s2) & ((1 << n) - 1))); int d3 = n - (__builtin_popcount(i & s3) + __builtin_popcount((~i) & (~s3) & ((1 << n) - 1))); if (d1 <= r1 || d2 <= r2 || d3 <= r3) { result++; } } return result; } int main() { int n, r[3]; char s[3][max_n]; scanf("%d", &n); for (int i = 0; i < 3; i++) { scanf("%d", &r[i]); scanf("%s", &s[i][0]); } unsigned long long int s_int[3]; s_int[0] = s_int[1] = s_int[2] = 0; for (int i = 0; i < n; i++) { s_int[0] |= (((s[0][i] == '0') ? 0ULL : 1ULL) << i); s_int[1] |= (((s[1][i] == '0') ? 0ULL : 1ULL) << i); s_int[2] |= (((s[2][i] == '0') ? 0ULL : 1ULL) << i); } printf( "%lld\n", brute_force_check(n, s_int[0], s_int[1], s_int[2], r[0], r[1], r[2]) % p); return 0; }
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 | #include <cstdio> const int max_n = 10001; long long int p = 1000000007LL; long long int brute_force_check(int n, unsigned long long int s1, unsigned long long int s2, unsigned long long int s3, int r1, int r2, int r3) { long long int result = 0LL; for (unsigned long long int i = 0ULL; i < (1ULL << n); i++) { int d1 = n - (__builtin_popcount(i & s1) + __builtin_popcount((~i) & (~s1) & ((1 << n) - 1))); int d2 = n - (__builtin_popcount(i & s2) + __builtin_popcount((~i) & (~s2) & ((1 << n) - 1))); int d3 = n - (__builtin_popcount(i & s3) + __builtin_popcount((~i) & (~s3) & ((1 << n) - 1))); if (d1 <= r1 || d2 <= r2 || d3 <= r3) { result++; } } return result; } int main() { int n, r[3]; char s[3][max_n]; scanf("%d", &n); for (int i = 0; i < 3; i++) { scanf("%d", &r[i]); scanf("%s", &s[i][0]); } unsigned long long int s_int[3]; s_int[0] = s_int[1] = s_int[2] = 0; for (int i = 0; i < n; i++) { s_int[0] |= (((s[0][i] == '0') ? 0ULL : 1ULL) << i); s_int[1] |= (((s[1][i] == '0') ? 0ULL : 1ULL) << i); s_int[2] |= (((s[2][i] == '0') ? 0ULL : 1ULL) << i); } printf( "%lld\n", brute_force_check(n, s_int[0], s_int[1], s_int[2], r[0], r[1], r[2]) % p); return 0; } |