thảo luận Leetcode mỗi ngày

freedom.9 said:
Code này rớt cmn interview luôn vì thằng pv ko hiểu gì :doubt: Đm bài hard hôm qua ko nhìn ra số cách là lấy a*b ạ :ah: cái tội lười ko vẽ decision tree đúng ngu học luôn :ah:
Click to expand...
Bài hôm qua mà phải vẽ decision trê á? Đọc đến đâu code đến đấy chứ.
 
Java: 
    public static int hammingWeight(int n) {
        int count = 0;
        String binary = Integer.toBinaryString(n);
        for (int i=0;i<binary.length();i++) {
            if (binary.charAt(i)=='1') {
                count++;
            }
        }
        return count;
    }
 
pikachu_1 said:
Tuyệt vời. Để tui nghiên cứu để hiểu cái rồi đi flex là beat tác giả luôn.
Click to expand...
vô coi lại mấy cái hằng số ròi rút gọn công thức để dễ tính thoy. Ở đây tạo class Sqrt5Sum là kiểu có 2 biến a, b tương ứng với a + b*căn(5), cách cộng trừ nhân chia mũ y hệt class số phức, chỉ khác là căn(5)^2 = 5 chứ ko phải bằng -1 như i. Có thể generalize thành cho mọi căn(k) 5 và kiểu của a, b luôn nên ở đây tạo cái class là template <class T, size_t SqrtValue> struct SqrtSum.

để tính số nguyên % 1e9+7 thì vì 1e9+7 là prime nên nó thuộc cái field nguyên tố gì đó, đọc wiki ko hiểu tại sao lại được như vậy nhưng nếu field nguyên tố thì mọi phần tử trên field đó phép cộng trừ nhân chia ra số xác định hết. Như vậy ko những nó định nghĩa được số nguyên mà còn định nghĩa được phân số luôn
0KSdPUp.png
(tử/mẫu) mod P= tử * (mẫu^-1 mod P) mod P. Class này được đặt tên là template <uint32_t Order> class PrimeField::Element.

xong ròi chỉ còn tính tón sao cho mấy hằng số d1 d2 d3 d4 có dạng sqrt5 sum rồi bỏ vào tính là được. 4 cái d này có dính căn(3 + căn(5)) = e1, ko biểu diễn được nhưng có thể viết thành d1 = A + B*e1, với A, B là kiểu sqrt5 sum kia, ví dụ d1 thì A = 1 + 2/5*căn5, B = 1/2 + 3/20*căn5 --> viết nó là constexpr Sqrt5Sum d1a{Mint{1}, Mint{2} / Mint{5}}; và constexpr Sqrt5Sum d1b{Mint{1} / Mint{2}, Mint{3} / Mint{20}};

u(n) = d1 * e1^n + d2 * e2^n + d3 * e3^n + d4 * e4^n. Vì e1 = căn(...) nên có thể viết lại thành

u(n) = d1 * e1'^{n/2} + d2 * e2'^{n/2} + d3 * e3'^{n/2} + d4 * e4'^{n/2} với e1' = e1^2 = 3 + căn5, v.v.. nếu n chẵn
vì e2 = -e1, e4 = -e3 nên có thể tính lẹ e2'^{n/2} = (-1)^n * e1'^{n/2}, e4'^{n/2} = (-1)^n * e3'^{n/2}
rồi để ý thấy rằng e1'^{n/2} ko có e1 ở trỏng nên phần B trong d1 có thể bỏ đi, chỉ lấy tích 4 phần A trong d1, d2, d3, d4 thoy: res = d1e1n2a + d2e2n2a + d3e3n2a + d4e4n2a;

