Hỏi Bài : Bài KTUAN trên vn.spoj.pl

Bài này khá quen thuộc nhưng mà nêu giải theo kiểu quen thuộc ( O(n^2) ) thì ... không kịp thời gian
Xin các đàn anh chỉ giáo

https://vn.spoj.pl/problems/KTUAN/

Vì bài này chỉ yêu cầu xuất ra số cách phân tích mod 10^9, nên bạn có thể dùng QHĐ để giải:
F[i,j]: Số các phân tích số j thành tổng các số từ 1..i
if (i>j)
F[i,j]=F[i-1,j];
else
F[i,j]=F[i-1,j]+F[i,j-i];

T chỉ QHĐ được tới mức này thôi. theo như họ nói là kiểu... có công thức. Toán nặng.

Code:

 
    for (int i = 0; i<=n; i++){
        l[i] = 1;
    }
   
    for (int j = 2; j<=n; j++){     
        for (int i = j; i<=n; i++){
            l[i] += l[i-j];
            l[i] %= 1000000000;
        }
    }

link thảo luận ở đây http://vnoi.info/index.php?option=com_voj&task=viewDiscussion&problem=KTUAN

anh hữu qhd như thế thì lấy gì để chứa hết được.
em cũng qhd nhưng mà vẫn là 0(n^2), TLE

[code]arr[0]=1;
for (j=1; j

o0o.hero.o0o đã viết:

anh hữu qhd như thế thì lấy gì để chứa hết được.
em cũng qhd nhưng mà vẫn là 0(n^2), TLE

nếu QHD như Hữu thì rút gọn 1 bước nữa thành mảng 1 chiều như của anh.

Nhưng như vậy vẫn không đủ thời gian chạy.
Bài này thuộc dạng có công thức, em nên xì pam diễn đàn bên đó hỏi những người đã AC thì khả quan hơn.

http://en.wikipedia.org/wiki/Integer_partition
ben VNOI thay co may nguoi xai mang hang de rut ngan thoi gian chay.^^

ldt đã viết:

o0o.hero.o0o đã viết:

anh hữu qhd như thế thì lấy gì để chứa hết được.
em cũng qhd nhưng mà vẫn là 0(n^2), TLE

nếu QHD như Hữu thì rút gọn 1 bước nữa thành mảng 1 chiều như của anh.

Nhưng như vậy vẫn không đủ thời gian chạy.
Bài này thuộc dạng có công thức, em nên xì pam diễn đàn bên đó hỏi những người đã AC thì khả quan hơn.

em nghe đồn bài mày không có công thức tổng quát , người ta chỉ tìm ra công thức gần đúng thôi.
Mà hình như tìm ra công thức tổng quát cho bài này là 1 thách thức toán học thì phải. ^.^
Đành nhắm mắt làm ngơ bài này thôi.

duy đã viết:

ldt đã viết:

o0o.hero.o0o đã viết:

anh hữu qhd như thế thì lấy gì để chứa hết được.
em cũng qhd nhưng mà vẫn là 0(n^2), TLE

nếu QHD như Hữu thì rút gọn 1 bước nữa thành mảng 1 chiều như của anh.

Nhưng như vậy vẫn không đủ thời gian chạy.
Bài này thuộc dạng có công thức, em nên xì pam diễn đàn bên đó hỏi những người đã AC thì khả quan hơn.

em nghe đồn bài mày không có công thức tổng quát , người ta chỉ tìm ra công thức gần đúng thôi.
Mà hình như tìm ra công thức tổng quát cho bài này là 1 thách thức toán học thì phải. ^.^
Đành nhắm mắt làm ngơ bài này thôi.

sao lại không có công thức em, Chí ít cái QHD của mình cũng là công thức rồi, có điều nó bị time thôi.

hjxhjx, muon dien dau voi bai nay qua, lam theo dung cong thuc roi, chay ra dung ket qua het roi, the ma luc thi TLE , luc thi WA, buc minh qua

đã kill xong bài bài KTUAN.

https://vn.spoj.pl/status/KTUAN,hcmut/

Nếu bạn nào cần code, tự log-in lấy về xem.

Lý thuyết để giải bài này:
- http://en.wikipedia.org/wiki/Integer_partition
- http://en.wikipedia.org/wiki/Pentagonal_number

Ặc ặc, vậy mà hồi đó giờ ko để ý, tưởng nó dùng công thức QHĐ chứ :-p

QHĐ không kịp time, nó dùng công thức của Euler cái này làm rồi, ra thi lại cũng po tay

1 2008-12-07 17:29:52 o0oheroo0o Đạt yêu cầu 0.73 3.3M C++
tình hình là đã AC được bài này, quá tối ưu luôn )

