题目描述

Farmer John's N cows (1 <= N <= 100,000) share many similarities. In fact, FJ has been able to narrow down the list of features shared by his cows to a list of only K different features (1 <= K <= 30). For example, cows exhibiting feature #1 might have spots, cows exhibiting feature #2 might prefer C to Pascal, and so on. FJ has even devised a concise way to describe each cow in terms of its "feature ID", a single K-bit integer whose binary representation tells us the set of features exhibited by the cow. As an example, suppose a cow has feature ID = 13. Since 13 written in binary is 1101, this means our cow exhibits features 1, 3, and 4 (reading right to left), but not feature 2. More generally, we find a 1 in the 2^(i-1) place if a cow exhibits feature i. Always the sensitive fellow, FJ lined up cows 1..N in a long row and noticed that certain ranges of cows are somewhat "balanced" in terms of the features the exhibit. A contiguous range of cows i..j is balanced if each of the K possible features is exhibited by the same number of cows in the range. FJ is curious as to the size of the largest balanced range of cows. See if you can determine it. --我也懒得翻译了....-- N(1<=N<=100000)头牛，一共K(1<=K<=30)种特色， 每头牛有多种特色，用二进制表示它的特色序列。比如当牛的特征值为13，他的特色序列为1101， 则它有第1、3、4种特色。[i,j]段被称为牛平衡组.姑且这么称呼吧.... 当且仅当K中特色中，每种特色在[i,j]内拥有次数相同。求最大的[i,j]段长度。 说白了就是让你求一大串二进制表里面，从i行到第j行所有的二进制位对应数(0或1)相加后，整整一行表示出来每一位的值都相等。详见最后的提示... 顺便提醒注意内存和时间限制 ##不懂的话泥萌直接来问我吧....BY FmuckssXTT

输入格式

• Line 1: Two space-separated integers, N and K. ###第1行:N和K
• Lines 2..N+1: Line i+1 contains a single K-bit integer specifying the features present in cow i. The least-significant bit of this integer is 1 if the cow exhibits feature #1, and the most-significant bit is 1 if the cow exhibits feature #K. ###第2~N+1行: 第N-1行:第N头牛的特征值。 再次提醒时间和内存限制...

输出格式

• Line 1: A single integer giving the size of the largest contiguous balanced group of cows. ###只有一行，为一个最长的牛平衡组..

样例

####输入样例

7 3
7
6
7
2
1
4
2

####输出样例

4

数据范围与提示

The line has 7 cows with 3 features; the table below summarizes the correspondence: 对于样例，每行有七头三种特色的牛，如图所示(请将屏幕旋转90度或把脖子反向旋转90度..)

Key:         7   6   7   2   1   4   2  

              Cow #:       1   2   3   4   5   6   7  

              Feature 3:   1   1   1   0   0   1   0

              Feature 2:   1   1   1   1   0   0   1

              Feature 1:   1   0   1   0   1   0   0

In the range from cow #3 to cow #6 (of size 4), each feature appears in exactly 2 cows in this range:

Feature 3:     1   0   0   1  -> 2

              Feature 2:     1   1   0   0  -> 2

              Feature 1:     1   0   1   0  -> 2

              Key:           7   2   1   4 

              Cow #:         3   4   5   6

最后再提醒时间和内存限制...重要的事说三遍 USACA07 MAR GOLD