nếu n lẻ thì u(n) = d1 * e1'^{n//2} * e1 + d2 * e2'^{n//2} * e2 + d3 * e3'^{n//2} * e3 + d4 * e4'^{n//2} * e4 với // là phép chia bỏ phần dư. May mắn ở đây là (3 + căn5)*(3 - căn5) = 4 nên e1*e3 = căn 4 = 2. Vậy u(n) lấy tích phần B trong d1,...,d4 và nhân thêm cho e1 hay 2 tương ứng res = d1e1n2b * e1 + d2e2n2b * e1 + d3e3n2b * Sqrt5Sum{Mint{2}} + d4e4n2b * Sqrt5Sum{Mint{2}}; ơ mà viết tới đây thấy hơi điêu nhỉ đáng lẽ d2e2n2b * e2 = d2e2n2b * -e1 mới đúng chứ đếch hiểu sao lại đúng
rl1Kgfo.gif
à hình như ở trên có đảo dấu e2n2 ròi.
 
Last edited:
Kankute said:
vô coi lại mấy cái hằng số ròi rút gọn công thức để dễ tính thoy. Ở đây tạo class Sqrt5Sum là kiểu có 2 biến a, b tương ứng với a + b*căn(5), cách cộng trừ nhân chia mũ y hệt class số phức, chỉ khác là căn(5)^2 = 5 chứ ko phải bằng -1 như i. Có thể generalize thành cho mọi căn(k) 5 và kiểu của a, b luôn nên ở đây tạo cái class là template <class T, size_t SqrtValue> struct SqrtSum.

để tính số nguyên % 1e9+7 thì vì 1e9+7 là prime nên nó thuộc cái field nguyên tố gì đó, đọc wiki ko hiểu tại sao lại được như vậy nhưng nếu field nguyên tố thì mọi phần tử trên field đó phép cộng trừ nhân chia ra số xác định hết. Như vậy ko những nó định nghĩa được số nguyên mà còn định nghĩa được phân số luôn
0KSdPUp.png
(tử/mẫu) mod P= tử * (mẫu^-1 mod P) mod P. Class này được đặt tên là template <uint32_t Order> class PrimeField::Element.

xong ròi chỉ còn tính tón sao cho mấy hằng số d1 d2 d3 d4 có dạng sqrt5 sum rồi bỏ vào tính là được. 4 cái d này có dính căn(3 + căn(5)) = e1, ko biểu diễn được nhưng có thể viết thành d1 = A + B*e1, với A, B là kiểu sqrt5 sum kia, ví dụ d1 thì A = 1 + 2/5*căn5, B = 1/2 + 3/20*căn5 --> viết nó là constexpr Sqrt5Sum d1a{Mint{1}, Mint{2} / Mint{5}}; và constexpr Sqrt5Sum d1b{Mint{1} / Mint{2}, Mint{3} / Mint{20}};

u(n) = d1 * e1^n + d2 * e2^n + d3 * e3^n + d4 * e4^n. Vì e1 = căn(...) nên có thể viết lại thành

u(n) = d1 * e1'^{n/2} + d2 * e2'^{n/2} + d3 * e3'^{n/2} + d4 * e4'^{n/2} với e1' = e1^2 = 3 + căn5, v.v.. nếu n chẵn
vì e2 = -e1, e4 = -e3 nên có thể tính lẹ e2'^{n/2} = (-1)^n * e1'^{n/2}, e4'^{n/2} = (-1)^n * e3'^{n/2}
rồi để ý thấy rằng e1'^{n/2} ko có e1 ở trỏng nên phần B trong d1 có thể bỏ đi, chỉ lấy tích 4 phần A trong d1, d2, d3, d4 thoy: res = d1e1n2a + d2e2n2a + d3e3n2a + d4e4n2a;

nếu n lẻ thì u(n) = d1 * e1'^{n//2} * e1 + d2 * e2'^{n//2} * e2 + d3 * e3'^{n//2} * e3 + d4 * e4'^{n//2} * e4 với // là phép chia bỏ phần dư. May mắn ở đây là (3 + căn5)*(3 - căn5) = 4 nên e1*e3 = căn 4 = 2. Vậy u(n) lấy tích phần B trong d1,...,d4 và nhân thêm cho e1 hay 2 tương ứng res = d1e1n2b * e1 + d2e2n2b * e1 + d3e3n2b * Sqrt5Sum{Mint{2}} + d4e4n2b * Sqrt5Sum{Mint{2}}; ơ mà viết tới đây thấy hơi điêu nhỉ đáng lẽ d2e2n2b * e2 = d2e2n2b * -e1 mới đúng chứ đếch hiểu sao lại đúng
rl1Kgfo.gif
à hình như ở trên có đảo dấu e2n2 ròi.
Click to expand...
Còn mông lung nhưng cũng hiểu thêm 1 chút rồi thím. Chỗ số nguyên tố là dùng định lý Fermat nên a^(-1) mod p = a^(p-2) mod p. Đại loại là mẫu số bị triệt tiêu.
Mà xem kỹ lại cần dùng nhiều biến quá, tử số mẫu số các kiểu nên chắc không beat được ma trận 2x2 của thằng tác giả rồi.
Dù sao thì O(logn) cũng là top server rồi.
 
Lâu lâu mới thấy có bài bitwise

Python: 
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            count += n & 1
            n = n >> 1
        return count
 
Java không có unsigned integer, bị stack overflow méo biết tại sao
Java: 
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        return n == 0 ? 0 : (n & 1) + hammingWeight(n >>> 1);
    }
}
 
