Subtask ~1~ ~(40\%)~: ~N = 2~:

Lúc này chỉ có hai đứa trẻ, bài toán trở thành tìm số lượng cặp số ~(i,j)~ ~(0\le i \le A_1, 0\le j \le A_2)~ sao cho ~i+j=K~.

Code tham khảo

void Solve1() {
    long long cnt=0;

    for(int i=1;i<=min(k,a[1]);i++)
        if(k-i<=a[2])
            cnt++;

    cout<<cnt;
}

Độ phức tạp : ~\mathcal{O}(K^{N-1})~

Subtask ~2~ ~(40\%)~: ~1 \le K \le 500~.

Gọi ~dp_{i,j}~ là số cách chia kẹo cho ~i~ đứa trẻ khi có ~j~ viên kẹo. ~(1\le i \le N, 0\le j \le K)~

Nhận xét:

• Đứa trẻ thứ ~i~ khi có ~j~ viên kẹo chỉ lấy được trong phạm vi từ ~0~ tới ~min(A_i,j)~.
• Ở ô ~dp_{i,j}~, nếu đứa trẻ thứ ~i~ lấy ~0~ viên kẹo thì để đủ ~j~ viên kẹo như được định nghĩa từ trước, nó phải kết hợp với số cách ở ô ~dp_{i-1,\ j}~ (số cách chia kẹo cho đứa trẻ thứ ~i-1~ khi có ~j~ viên kẹo). Tương tự:
  • Nếu đứa trẻ thứ ~i~ lấy ~1~ viên, nó phải kết hợp với số cách ở ô ~dp_{i-1,\ j-1}~.
  • Nếu đứa trẻ thứ ~i~ lấy ~2~ viên, nó phải kết hợp với số cách ở ô ~dp_{i-1,\ j-2}~.
  • ~\dots~
  • Nếu đứa trẻ thứ ~i~ lấy ~min(A_i,j)~ viên, nó phải kết hợp với số cách ở ô ~dp_{i-1,\ j-min(A_i,j)}~. (*)
• Kết quả là ô ~dp_{n,k}~.

Code tham khảo

void Solve2() {
    dp[0][0]=1;
    for(int i=1;i<=min(k,a[1]);i++)
        for(int j=0;j<=k;j++)
            for(int x=0;x<=min(a[i],j);x++)
                dp[i][j]=(dp[i][j]+dp[i-1][j-x])%mod;
    cout<<dp[n][k];
}

Độ phức tạp : ~\mathcal{O}(N \cdot K^2)~.

Lưu ý: Với độ phức tạp này, bạn cần code riêng trường hợp cho subtask ~1~ để dành trọn ~80 \%~.

Subtask ~3~ ~(20\%)~

Nhận thấy rằng, ở nhận xét (*) tổng của đoạn này liên tiếp và không thay đổi giá trị trong quá trình tính toán nên ta có thể dễ dàng tiền xử lí để giảm độ phức tạp. Tạo mảng ~pre~ là mảng cộng dồn của hàng ~i-1~ và khi này tổng của đoạn ~[j-min(A_i,j);j]~ là ~pre_j-pre_{j-min(A_i,j)-1}~.

Code tham khảo

void Solve() {
    dp[0][0]=1;

    for(int i=1;i<=n;i++)
    { 
        pre[0]=1;
        for(int j=1;j<=k;j++)
            pre[j]=pre[j-1]+dp[i-1][j]; //tiền xử lí hàng i-1
        for(int j=1;j<=k;j++)
            if(j-a[i]<=0)
                dp[i][j]=(pre[j]-pre[0]+1)%mod;
            else
                dp[i][j]=(pre[j]-pre[j-a[i]-1])%mod;
    }

    cout<<dp[n][k];
}

Độ phức tạp : ~\mathcal{O}(N \cdot K \cdot 2)~.