CODE của em đây: http://ideone.com/nPjhWA
Thuật toán:
B1: Tính a[i] là tổng từ 1 đến i.
B2: Kiểm tra a[n] có chia hết cho k không. Nếu có: Chia làm 2 trường hợp
XL1: TH: a[n]=0: Đi đếm tất cả những vị trí có tổng =0 (s[k]) . Khi đó dùng res= tổ hợp chập k-1 của s[k]-1.
XL: TH: a[n]<>0: đặt h=a[i] div m với m=a[n] div k và a[i] mod m=0.
Gọi s[h] là số đoạn chia được làm h phần. -> res=s[k-1];
Bạn thử trường hợp số 0 chưa?
đào đào
Em bị WA. Và khi em đăng code hỏi bài thì em nên nói sơ cả thuật toán, vì người khác rất ngại đọc code, và có đọc cũng khó mà hiểu được khi code không chú thích gì cả.
Dạ. Để em bổ sung. Anh cho em hỏi WA test nào ạ?
TH tổng của đoạn từ a[j]->a[i]=0 trong TH1 của em hả anh?
Em sai TH tổng các phần tử bằng 0, cụ thể hơn thì anh cũng không rõ do không hiểu thuật toán của em.
Em làm giống như ý tưởng của anh onlylove97:
Chia làm 2 trường hợp:
+)Nếu tổng N số bằng 0
Gọi dem là số các vị trí i thỏa mãn tổng các số từ 1->i bằng 0
->Kết quả bài toán là C(dem-1,k-1).
+) Nếu tổng N số khác 0 và chia hết cho k
Gọi Sum[i]=A1+A2+...+Ai
Đặt s=Sum[n]/k (tính tổng của một đoạn :D )
Gọi ans[i] là số cách chia mảng thành i+1 đoạn có tổng bằng nhau
->ans[0]=1.
Giả sử đang xét tới vị trí i và Sum[i] chia hết cho s
->đặt t=Sum[i]/s.
->f[t]=f[t]+f[t-1].
Kết quả bài toán là f[k-1].
+) Ngược lại, kết quả bài toán bằng 0.