gazer000 said:
Java không có unsigned integer, bị stack overflow méo biết tại sao
Java: 
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        return n == 0 ? 0 : (n & 1) + hammingWeight(n >>> 1);
    }
}
Click to expand...
do recursion stack limit, chuyển thành while loop xem
 
pikachu_1 said:
Mà xem kỹ lại cần dùng nhiều biến quá, tử số mẫu số các kiểu nên chắc không beat được ma trận 2x2 của thằng tác giả rồi.
Click to expand...
thằng tác giả xài ma trận 2x2 à
u3720e4.png

10x10 đâu ra 2x2
tử số mẫu số nhiều nhưng 1/2 trong field 1e9+7 là 2^-1 mod 1e9+7 là 1 số nguyên chứ đâu có phân số nào. Nên e1'^{n/2} là mũ n/2 của 2 số nguyên thoy lẹ lắm
có điều do custom kiểu T nên mỗi phép nhân a*b là bao gồm cả phép mod 1e9+7
OANgL56.png


e1'^{n/2} tốn logn bước nhân, mỗi bước cần 2 phép nhân sqrtsum, mỗi phép nhân sqrtsum tốn 5 phép nhân 2 phép cộng field element, vậy tốn tổng cộng 10 phép nhân 14 lần mod 1e9+7. Trong khi nhân ma trận dù có optmize còn 4x4 thì tốn logn lần nhân ma trận, mỗi lần nhân ma trận tốn 16 phép chia 1e9+7 và 64 phép nhân sao sao bằng được
osCpCsi.png


edit: đo thử tốc độ thì chạy n từ 1 tới 1e6 thì ra kết quả
Elapsed: 1.1236565s
Elapsed: 0.367232s
nhân ma trận 4x4 chậm thua tính chực tiếp 3 lần nhóe
XgR55w2.gif
XgR55w2.gif
XgR55w2.gif
 
Last edited:
Chào các cụ em member mới.
Mong các cụ chỉ giáo ạ.
C++: 
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while (n) {
            count += n&1;
            n = n >> 1;
        }
        return count;
    }
};
 
Kankute said:
thằng tác giả xài ma trận 2x2 à
u3720e4.png

10x10 đâu ra 2x2
tử số mẫu số nhiều nhưng 1/2 trong field 1e9+7 là 2^-1 mod 1e9+7 là 1 số nguyên chứ đâu có phân số nào. Nên e1'^{n/2} là mũ n/2 của 2 số nguyên thoy lẹ lắm
có điều do custom kiểu T nên mỗi phép nhân a*b là bao gồm cả phép mod 1e9+7
OANgL56.png


e1'^{n/2} tốn logn bước nhân, mỗi bước cần 2 phép nhân sqrtsum, mỗi phép nhân sqrtsum tốn 5 phép nhân 2 phép cộng field element, vậy tốn tổng cộng 10 phép nhân 14 lần mod 1e9+7. Trong khi nhân ma trận dù có optmize còn 4x4 thì tốn logn lần nhân ma trận, mỗi lần nhân ma trận tốn 16 phép chia 1e9+7 và 64 phép nhân sao sao bằng được
osCpCsi.png


