LQDRECT - Đếm hình chữ nhật

Tác giả: hieult

Ngôn ngữ: C++

#pragma comment(linker, "/STACK:16777216")

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000001
#define maxn 2002
#define base 1000000000
#define modunlo 111539786
#define oo 1000000002
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define ull unsigned long long
#define fi first
#define se second

double const PI=4*atan(1);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

typedef long long int64;

int f[1<<16], the, a[333][111], d[1011][311], t, so;
int n,m;

int main(){
   // freopen("input.in","r",stdin);
   // freopen("output.out","w",stdout);
    
    for(int i = 0; i < (1<<16); i ++){
        the = i;
        f[i] = 0;
        for(int j = 0; j < 16; j++){
            f[i] += (the & 1);
            the >>= 1;
        }
    }
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) scanf("%d",&d[i][j]);
    int run;
    for(int i = 1; i <= m; i++){
        so = 0;
        run = 0;
        for(int j = 1; j <= n; j++){
            so = so * 2 + d[j][i];
            if(j % 16 == 0 || j == n){
                a[i][++run] = so;
                so = 0;
            }
        }
    }
    
 //   printf("%d\n",run);
    
    long long kq = 0, tinh;
    for(int i = 1; i <= m; i++) for(int j = i + 1; j <= m; j++){
        tinh = 0;
        for(int k = 1; k <= run; k++) tinh += f[a[i][k]&a[j][k]];
       // printf("%d %d %d\n",i,j,a[i][1]&a[j][1]);
        kq += tinh * (tinh - 1) / 2;
    }
    printf("%lld",kq);
    
}

Download