অ-ল্যাটিস পলিগনের ভেতরে ল্যাটিস পয়েন্ট#

ল্যাটিস পলিগনের জন্য পলিগনের ভেতরে ল্যাটিস পয়েন্ট গণনা করতে পিকের সূত্র আছে। যদি পলিগনের শীর্ষবিন্দু যেকোনো স্থানে হয় তখন কী হবে?

চলুন পলিগনের প্রতিটি বাহু আলাদাভাবে প্রসেস করি, এবং এরপর প্রতিটি বাহুর নিচে ল্যাটিস পয়েন্টের পরিমাণ যোগ করতে পারি, এর ওরিয়েন্টেশন বিবেচনা করে চিহ্ন নির্বাচন করে (ট্র্যাপিজয়েড ব্যবহার করে পলিগনের ক্ষেত্রফল গণনা করার মতো)।

প্রথমত আমাদের লক্ষ্য করা উচিত যে বর্তমান বাহুর প্রান্তবিন্দু $A=(x_1;y_1)$ এবং $B=(x_2;y_2)$ হলে এটিকে একটি রৈখিক ফাংশন হিসেবে উপস্থাপন করা যায়:

$$y=y_1+(y_2-y_1) \cdot \dfrac{x-x_1}{x_2-x_1}=\left(\dfrac{y_2-y_1}{x_2-x_1}\right)\cdot x + \left(\dfrac{y_1x_2-x_1y_2}{x_2-x_1}\right)$$$$y = k \cdot x + b,~k = \dfrac{y_2-y_1}{x_2-x_1},~b = \dfrac{y_1x_2-x_1y_2}{x_2-x_1}$$

এখন আমরা $x=x'+\lceil x_1 \rceil$ প্রতিস্থাপন করব যাতে $b' = b + k \cdot \lceil x_1 \rceil$ হয়। এটি আমাদের $x_1'=0$ এবং $x_2'=x_2 - \lceil x_1 \rceil$ নিয়ে কাজ করতে দেয়। ধরি $n = \lfloor x_2' \rfloor$।

অ্যালগরিদমের সামঞ্জস্যের জন্য আমরা $x = n$ এবং $y = 0$-তে বিন্দুগুলো যোগ করব না। সেগুলো পরবর্তীতে ম্যানুয়ালি যোগ করা যেতে পারে। এইভাবে আমাদের $\sum\limits_{x'=0}^{n - 1} \lfloor k' \cdot x' + b'\rfloor$ যোগ করতে হবে। আমরা এটাও ধরে নিই যে $k' \geq 0$ এবং $b'\geq 0$। অন্যথায় $x'=-t$ প্রতিস্থাপন করতে হবে এবং $b'$-তে $\lceil|b'|\rceil$ যোগ করতে হবে।

চলুন আলোচনা করি কীভাবে $\sum\limits_{x=0}^{n - 1} \lfloor k \cdot x + b\rfloor$ যোগফল মূল্যায়ন করা যায়। আমাদের দুটি ক্ষেত্র আছে:

$k \geq 1$ অথবা $b \geq 1$।
তাহলে আমাদের $y=\lfloor k \rfloor \cdot x + \lfloor b \rfloor$-এর নিচে বিন্দু যোগ করে শুরু করা উচিত। তাদের সংখ্যা সমান
\[ \sum\limits_{x=0}^{n - 1} \lfloor k \rfloor \cdot x + \lfloor b \rfloor=\dfrac{(\lfloor k \rfloor(n-1)+2\lfloor b \rfloor) n}{2}. \]
এখন আমরা শুধুমাত্র সেই $(x;y)$ বিন্দুতে আগ্রহী যেখানে $\lfloor k \rfloor \cdot x + \lfloor b \rfloor < y \leq k\cdot x + b$। এই সংখ্যা সেই বিন্দুর সংখ্যার সমান যেখানে $0 < y \leq (k - \lfloor k \rfloor) \cdot x + (b - \lfloor b \rfloor)$। তাই আমরা আমাদের সমস্যাকে $k'= k - \lfloor k \rfloor$, $b' = b - \lfloor b \rfloor$-তে রিডিউস করেছি এবং $k'$ ও $b'$ উভয়ই এখন ১-এর কম। এখানে একটি ছবি আছে, আমরা শুধু নীল বিন্দু যোগ করেছি এবং $k$ ও $b$-এর ছোট মানে সমস্যা রিডিউস করতে কালো ফাংশন থেকে নীল রৈখিক ফাংশন বিয়োগ করেছি:

কমপ্লেক্সিটি বিশ্লেষণ#

আমাদের সর্বাধিক $\dfrac{(k(n-1)+2b)n}{2}$টি বিন্দু গণনা করতে হবে। এদের মধ্যে আমরা প্রথম ধাপেই $\dfrac{\lfloor k \rfloor (n-1)+2\lfloor b \rfloor}{2}$টি গণনা করব। আমরা ধরে নিতে পারি যে $b$ নগণ্যভাবে ছোট কারণ আমরা এটিকে ১-এর কম করে শুরু করতে পারি। সেক্ষেত্রে আমরা বলতে পারি যে আমরা সব বিন্দুর প্রায় $\dfrac{\lfloor k \rfloor}{k} \geq \dfrac 1 2$ অংশ গণনা করি। এইভাবে আমরা $O(\log n)$ ধাপে শেষ করব।

ইমপ্লিমেন্টেশন#

এখানে একটি সরল ফাংশন দেওয়া হলো যা পূর্ণসংখ্যা বিন্দু $(x;y)$-এর সংখ্যা গণনা করে যেখানে $0 \leq x < n$ এবং $0 < y \leq \lfloor k x+b\rfloor$:

int count_lattices(Fraction k, Fraction b, long long n) {
    auto fk = k.floor();
    auto fb = b.floor();
    auto cnt = 0LL;
    if (k >= 1 || b >= 1) {
        cnt += (fk * (n - 1) + 2 * fb) * n / 2;
        k -= fk;
        b -= fb;
    }
    auto t = k * n + b;
    auto ft = t.floor();
    if (ft >= 1) {
        cnt += count_lattices(1 / k, (t - t.floor()) / k, t.floor());
    }
    return cnt;
}

এখানে Fraction হলো মূলদ সংখ্যা হ্যান্ডেল করা কোনো ক্লাস। ব্যবহারিক ক্ষেত্রে মনে হয় যে যদি সব লব এবং হর পরম মানে সর্বাধিক $C$ হয় তাহলে রিকার্সিভ কলগুলোতে তারা সর্বাধিক $C^2$ হবে যদি আপনি লব ও হরকে তাদের গসাগু দিয়ে ভাগ করতে থাকেন। এই অনুমানে আমরা বলতে পারি যে ডাবল ব্যবহার করা যায় এবং $\varepsilon^2$ নির্ভুলতা প্রয়োজন যেখানে $\varepsilon$ হলো যে নির্ভুলতায় $k$ ও $b$ দেওয়া আছে। এর মানে হলো floor-এ সংখ্যাগুলোকে পূর্ণসংখ্যা হিসেবে বিবেচনা করা উচিত যদি তারা একটি পূর্ণসংখ্যা থেকে সর্বাধিক $\varepsilon^2$ পার্থক্য রাখে।