edit: đo thử tốc độ thì chạy n từ 1 tới 1e6 thì ra kết quả
Elapsed: 1.1236565s
Elapsed: 0.367232s
nhân ma trận 4x4 chậm thua tính chực tiếp 3 lần nhóe
XgR55w2.gif
XgR55w2.gif
XgR55w2.gif
Click to expand...
Ok, thế lại gáy à.
Nhìn nhầm tưởng ma trận tác giả là 2x2 = 4. Hoá ra 4x4 = 16 à.
Thím sửa code sao cho nó ngắn hơn để tui mang đi gáy cái.
 
pikachu_1 said:
Ok, thế lại gáy à.
Nhìn nhầm tưởng ma trận tác giả là 2x2 = 4. Hoá ra 4x4 = 16 à.
Thím sửa code sao cho nó ngắn hơn để tui mang đi gáy cái.
Click to expand...
sao ngắn hơn được
C50F2UH.png
tự viết lại đi cho vui, bỏ hết mấy cái template ra chắc cũng bớt được vài chục dòng
JiZo9zf.png

chắc bỏ phần check cái field order có phải prime hay ko, bỏ luôn phần arithmetic type thêm 8 dòng +-*/ vào lại
pzGVwuf.png


C++: 
template <uint32_t Order>
class PrimeField {
public:
    PrimeField() = delete;
    ~PrimeField() = delete;
    
    class Element {
    public:
        explicit constexpr Element(int64_t n) {
            if (n >= Order) {
                value = n % Order;
            } else if (n >= 0) {
                value = static_cast<uint32_t>(n);
            } else {
                const auto quot = -n / Order;
                const auto rem = -n % Order;
                const auto q = quot + static_cast<int>(rem != 0);
                value = static_cast<uint32_t>(n + q * Order);
            }
        }
        constexpr uint32_t getValue() const { return value; }
        constexpr Element& operator+=(const Element& other) {
            value = (static_cast<uint64_t>(value) + other.value) % Order;
            return *this;
        }
        constexpr Element& operator-=(const Element& other) {
            value = (static_cast<uint64_t>(value) + Order - other.value) % Order;
            return *this;
        }
        constexpr Element& operator*=(const Element& other) {
            value = static_cast<uint64_t>(value) * other.value % Order;
            return *this;
        }
        constexpr Element& operator/=(const Element& other) {
            value = static_cast<uint64_t>(value) * mod_inverse(other.value) % Order;
            return *this;
        }
        constexpr Element operator-() const { return Element{Order - value}; }
        constexpr Element operator+(const Element& other) const { return Element{*this} += other; }
        constexpr Element operator-(const Element& other) const { return Element{*this} -= other; }
        constexpr Element operator*(const Element& other) const { return Element{*this} *= other; }
        constexpr Element operator/(const Element& other) const { return Element{*this} /= other; }

    private:
        static constexpr uint32_t mod_inverse(uint32_t a) {
            int32_t t = 0;
            int32_t r = Order;
            int32_t newt = 1;
            int32_t newr = a;
            while (newr != 0) {
                const auto quotient = r / newr;
                t = exchange(newt, t - quotient * newt);
                r = exchange(newr, r - quotient * newr);
            }
            if (t < 0) t += Order;
            return t;
        }

        uint32_t value = 0;
    };
};

template <class T, size_t SqrtValue>
struct SqrtSum {
    T rp{0}; // rational part
    T ip{0}; // irrational part

