Tối ưu đoạn code bị TLE

[Silver_Boss (Acb bca cba)]

Cho em hỏi liệu còn cách nào tối ưu đoạn code dưới đây nhanh hơn không ạ ? Em bị TLE ở test cuối (n = 1000)

string sum(string a, string b) {
        int carry = 0;
        string res;

        while (a.length() < b.length())
                a = '0' + a;
        while (b.length() < a.length())
                b = '0' + b;

        for (int i = a.length() - 1; i >= 0; --i) {
                int d = (a[i] - '0') + (b[i] - '0') + carry;
                carry = d / 10;
                res = (char)(d % 10 + '0') + res;
        }

        if (carry) res = '1' + res;
        return res;
}

string dp[1002][1002];
void solve() {
        int n;
        cin >> n;

        for (int i = 0; i < n; ++i) dp[0][i] = "1";
        for (int i = 0; i < n; ++i) dp[i][0] = "1";
        for (int i = 1; i < n; ++i) {
                for (int j = 1; j < n; ++j) {
                        dp[i][j] = sum(dp[i - 1][j], dp[i][j - 1]);
                }
        }
        cout << dp[n - 1][n - 1];
}

[rogp10]

Phép cộng của bạn là O(n^2) vì phải tạo n chuỗi, nhân với n^2 ô nữa là O(n^4).

Công thức tổng quát là F(n,k) = C(n+k-1, n-1). Sau khi biến đổi đại số thì thành ra là phép nhân và chia bignum cho 1 số nguyên - tương đối dễ.

[kisuluoibieng (Tên Gì Cũng Được)]

1	1	1	1	1	1	1	1	1	1	1	1
1	2	3	4	5	6	7	8	9	10	11	12
1	3	6	10	15	21	28	36	45	55	66	78
1	4	10	20	35	56	84	120	165	220	286	364
1	5	15	35	70	126	210	330	495	715	1001	1365
1	6	21	56	126	252	462	792	1287	2002	3003	4368
1	7	28	84	210	462	924	1716	3003	5005	8008	12376
1	8	36	120	330	792	1716	3432	6435	11440	19448	31824
1	9	45	165	495	1287	3003	6435	12870	24310	43758	75582
1	10	55	220	715	2002	5005	11440	24310	48620	92378	167960
1	11	66	286	1001	3003	8008	19448	43758	92378	184756	352716
1	12	78	364	1365	4368	12376	31824	75582	167960	352716	705432
1	13	91	455	1820	6188	18564	50388	125970	293930	646646	1352078
1	14	105	560	2380	8568	27132	77520	203490	497420	1144066	2496144
1	15	120	680	3060	11628	38760	116280	319770	817190	1961256	4457400
1	16	136	816	3876	15504	54264	170544	490314	1307504	3268760	7726160
1	17	153	969	4845	20349	74613	245157	735471	2042975	5311735	13037895
1	18	171	1140	5985	26334	100947	346104	1081575	3124550	8436285	21474180
1	19	190	1330	7315	33649	134596	480700	1562275	4686825	13123110	34597290
1	20	210	1540	8855	42504	177100	657800	2220075	6906900	20030010	54627300

tinh ý 1 chút thì lập cái bảng excel sẽ thấy công thứ O(1)
update: vẫn phải O(n) vì có tính giai thừa

[tntxtnt]

ngoẹo đầu qua trái nhìn cái bảng thì thấy nó là tam giác Pasca :V điểm chính giữa mỗi dòng trong tam giác Pascal thứ 2k là {2k \choose k} = \frac{2k!}{k!k!}

với n = 4 thì ứng với 2k=6 hay k=3
với n = 3 thì ứng với 2k=4 hay k=2
vậy suy ra k=n-1, vậy đáp án là {2n-2 \choose n-1} = \frac{(2n-2)!}{(n-1)!(n-1)!}

ơ mà phải ra số lớn bất kì ko có mod gì à, chịu :V