anh ldt co the gui gium em bai Ktuan "Nho sua thanh Pascal luon nghe"...em chi biet minh pascal thoi
mail: lekhactuanlamson0710@yahoo.com.vn

Bài này với test 100000 ra bao nhiêu vậy. Ai AC rồi cho em biết được không.
Nếu được thì xem luôn hộ em tại sao QHĐ kiểu O(n^3/2) kiểu này lại bị TLE

Trích dẫn :

var f:array[1..100001] of longint;
g:array[0..600] of longint;
n,j,i,r,ff,k:longint;
{-----------------------------------------------------------------------}
function pentagonal(n:Longint):longint;
Begin
exit(n*(3*n-1) div 2);
End;
{-----------------------------------------------------------------------}
function Generalised_pentagonal(n:longint):longint;
Begin
If n<0 then exit(0);
If (n mod 2)=0 then exit(pentagonal(n div 2+1))
else exit(pentagonal(-(n div 2 +1)));
End;
{----------------------------------------------------------------------}
BEGIN
f[1]:=1;
Readln(n);
i:=0;
Repeat
g[i]:=Generalised_pentagonal(i);
i:=i+1;
Until g[i-1]>n;
For j:=2 to n+1 do
Begin
r:=0;
i:=0;
ff:=-1;
While g[i]<=j do
Begin
k:=g[i]; If k>n then break;
If k>j then break;
If (i mod 2)=0 then ff:=-ff;
r:=(r+ff*f[j-k]) mod 1000000000;
i:=i+1;
End;
f[j]:=r;
If f[j]<0 then f[j]:=(f[j]+1000000000) mod 1000000000;
End;
Writeln(f[n+1]);
END.

có code AC sẵn trong account HCMUT đó, em log về, nếu muốn test các trường hợp
https://vn.spoj.pl/status/KTUAN,hcmut/

@KTuan: đã mail cho em chương trình C++.
Em có thể ánh xạ những cấu trúc tương đương:

- { } = Begin end
- while (Exp) { } = còn lặp khi biểu thức Exp Đúng
- for (i = 2; i<=n; i++) = for i:=2 to n do
(khởi trị; điền kiện kết thúc; biến đổi sau mỗi vòng lặp)
- switch () case.. = giống cấu trúc case of của Pascal
- cin >> x = read(x);
- cout << x = write(x);

ừh, để forward bài làm qua cho em.

cam on anh day la chuong trinh viet bang pascal moi nguoi co the tham khao
const cmaxn=100010;
var n,dd,i,j,jj:longint;
np:array[0..600] of longint;
l:array[0..cmaxn] of int64;
BEGIN
readln(n);
if n = 0 then writeln(0)
else
begin
np[0]:=0;
dd:=1;
i:=0;
while np[i]<=n do
begin
i:=i+1;
jj:=(i+1) div 2 * dd;
dd:=-dd;
np[i]:=jj*(3*jj-1) div 2;
end;
l[0]:=1;
l[1]:=1;
for i:=2 to n do
begin
j:=1;
while (np[j]<=i) do
begin
case j mod 4 of
0,3:
l[i]:=l[i]+1000000000-l[i-np[j]];
1,2:
l[i]:=l[i]+l[i-np[j]];
end;
j:=j+1;
end;
l[i]:=l[i] mod 1000000000;
end;
writeln(l[n]);
end;
END.