    constexpr SqrtSum() = default;
    constexpr SqrtSum(T rp, T ip = T(0)) : rp(rp), ip(ip) {}
    constexpr SqrtSum& operator+=(const SqrtSum& rhs) {
        rp += rhs.rp;
        ip += rhs.ip;
        return *this;
    }
    constexpr SqrtSum& operator-=(const SqrtSum& rhs) {
        rp -= rhs.rp;
        ip -= rhs.ip;
        return *this;
    }
    constexpr SqrtSum& operator*=(const SqrtSum& rhs) {
        const T temp = rp * rhs.rp + ip * rhs.ip * T{SqrtValue};
        ip = rp * rhs.ip + ip * rhs.rp;
        rp = temp;
        return *this;
    }
    constexpr SqrtSum& operator/=(const SqrtSum& rhs) {
        constexpr T SqrtValue_T{SqrtValue};
        const T numerRp{rp * rhs.rp - SqrtValue_T * ip * rhs.ip};
        const T numerIp{ip * rhs.rp - rp * rhs.ip};
        const T denom{rhs.rp * rhs.rp - SqrtValue_T * rhs.ip * rhs.ip};
        rp = numerRp / denom;
        ip = numerIp / denom;
        return *this;
    }
    constexpr SqrtSum operator-() const { return SqrtSum{-rp, -ip}; }
    constexpr SqrtSum operator+(const SqrtSum& other) const { return SqrtSum{*this} += other; }
    constexpr SqrtSum operator-(const SqrtSum& other) const { return SqrtSum{*this} -= other; }
    constexpr SqrtSum operator*(const SqrtSum& other) const { return SqrtSum{*this} *= other; }
    constexpr SqrtSum operator/(const SqrtSum& other) const { return SqrtSum{*this} /= other; }
};

template <class T, size_t V>
constexpr auto pow(SqrtSum<T, V> a, size_t p) {
    SqrtSum<T, V> res = T{1};
    for (; p; p >>= 1, a *= a)
        if (p & 1) res *= a;
    return res;
}

constexpr int kMod = 1'000'000'007;

struct Solution {
    using Mint = PrimeField<kMod>::Element;
    using Sqrt5Sum = SqrtSum<Mint, 5>;
    int knightDialer(int n) {
        if (n == 1) return 10;
        constexpr Sqrt5Sum e1{Mint{3}, Mint{1}};
        constexpr Sqrt5Sum e3{Mint{3}, -Mint{1}};
        constexpr Sqrt5Sum d1a{Mint{1}, Mint{2} / Mint{5}};
        constexpr Sqrt5Sum d1b{Mint{1} / Mint{2}, Mint{3} / Mint{20}};
        constexpr Sqrt5Sum d3a{Mint{1}, -(Mint{2} / Mint{5})};
        constexpr Sqrt5Sum d3b{Mint{9} / Mint{8}, -(Mint{19} / Mint{40})};
        constexpr auto kTwo = Sqrt5Sum{Mint{2}};
        const auto e1n2 = pow(e1, n / 2);
        const auto e3n2 = pow(e3, n / 2);
        const auto res = (n % 2 ? e1n2 * d1b * e1 + e3n2 * d3b * kTwo : e1n2 * d1a + e3n2 * d3a) * kTwo;
        return res.rp.getValue();
    }
};
 
Last edited:
Kankute said:
sao ngắn hơn được
C50F2UH.png
tự viết lại đi cho vui, bỏ hết mấy cái template ra chắc cũng bớt được vài chục dòng
JiZo9zf.png

chắc bỏ phần check cái field order có phải prime hay ko, bỏ luôn phần arithmetic type thêm 8 dòng +-*/ vào lại
pzGVwuf.png
Click to expand...
Thôi tối về xử thêm, đang ở công ty.
À cái phần tính ra d và u cũng là khá mấu chốt. Ở đây chắc toàn cao thủ tui không dám múa rìu, nhưng nếu mọi người cần thì tối về tui cũng chia sẻ cách làm sao tìm ra phương trình sai phân. Bằng tay thôi, còn có khi có công cụ toán ra cái 1 mà không biết.
 
genik92 said:
Chào các cụ em member mới.
Mong các cụ chỉ giáo ạ.
C++: 
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while (n) {
            count += n&1;
            n = n >> 1;
        }
        return count;
    }
};
Click to expand...
Ngon rồi bạn. Phía trên += rồi thì phía dưới >>= cho nó đồng bộ. Thừa chữ n thôi nhưng trông hơi ngứa mắt.
 
