Editorial for Bedao Grand Contest 10 - MILKTEA


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.

Author: bedao

Từ đây đến cuối bài ta sẽ gọi ~\%~ là phép chia lấy dư.

Subtask 2

~dp[0][i] = 0~ ~(0 < i < n)~

~dp[0][0] = 1~

~dp[i][sum] = dp[i-1][sum] + dp[i-1][(sum-i)\%n]~

Kết quả là ~dp[n\times k][0]~.

Độ phức tạp: ~O(n^2\times k)~.

Subtask 3

Ta thấy vì mọi ngày Naot đều uống trà sữa như nhau; nên có thể gọi ~c_i = dp[n][i]~, khi đó xét đa thức:

~P(x)=(c_0\times x^0+c_1\times x^1+....+c_{n-1}\times x^{n-1})^k~

Đáp án sẽ là ~\sum_{i=0}^{k-1} h_{i\times n}~ với ~h_j~ là hệ số của ~x^j~ trong ~P~. Theo đó ta có thể thực hiện nhân đa thức sử dụng chia để trị để tính ~P~; nhằm tối ưu hóa thuật toán, khi nhân hai đa thức, ta viết ~h_{i \% n}~ thay cho ~h_i~.

Độ phức tạp: ~O(n^2 \times logk)~

Subtask 4

Gọi ~A\left(x\right)=\left[\left(1+x^0\right)\left(1+x^1\right)\dots\left(1+x^{n-1}\right)\right]^k = a_0x^0+a_1x^1+a_2x^2+\dots+a_nx^n+\dots~

Dễ thấy rằng ~a_i~ là số subset con có tổng bằng ~i~. Bài toán yêu cầu ta tính tổng các ~a_i~ với ~i~ là bội của ~n~.

Gọi ~\zeta_n~ là nghiệm đơn vị nguyên thủy cấp ~n~ (primitive ~n~th root of unity). Ta xét biểu thức sau:

~\sum_{i=1}^nA(\zeta_n^i)=a_0\sum_{i=1}^n\zeta_n^{0\times i} + a_1\sum_{i=1}^n\zeta_n^{1\times i}+a_2\sum_{i=1}^n\zeta_n^{2\times i}+\dots+a_n\sum_{i=1}^n\zeta_n^{n\times i}+\dots~

~=a_0\sum_{i=1}^n1 + a_1\sum_{i=1}^n\zeta_n^{ i}+a_2\sum_{i=1}^n\zeta_n^{2i}+\dots+a_n\sum_{i=1}^n1+\dots~

~=n(a_0+a_n+a_{2n}+\dots)+a_{1+nj}\sum_{i=1}^{n}\zeta_n^i+a_{2+nj}\sum_{i=1}^{n}\zeta_n^{2i}+\dots+a_{(n-1)+nj}\sum_{i=1}^{n}\zeta_n^{(n-1)i}\,\,\,(j \text{ là số nguyên})~

~=n(a_0+a_n+a_{2n}+\dots) + 0 + 0 +\dots + 0~

Từ biểu thức này ta thấy kết quả chúng ta cần tìm là: ~\frac{1}{n}\sum_{i=1}^nA(\zeta_n^i)~

Từ đây ta chỉ cần tìm cách tính ~A(\zeta_n^i)~.

Dễ thấy ở trường hợp đơn giản nhất, ~A(\zeta_n^n)=A(1)=\left[\left(1+1^0\right)\left(1+1^1\right)\dots\left(1+1^{n-1}\right)\right]^k = 2^{nk}~

Ta có nhận xét ~\zeta_n^{i\times j}~ với ~i~ cố định và ~j~ chạy từ ~1~ đến ~n~ thì ~\zeta_n^{i\times j}~ sẽ phân bố đều vào nghiệm đơn vị cấp ~n/gcd(n, i)~ (Phần chứng minh để lại cho bạn đọc).

Từ tính chất trên ta có: ~A(\zeta_n^i)=\left[\prod_{j=1}^{n/gcd(n,i)}\left(1+\zeta_{n/gcd(n,i)}^{j}\right)\right]^{gcd(n,i)\times k}~

Xét: ~x^n-1=\prod_{i=1}^n(x-\zeta_n^i)~

~\Rightarrow (-1)^n-1=\prod_{i=1}^n(-1-\zeta_n^i)~

~\Rightarrow \prod_{i=1}^n(1+\zeta_n^i)=\frac{(-1)^n-1}{(-1)^n}=\begin{cases}2, & n \% 2 = 1 \\ 0, & n\%2=0\end{cases}=2\times (n\%2)~

Từ đó ta có thể suy ra: ~A(\zeta_n^i) = \left[2\times \left(\frac{n}{gcd(n,i)}\%2\right)\right]^{gcd(n,i)\times k}=2^{gcd(n,i)\times k} \times \left(\frac{n}{gcd(n,i)}\%2\right)~

Dựa vào công thức kết quả ~\frac{1}{n}\sum_{i=1}^nA(\zeta_n^i)~ đã nêu ở trên, ta khai triển:

~ans = \frac{1}{n} \sum_{i=1}^{n} \left[2^{gcd(n,i)\times k} \times \left(\frac{n}{gcd(n,i)}\%2\right)\right]~

Độ phức tạp: ~O(n)~.

Subtask 5

Theo trên: ~ans = \frac{1}{n} \sum_{i=1}^{n} \left[2^{gcd(n,i)\times k} \times \left(\frac{n}{gcd(n,i)}\%2\right)\right] = \frac{1}{n} \sum_{d|n} \left[2^{d\times k} \times \left(\frac{n}{d}\%2\right)\times \varphi\left(\frac{n}{d}\right)\right]~

Như vậy; thay vì phải duyệt từ 1 tới ~n~, ta chỉ cần duyệt qua các ước của ~n~ và duy trì việc tính ~\varphi(n)~ nhanh.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.