題目的要求重新表述如下：給定數列 a[1], a[2], ... a[n], 尋找一段連續的序列[L, R]，使得 (a[L] + a[L + 1] + ... + a[R]) mod P = 0。求最長的序列，即R-L的最大值，無解輸出1。
首先引入前綴和(Prefix Sum)的概念：
定義 sum[i] = (a[1] + a[2] +... + a[i]) 稱為i位置的前綴和。 (1 <= i <= n)，特別的有sum[0] = 0。那么如果某段連續的[L, R]滿足條件，即元素之和為P的倍數，那么一定有以下結論成立：
(sum[R] - sum[L - 1]) % P = 0，易證此條件是充要的。
換言之，問題變為，求相隔最遠的L和R，滿足 sum[L - 1] 和 sum[R]在模P域下相等，即sum[L - 1] % P == sum[R] % P。

(1 <= L <= R <= n)由于P很小，不超過11，我們開一個長度為P的數組front[P] 和 rear[P],?front[i]代表最小的下標x，使得sum[x] % P = i，rear[i]則代表最大的下標x滿足相同的條件。
當i！=0時，并且（rear[i]&&front[i])都有值，則余數為i的最長連續序列個數為rear[i]-front[i];
如果i==0時的最大長度是c【i】；最后枚舉從（0——m-1）個余數，記最大的情況即可； ???????

#include"stdio.h"
#include"string.h"
int main()
{
?int m,n,i,k,h,sum,max;
?int b[12],c[12];
?scanf("%d",&k);
?while(k--)
?{
??scanf("%d%d",&n,&m);
??memset(b,-1,sizeof(b));
??memset(c,-1,sizeof(c));
??sum=0;max=1;
??for(i=1;i<=n;i++)
??{
???scanf("%d",&h);
???sum+=h;
???sum=sum%m;
???if(b[sum]==-1)
????b[sum]=i;
????c[sum]=i;
??}
??for(i=0;i<m;i++)
??{
???if(i==0&&c[i]!=-1)
???{
????? if(max<c[i])
?????max=c[i];
???}
???? ?else if(b[i]&&c[i])
???{????
???? ????? if(max<c[i]-b[i])
??????????? max=c[i]-b[i];
???}
??}
???printf("%d\n",max);
?}
?return 0;
}

總結

以上是生活随笔為你收集整理的uestc 1901 方方是个坏孩子的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。