Đóng góp thêm 1 p.a cho các bác code JS
Code: 
var hammingWeight = function(n) {
    const str = n.toString(2).replaceAll('0','')
    return str.length
};
 
lặn hơi sâu, nay có bài easy mới dám ngoi lên :adore:
C++: 
class Solution {
public:
    int hammingWeight(uint32_t n) {
        return __builtin_popcount(n);
    }
};
 
Kankute said:
thằng tác giả xài ma trận 2x2 à
u3720e4.png

10x10 đâu ra 2x2
tử số mẫu số nhiều nhưng 1/2 trong field 1e9+7 là 2^-1 mod 1e9+7 là 1 số nguyên chứ đâu có phân số nào. Nên e1'^{n/2} là mũ n/2 của 2 số nguyên thoy lẹ lắm
có điều do custom kiểu T nên mỗi phép nhân a*b là bao gồm cả phép mod 1e9+7
OANgL56.png


e1'^{n/2} tốn logn bước nhân, mỗi bước cần 2 phép nhân sqrtsum, mỗi phép nhân sqrtsum tốn 5 phép nhân 2 phép cộng field element, vậy tốn tổng cộng 10 phép nhân 14 lần mod 1e9+7. Trong khi nhân ma trận dù có optmize còn 4x4 thì tốn logn lần nhân ma trận, mỗi lần nhân ma trận tốn 16 phép chia 1e9+7 và 64 phép nhân sao sao bằng được
osCpCsi.png


edit: đo thử tốc độ thì chạy n từ 1 tới 1e6 thì ra kết quả
Elapsed: 1.1236565s
Elapsed: 0.367232s
nhân ma trận 4x4 chậm thua tính chực tiếp 3 lần nhóe
XgR55w2.gif
XgR55w2.gif
XgR55w2.gif
Click to expand...
Kankute said:
sao ngắn hơn được
C50F2UH.png
tự viết lại đi cho vui, bỏ hết mấy cái template ra chắc cũng bớt được vài chục dòng
JiZo9zf.png

chắc bỏ phần check cái field order có phải prime hay ko, bỏ luôn phần arithmetic type thêm 8 dòng +-*/ vào lại
pzGVwuf.png


C++: 
template <uint32_t Order>
class PrimeField {
public:
    PrimeField() = delete;
    ~PrimeField() = delete;
   
    class Element {
    public:
        explicit constexpr Element(int64_t n) {
            if (n >= Order) {
                value = n % Order;
            } else if (n >= 0) {
                value = static_cast<uint32_t>(n);
            } else {
                const auto quot = -n / Order;
                const auto rem = -n % Order;
                const auto q = quot + static_cast<int>(rem != 0);
                value = static_cast<uint32_t>(n + q * Order);
            }
        }
        constexpr uint32_t getValue() const { return value; }
        constexpr Element& operator+=(const Element& other) {
            value = (static_cast<uint64_t>(value) + other.value) % Order;
            return *this;
        }
        constexpr Element& operator-=(const Element& other) {
            value = (static_cast<uint64_t>(value) + Order - other.value) % Order;
            return *this;
        }
        constexpr Element& operator*=(const Element& other) {
            value = static_cast<uint64_t>(value) * other.value % Order;
            return *this;
        }
        constexpr Element& operator/=(const Element& other) {
            value = static_cast<uint64_t>(value) * mod_inverse(other.value) % Order;
            return *this;
        }
        constexpr Element operator-() const { return Element{Order - value}; }
        constexpr Element operator+(const Element& other) const { return Element{*this} += other; }
        constexpr Element operator-(const Element& other) const { return Element{*this} -= other; }
        constexpr Element operator*(const Element& other) const { return Element{*this} *= other; }
        constexpr Element operator/(const Element& other) const { return Element{*this} /= other; }

