/* 64位的位运算！！！ 题意： 给定一个01矩阵。T个询问，每次询问大矩阵中是否存在这个特定的小矩阵。 （64位记录状态！！！） */ #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int64; //typedef __int64 int64; typedef pair PII; #define MP(a,b) make_pair((a),(b)) const int maxn = 1005; const int maxm = 55; const int inf = 0x7fffffff; const double pi=acos(-1.0); const double eps = 1e-8; char mat[ maxn ][ maxn ]; char tmp[ maxm ][ maxm ]; int64 A[ maxn ][ maxn ]; int64 AA[ maxm ]; int64 sum[ maxn ][ maxn ]; void init( int n,int m,int p,int q ){ for( int i=0;i<=m;i++ ) sum[0][i] = 0; for( int i=0;i<=n;i++ ) sum[i][0] = 0; for( int i=1;i<=n;i++ ){ for( int j=1;j<=m;j++ ){ sum[ i ][ j ] = sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]; if( mat[i][j]=='*' ) sum[i][j] ++; } } memset( A,0,sizeof( A ) ); for( int i=1;i<=n;i++ ){ for( int j=1;j<=q;j++ ){ if( mat[i][j]=='*' ) A[i][q] |= ((1LL)<<(j-1)); } } for( int i=1;i<=n;i++ ){ for( int j=q+1;j<=m;j++ ){ if( mat[i][j-q]=='*' ) A[i][j] = A[i][j-1]-(1LL); else A[i][j] = A[i][j-1]; A[i][j] = A[i][j]>>(1LL); if( mat[i][j]=='*' ) A[i][j] |= ((1LL)<<(q-1)); } } } void GetBinary( int p,int q ){ for( int i=1;i<=p;i++ ){ AA[ i ] = 0; for( int j=1;j<=q;j++ ){ if( tmp[i][j]=='*' ) AA[ i ] |= ((1LL)<<(j-1)); } } } int Judge( int n,int m,int p,int q,int64 cnt ){ for( int i=1;i+p-1<=n;i++ ){ if( sum[n][m]-sum[i-1][m]