Bài hôm qua mà phải vẽ decision trê á? Đọc đến đâu code đến đấy chứ.Code này rớt cmn interview luôn vì thằng pv ko hiểu gì Đm bài hard hôm qua ko nhìn ra số cách là lấy a*b ạ cái tội lười ko vẽ decision tree đúng ngu học luôn
Bài hôm qua mà phải vẽ decision trê á? Đọc đến đâu code đến đấy chứ.Code này rớt cmn interview luôn vì thằng pv ko hiểu gì Đm bài hard hôm qua ko nhìn ra số cách là lấy a*b ạ cái tội lười ko vẽ decision tree đúng ngu học luôn
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 classTuyệt vời. Để tui nghiên cứu để hiểu cái rồi đi flex là beat tác giả luôn.
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
.template <uint32_t Order> class PrimeField::Element
.constexpr Sqrt5Sum d1a{Mint{1}, Mint{2} / Mint{5}};
và constexpr Sqrt5Sum d1b{Mint{1} / Mint{2}, Mint{3} / Mint{20}};
res = d1e1n2a + d2e2n2a + d3e3n2a + d4e4n2a;
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 class Solution {
public:
int hammingWeight(uint32_t n) {
return __builtin_popcount(n);
}
};
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.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 classSqrt5Sum
là kiểu có 2 biến a, b tương ứng vớia + 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(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 ứngres = 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à hình như ở trên có đảo dấu e2n2 ròi.
do recursion stack limit, chuyển thành while loop xemJava 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); } }
Integer thì chạy có 32 lần thôi, cái solution của mình bên trên chạy rồi, phải dùng >>> operator là unsigned shift thì nó mới được chứ signed shift là nó cứ shift về -1 miết thôido recursion stack limit, chuyển thành while loop xem
thằng tác giả xài ma trận 2x2 à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.
Ok, thế lại gáy à.thằng tác giả xài ma trận 2x2 à
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
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
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
sao ngắn hơn đượcOk, 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.
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();
}
};
Thôi tối về xử thêm, đang ở công ty.sao ngắn hơn đượctự 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
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
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.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; } };
var hammingWeight = function(n) {
const str = n.toString(2).replaceAll('0','')
return str.length
};
class Solution {
public:
int hammingWeight(uint32_t n) {
return __builtin_popcount(n);
}
};
thằng tác giả xài ma trận 2x2 à
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
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
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
Ozosao ngắn hơn đượctự 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
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
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(); } };
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 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;
}
};