    private:
        static constexpr uint32_t mod_inverse(uint32_t a) {
            int32_t t = 0;
            int32_t r = Order;
            int32_t newt = 1;
            int32_t newr = a;
            while (newr != 0) {
                const auto quotient = r / newr;
                t = exchange(newt, t - quotient * newt);
                r = exchange(newr, r - quotient * newr);
            }
            if (t < 0) t += Order;
            return t;
        }

        uint32_t value = 0;
    };
};

template <class T, size_t SqrtValue>
struct SqrtSum {
    T rp{0}; // rational part
    T ip{0}; // irrational part

    constexpr SqrtSum() = default;
    constexpr SqrtSum(T rp, T ip = T(0)) : rp(rp), ip(ip) {}
    constexpr SqrtSum& operator+=(const SqrtSum& rhs) {
        rp += rhs.rp;
        ip += rhs.ip;
        return *this;
    }
    constexpr SqrtSum& operator-=(const SqrtSum& rhs) {
        rp -= rhs.rp;
        ip -= rhs.ip;
        return *this;
    }
    constexpr SqrtSum& operator*=(const SqrtSum& rhs) {
        const T temp = rp * rhs.rp + ip * rhs.ip * T{SqrtValue};
        ip = rp * rhs.ip + ip * rhs.rp;
        rp = temp;
        return *this;
    }
    constexpr SqrtSum& operator/=(const SqrtSum& rhs) {
        constexpr T SqrtValue_T{SqrtValue};
        const T numerRp{rp * rhs.rp - SqrtValue_T * ip * rhs.ip};
        const T numerIp{ip * rhs.rp - rp * rhs.ip};
        const T denom{rhs.rp * rhs.rp - SqrtValue_T * rhs.ip * rhs.ip};
        rp = numerRp / denom;
        ip = numerIp / denom;
        return *this;
    }
    constexpr SqrtSum operator-() const { return SqrtSum{-rp, -ip}; }
    constexpr SqrtSum operator+(const SqrtSum& other) const { return SqrtSum{*this} += other; }
    constexpr SqrtSum operator-(const SqrtSum& other) const { return SqrtSum{*this} -= other; }
    constexpr SqrtSum operator*(const SqrtSum& other) const { return SqrtSum{*this} *= other; }
    constexpr SqrtSum operator/(const SqrtSum& other) const { return SqrtSum{*this} /= other; }
};

template <class T, size_t V>
constexpr auto pow(SqrtSum<T, V> a, size_t p) {
    SqrtSum<T, V> res = T{1};
    for (; p; p >>= 1, a *= a)
        if (p & 1) res *= a;
    return res;
}

constexpr int kMod = 1'000'000'007;

struct Solution {
    using Mint = PrimeField<kMod>::Element;
    using Sqrt5Sum = SqrtSum<Mint, 5>;
    int knightDialer(int n) {
        if (n == 1) return 10;
        constexpr Sqrt5Sum e1{Mint{3}, Mint{1}};
        constexpr Sqrt5Sum e3{Mint{3}, -Mint{1}};
        constexpr Sqrt5Sum d1a{Mint{1}, Mint{2} / Mint{5}};
        constexpr Sqrt5Sum d1b{Mint{1} / Mint{2}, Mint{3} / Mint{20}};
        constexpr Sqrt5Sum d3a{Mint{1}, -(Mint{2} / Mint{5})};
        constexpr Sqrt5Sum d3b{Mint{9} / Mint{8}, -(Mint{19} / Mint{40})};
        constexpr auto kTwo = Sqrt5Sum{Mint{2}};
        const auto e1n2 = pow(e1, n / 2);
        const auto e3n2 = pow(e3, n / 2);
        const auto res = (n % 2 ? e1n2 * d1b * e1 + e3n2 * d3b * kTwo : e1n2 * d1a + e3n2 * d3a) * kTwo;
        return res.rp.getValue();
    }
};
Click to expand...
Ozo
 
ngồi xóa bớt mấy hàm ko cần thiết còn 44 50 dòng
JSxuR2w.gif


