## Editorial for Dãy con dài nhất có tổng chia hết cho K

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

var n,i,k,t,j,p:longint;
f:array[0..1,0..51] of longint;

begin
fillchar(f,sizeof(f),0);
f[0,0]:=1;
for i:=1 to n do
begin
p:=i mod 2;
for j:=0 to k-1 do f[p,j]:=0;
for j:=0 to k-1 do
if (f[1-p,j]>0) then
begin
if (f[p,j]<f[1-p,j]) then
f[p,j]:=f[1-p,j];
if (f[p,(j+t) mod k]<=f[1-p,j]) then
f[p,(j+t) mod k]:=f[1-p,j]+1;
end;
end;
write(f[p,0]-1);
end.


#### Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long LL;

#define sz(a) (int((a).size()))
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 1005
#define KK 55

int f[N][KK], n, k, a[N];

int main() {
#ifndef ONLINE_JUDGE
freopen( "input.txt", "r", stdin );
//freopen( "output.txt", "w", stdout );
#endif
LL s = 0;
scanf("%d%d",&n,&k);
fo(i,1,n) { scanf("%d",a+i); s = (s+a[i])%k; }
//f[i][j], chon ra it nhat f[i][j] phan tu trong doan a[1..i] de co tong chia k du i
f[0][0] = 0; fo(i,1,k-1) f[0][i] = INF;
fo(i,1,n) rep(j,k)
f[i][j] = min(f[i-1][j], f[i-1][((j-a[i])%k+k)%k]+1);
printf("%d\n", n-f[n][s%k]);
return 0;
}


program qbseq;
uses    math;
const   fi='';
var     f:array[0..1001,0..51] of longint;
a:array[1..1000] of longint;
inp:text;
n,i,k:longint;
check:array[0..1001,0..51] of boolean;
procedure input;
var     i:longint;
begin
assign(inp,fi);
reset(inp);
for i:=1 to n do
close(inp);
end;

function qhd(i,t:longint):longint;

begin
if check[i,t] then exit(f[i,t]);
f[i,t]:=max(qhd(i-1,t),1+qhd(i-1,(t+k-(a[i] mod k)) mod k));
check[i,t]:=true;
exit(f[i,t]);
end;

begin
input;
f[0,0]:=0;
check[0,0]:=true;
for i:=1 to k-1 do
begin
f[0,i]:=low(integer);
check[0,i]:=true;
end;
write(qhd(n,0));
end.


#### Code mẫu của RR

uses math;
var
a:array[1..1011] of longint;
f:array[1..1011,0..50] of longint;
next,n,k,i,j:longint;
begin
for i:=1 to n do read(a[i]);

fillchar(f,sizeof(f),\$FF);
f[1,0]:=0;
f[1,a[1] mod k]:=1;

for i:=2 to n do
begin
for next:=0 to k-1 do
f[i,next]:=f[i-1,next];

for j:=0 to k-1 do
if f[i-1,j]>=0 then
begin
next:=(j+a[i]) mod k;
f[i,next]:=max(f[i,next],f[i-1,j]+1);
end;
end;

writeln(f[n,0]);
end.


#### Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
main()
{ int n,k,a[1001],b[1001][51],m,l;
long x=0;
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
{ scanf("%d",&a[i]);
a[i]= a[i]%k ;
x+=a[i];
}
m=x%k ;
if(m==0)
printf("%d",n);
else
{
for(int i=0;i<k;i++)
b[0][i]=1001;
for(int i=1;i<=n;i++)
{ for(int j=0;j<k;j++)
{ if(j!=a[i])
{ l=j-a[i];
if(l<0)
l=l+k;
if(b[i-1][l]+1>=b[i-1][j])
b[i][j]=b[i-1][j];
else b[i][j]=b[i-1][l]+1;
}
else  b[i][j]=1;
}
}
printf("%d",n-b[n][m]);
}
//getch();
}


#### Code mẫu của ll931110

Program QBSEQ;
Const
input  = '';
output = '';
max = 1000000000;
Var
a: array[1..1000] of longint;
F: array[0..1000,0..1000] of longint;
n,k: longint;

Procedure enter;
Var
fi: text;
i: longint;
Begin
Assign(fi, input);
Reset(fi);
For i:= 1 to n do read(fi, a[i]);
Close(fi);
End;

Function sub(x,y: longint): longint;
Var
tmp: longint;
Begin
sub:= (x - y) mod k;
If sub < 0 then sub:= sub + k;
End;

Function min(x,y: longint): longint;
Begin
If x < y then exit(x) else exit(y);
End;

Procedure optimize;
Var
i,t: longint;
Begin
F[0,0]:= 0;
For t:= 1 to k - 1 do F[0,t]:= max;

For i:= 1 to n do
For t:= 0 to k - 1 do
F[i,t]:= min(F[i - 1,t], F[i - 1, sub(t, a[i])] + 1);
End;

Procedure solve;
Var
fo: text;
sum,i: longint;
Begin
sum:= 0;
For i:= 1 to n do sum:= sum + a[i];

Assign(fo, output);
Rewrite(fo);
Writeln(fo, n - F[n, sum mod k]);
Close(fo);
End;

Begin
enter;
optimize;
solve;
End.


#### Code mẫu của skyvn97

#include<stdio.h>
int opt[2000][100];
int a[2000];
int n,k,i,j,s;
int f(int x)
{
if (x>=0) return (x);
return (x+k);
}
int min(int a,int b)
{
if (a<b) return (a); else return (b);
}
int main(void)
{
scanf("%d",&n);
scanf("%d",&k);
s=0;
for (i=1;i<=n;i=i+1)
{
scanf("%d",&a[i]);
a[i]=a[i]%k;
s=(s+a[i])%k;
}
opt[0][0]=0;
for (i=1;i<k;i=i+1) opt[0][i]=32000;
for (i=1;i<=n;i=i+1)
for (j=0;j<k;j=j+1)
opt[i][j]=min(opt[i-1][j],opt[i-1][f(j-a[i])]+1);
printf("%d",n-opt[n][s%k]);
return 0;
}


#### Code mẫu của khuc_tuan

#include <stdio.h>
#include <iostream>
#include <set>
using namespace std;

int n, k;
int f1[55], f2[55];

int main() {
scanf("%d%d", &n, &k);
int *f = f1, *q = f2;
for(int i=0;i<55;++i) f1[i] = -1000000;
f1[0] = 0;
for(int i=0;i<n;++i) {
int x; scanf("%d", &x);
for(int j=0;j<55;++j) q[j] = -1000000;
for(int du=0;du<k;++du) q[(du+x)%k] >?= (f[du]+1) >? (f[(du+x)%k]);
swap( f, q);
}
printf("%d\n", f[0]);
return 0;
}