đo đạc lại thấy nếu bỏ operator*= khỏi SqrtSum thì MSVC nó ko optimize được hay sao ấy mà chạy mất 0.6s thay vì 0.36s đành phải cho vào lại cộng thêm 6 dòng
4gmOAMB.png

C++: 
template <uint32_t Order>
struct IntMod {
    uint32_t val = 0;
    explicit constexpr IntMod(uint64_t n) : val{static_cast<uint32_t>(n % Order)} {}
    constexpr IntMod operator-() const { return IntMod{Order - val}; }
    constexpr IntMod operator+(const IntMod& rhs) const { return IntMod{static_cast<uint64_t>(val) + rhs.val}; }
    constexpr IntMod operator*(const IntMod& rhs) const { return IntMod{static_cast<uint64_t>(val) * rhs.val}; }
    constexpr IntMod operator/(const IntMod& rhs) const { return *this * rhs.inv(); }
    constexpr IntMod inv() const {
        IntMod res{1}, a{*this};
        for (uint32_t p = Order - 2; p; p >>= 1, a = a * a) if (p & 1) res = res * a;
        return res;
    }
};

template <class T, size_t SqrtValue>
struct SqrtSum {
    T rp{0}; // rational part
    T ip{0}; // irrational part
    constexpr SqrtSum(T rp, T ip = T{0}) : rp(rp), ip(ip) {}
    constexpr SqrtSum& operator*=(const SqrtSum& rhs) { // faster in MSVC
        const T temp = rp * rhs.rp + ip * rhs.ip * T{SqrtValue};
        ip = rp * rhs.ip + ip * rhs.rp;
        rp = temp;
        return *this;
    }
    constexpr SqrtSum operator+(const SqrtSum& rhs) const { return SqrtSum{rp + rhs.rp, ip + rhs.ip}; }
    constexpr SqrtSum operator*(const SqrtSum& rhs) const { return SqrtSum{*this} *= rhs; }
    constexpr SqrtSum pow(uint32_t p) const {
        SqrtSum res = T{1}, a = *this;
        for (; p; p >>= 1, a *= a) if (p & 1) res *= a;
        return res;
    }
};

struct Solution {
    using Mint = IntMod<1'000'000'007>;
    using Sqrt5Sum = SqrtSum<Mint, 5>;
    int knightDialer(int n) {
        if (n == 1) return 10;
        constexpr Sqrt5Sum e1{Mint{3}, Mint{1}};
        constexpr Sqrt5Sum e3{Mint{3}, -Mint{1}};
        constexpr Sqrt5Sum d1a{Mint{1}, Mint{2} / Mint{5}};
        constexpr Sqrt5Sum d1b{Mint{1} / Mint{2}, Mint{3} / Mint{20}};
        constexpr Sqrt5Sum d3a{Mint{1}, -(Mint{2} / Mint{5})};
        constexpr Sqrt5Sum d3b{Mint{9} / Mint{8}, -(Mint{19} / Mint{40})};
        constexpr Sqrt5Sum kTwo{Mint{2}};
        return (kTwo * (n % 2 ? e1.pow(n/2) * d1b * e1 + e3.pow(n/2) * d3b * kTwo : e1.pow(n/2) * d1a + e3.pow(n/2) * d3a)).rp.val;
    }
};
 

Similar threads

4 More Years
Nhiều người mất sạch bài đăng trên Facebook
Replies
0
Views
198
4 More Years
4 More Years
4 More Years
Elon Musk có kế hoạch tính phí người dùng X mới để cho phép đăng bài
2 3
Replies
48
Views
3K
bimatcuasoi5
bimatcuasoi5
Lenh Ho Dai Ca
Giám đốc Nhã Nam xin lỗi
2 3 4
Replies
68
Views
8K
clonebymeeeee
clonebymeeeee
buiduchanh1995
thắc mắc Cách thiết kế database cho hệ thống lớn
2
Replies
37
Views
3K
khonganhit19
khonganhit19
meekoo
thắc mắc [Hỏi AI] Cách làm sao để train AI hiểu một task nào đấy?
Replies
9
Views
1K
weed_bông
weed_bông

Share this page

Back
Top