12.6 แบบฝึกหัด

เขียนแต่ละข้อเป็นไฟล์ใหม่ใน Code::Blocks รันแล้วเทียบกับผลลัพธ์ที่ต้องได้ให้ตรงทุกตัวอักษร รวมถึงช่องว่างและการขึ้นบรรทัด ติดจริงๆ ค่อยเปิดคำใบ้ และเปิดเฉลยหลังทำเสร็จแล้วเท่านั้น

ข้อ 1 วันไหนในสัปดาห์

ระดับง่าย เวลาไม่เกิน 1 วินาที

ชมรมดาราศาสตร์นับวันในสัปดาห์เป็นตัวเลข 0 คือวันอาทิตย์ 1 คือวันจันทร์ ไปจนถึง 6 คือวันเสาร์ วันนี้เป็นวันหมายเลข D ชมรมอยากรู้ว่าอีก K วันข้างหน้าจะเป็นวันอะไร ถ้า K ติดลบ หมายถึงย้อนหลังไป -K วัน เช่น K = -1 คือเมื่อวาน

ข้อมูลเข้า

บรรทัดเดียว มีจำนวนเต็ม D และ K คั่นด้วยช่องว่าง โดยที่ 0 ≤ D ≤ 6 และ -10¹⁸ ≤ K ≤ 10¹⁸

ข้อมูลออก

ชื่อวันเป็นภาษาอังกฤษ หนึ่งในเจ็ดคำนี้ Sunday Monday Tuesday Wednesday Thursday Friday Saturday

3 -12

Friday

0 10

Wednesday

ดูคำใบ้

วันที่ได้คือ D + K หารด้วย 7 เหลือเศษ แต่ K ติดลบได้ และ % ของเลขติดลบในภาษา C ได้เศษติดลบ ใช้ ((x % 7) + 7) % 7 ตามหน้า 12.1 ให้ได้ 0 ถึง 6 เสมอ K ใหญ่ถึง 10¹⁸ จึงต้องเป็น long long ชื่อวันเก็บในอาเรย์สองมิติของ char แบบบทที่ 7 แล้วใช้เลขวันเป็น index

ดูเฉลย

#include <stdio.h>

int main()
{
    char names[7][10] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
    long long today, shift;
    scanf("%lld %lld", &today, &shift);
    long long day = ((today + shift) % 7 + 7) % 7;
    printf("%s\n", names[day]);
    return 0;
}

ข้อ 2 ที่ดินสามเหลี่ยม

ระดับง่าย เวลาไม่เกิน 1 วินาที

เจ้าหน้าที่รังวัดปักหมุดเขตที่ดินแปลงหนึ่งไว้สามหมุด ที่ดินแปลงนี้จึงเป็นรูปสามเหลี่ยมที่มีหมุดเป็นมุม หมุดแต่ละหมุดมีพิกัด (x, y) เป็นจำนวนเต็ม หน่วยเป็นเมตร ให้หาพื้นที่ของที่ดินเป็นตารางเมตร ถ้าหมุดทั้งสามอยู่บนเส้นตรงเดียวกัน พื้นที่เป็น 0

ข้อมูลเข้า

บรรทัดเดียว มีจำนวนเต็มหกตัว x1 y1 x2 y2 x3 y3 คั่นด้วยช่องว่าง เป็นพิกัดของหมุดทั้งสาม โดยที่ -10⁹ ≤ x1, y1, x2, y2, x3, y3 ≤ 10⁹

ข้อมูลออก

พื้นที่ของที่ดิน เป็นทศนิยม 1 ตำแหน่ง

1 1 5 1 1 4

6.0

0 0 3 1 1 2

2.5

ดูคำใบ้

ใช้สูตรสองเท่าของพื้นที่ในหน้า 12.5 x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2) ซึ่งเป็นจำนวนเต็มเสมอ แล้วพิมพ์ครึ่งหนึ่งของมันเองด้วย / 2 ตามด้วย .0 หรือ .5 ไม่ต้องใช้ double พิกัดถึง 10⁹ ทำให้ผลคูณถึง 2 × 10¹⁸ ทุกตัวแปรต้องเป็น long long และอย่าลืมกลับเครื่องหมายก่อนดูว่าเป็นเลขคู่หรือคี่

ดูเฉลย

#include <stdio.h>

int main()
{
    long long x1, y1, x2, y2, x3, y3;
    scanf("%lld %lld %lld %lld %lld %lld", &x1, &y1, &x2, &y2, &x3, &y3);
    long long twice = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2);
    if (twice < 0) {
        twice = -twice;
    }
    if (twice % 2 == 0) {
        printf("%lld.0\n", twice / 2);
    } else {
        printf("%lld.5\n", twice / 2);
    }
    return 0;
}

ข้อ 3 แปลงฐาน

ระดับง่าย เวลาไม่เกิน 1 วินาที

เครื่องนับคะแนนสามเครื่องในห้องแล็บแสดงตัวเลขคนละฐาน ครูอยากได้โปรแกรมที่แปลงตัวเลข N ซึ่งเขียนในฐาน A ไปเป็นฐาน B เลขโดดที่มีค่า 0 ถึง 9 เขียนด้วย 0 ถึง 9 และเลขโดดที่มีค่า 10 ถึง 35 เขียนด้วยตัวพิมพ์ใหญ่ A ถึง Z

ข้อมูลเข้า

บรรทัดเดียว มีข้อความ N ตามด้วยจำนวนเต็ม A และ B คั่นด้วยช่องว่าง โดยที่ 2 ≤ A, B ≤ 36

N ยาว 1 ถึง 60 ตัวอักษร ประกอบด้วย 0 ถึง 9 และ A ถึง Z เท่านั้น ทุกหลักมีค่าน้อยกว่า A อาจมีเลข 0 นำหน้า และค่าของ N ไม่เกิน 10¹⁸

ข้อมูลออก

N ในฐาน B ใช้ตัวพิมพ์ใหญ่ และไม่มีเลข 0 นำหน้า ถ้า N มีค่าเป็นศูนย์ ให้พิมพ์ 0

11111101010 2 10

2026 10 16

7EA

ดูคำใบ้

ทำสองขั้นตามหน้า 12.3 ขั้นแรกอ่าน N เป็นข้อความด้วย %s แล้วแปลงเป็นค่าตัวเลขด้วย value = value * A + digit ขั้นที่สองแปลงค่านั้นเป็นฐาน B ด้วย % B กับ / B เก็บหลักไว้ในอาเรย์แล้วพิมพ์ย้อนกลับ เลข 0 ที่นำหน้าในข้อมูลเข้าไม่ทำให้ค่าเปลี่ยน และถ้าค่าเป็น 0 ต้องพิมพ์ 0 หนึ่งตัว ค่าถึง 10¹⁸ ต้องใช้ long long

ดูเฉลย

#include <stdio.h>

int main()
{
    char symbols[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    char text[70];
    int from_base, to_base;
    scanf("%s %d %d", text, &from_base, &to_base);
    long long value = 0;
    for (int i = 0; text[i] != '\0'; i++) {
        int digit;
        if (text[i] >= '0' && text[i] <= '9') {
            digit = text[i] - '0';
        } else {
            digit = text[i] - 'A' + 10;
        }
        value = value * from_base + digit;
    }
    char digits[70];
    int length = 0;
    do {
        digits[length] = symbols[value % to_base];
        length++;
        value /= to_base;
    } while (value > 0);
    for (int i = length - 1; i >= 0; i--) {
        printf("%c", digits[i]);
    }
    printf("\n");
    return 0;
}

ข้อ 4 ถุงเท้าข้างเดียว

ระดับกลาง เวลาไม่เกิน 1 วินาที

หอพักนักกีฬาซักถุงเท้ารวมกันในตะกร้าใบใหญ่ มีถุงเท้า N ข้าง แต่ละข้างมีรหัสสีเป็นจำนวนเต็ม ถุงเท้าสีเดียวกันจับคู่กันได้ หลังจับคู่จนหมด ทุกสีจับคู่ได้ลงตัวพอดี ยกเว้นสีเดียวที่เหลือถุงเท้าค้างอยู่ข้างเดียว ให้หาว่าสีนั้นคือรหัสอะไร

พูดอีกแบบคือ ทุกรหัสสีปรากฏเป็นจำนวนครั้งที่เป็นเลขคู่ ยกเว้นรหัสเดียวที่ปรากฏเป็นจำนวนครั้งที่เป็นเลขคี่

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N เป็นเลขคี่ โดยที่ 1 ≤ N ≤ 999999

บรรทัดที่สองมีรหัสสีของถุงเท้า N ข้าง คั่นด้วยช่องว่าง แต่ละตัวเป็นจำนวนเต็มตั้งแต่ 0 ถึง 1000000000

ข้อมูลออก

รหัสสีที่ปรากฏเป็นจำนวนครั้งที่เป็นเลขคี่

5
41 7 93 7 41

7
2 5 2 5 5 9 9

ดูคำใบ้

นับทีละสีด้วยลูปซ้อนต้องวนราว N² = 10¹² รอบ ไม่ทัน และรหัสสีใหญ่ถึง 10⁹ ใช้อาเรย์นับแบบหน้า 5.3 ไม่ได้ ลองนึกถึงสมบัติของ XOR ในหน้า 12.3 ถ้าเอารหัสสีทุกข้าง XOR รวมกัน สีที่มีจำนวนข้างเป็นเลขคู่จะเหลืออะไร ไม่ต้องเก็บรหัสสีไว้ในอาเรย์ด้วยซ้ำ

ดูเฉลย

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);
    int result = 0;
    for (int i = 0; i < n; i++) {
        int color;
        scanf("%d", &color);
        result = result ^ color;
    }
    printf("%d\n", result);
    return 0;
}

ข้อ 5 ไฟกะพริบพร้อมกัน

ระดับกลาง เวลาไม่เกิน 1 วินาที

ป้ายไฟหน้าโรงเรียนมีหลอดไฟ N หลอด ทุกหลอดกะพริบพร้อมกันที่วินาทีที่ 0 หลังจากนั้นหลอดที่ i กะพริบทุก T_i วินาที คือกะพริบที่วินาทีที่ T_i, 2T_i, 3T_i ไปเรื่อยๆ ให้หาว่าหลังวินาทีที่ 0 ทุกหลอดจะกะพริบพร้อมกันอีกครั้งเป็นครั้งแรกที่วินาทีที่เท่าไร

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N โดยที่ 1 ≤ N ≤ 100

บรรทัดที่สองมีจำนวนเต็ม T₁ ถึง T_N คั่นด้วยช่องว่าง โดยที่ 1 ≤ T_i ≤ 10⁹

รับประกันว่าคำตอบไม่เกิน 10¹⁸

ข้อมูลออก

วินาทีแรกหลังวินาทีที่ 0 ที่ทุกหลอดกะพริบพร้อมกัน

3
4 6 10

2
12 18

ดูคำใบ้

คำตอบคือ ค.ร.น. ของ T ทุกตัว หาทีละตัว answer = lcm(answer, t) โดย lcm ของสองตัวคือ a / gcd(a, b) * b ต้องหารก่อนคูณตามหน้า 12.2 เพราะ ค.ร.น. ที่สะสมมาอาจใหญ่ถึง 10¹⁸ แล้ว ถ้าคูณกับ T ตัวถัดไปก่อนจะล้น long long แม้ T ตัวนั้นจะหาร ค.ร.น. ลงตัวจนคำตอบไม่เปลี่ยนก็ตาม

ดูเฉลย

#include <stdio.h>

long long gcd(long long a, long long b)
{
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main()
{
    int n;
    scanf("%d", &n);
    long long answer = 1;
    for (int i = 0; i < n; i++) {
        long long period;
        scanf("%lld", &period);
        answer = answer / gcd(answer, period) * period;
    }
    printf("%lld\n", answer);
    return 0;
}

ข้อ 6 กระปุกออมสิน

ระดับกลาง เวลาไม่เกิน 1 วินาที

ธนาคารโรงเรียนจัดโครงการออมเงิน นักเรียนแต่ละคนเลือกแผนของตัวเอง วันแรกหยอดกระปุก A บาท แล้วทุกวันถัดไปหยอดมากกว่าวันก่อนหน้า D บาท หยอดติดต่อกัน N วัน คุณครูมีแผนของนักเรียน Q คน อยากรู้ว่าเมื่อครบกำหนด กระปุกของแต่ละคนจะมีเงินกี่บาท

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม Q โดยที่ 1 ≤ Q ≤ 100000

อีก Q บรรทัด แต่ละบรรทัดมีจำนวนเต็ม A D N คั่นด้วยช่องว่าง โดยที่ 1 ≤ A ≤ 10⁹ และ 0 ≤ D ≤ 1000 และ 1 ≤ N ≤ 10⁸

ข้อมูลออก

Q บรรทัด บรรทัดที่ i เป็นจำนวนเงินในกระปุกของนักเรียนคนที่ i

2475
5050
3500

ดูคำใบ้

วนลูปทีละวันต้องวนถึง 10⁸ รอบต่อคำถาม คำถามแสนข้อรวมเป็น 10¹³ รอบ ไม่ทัน ใช้สูตรอนุกรมเลขคณิตในหน้า 12.4 คือ N × A + D × N(N - 1) / 2 แต่ต้องหาร N(N - 1) ด้วย 2 ให้เสร็จก่อนคูณ D เพราะ D × N × (N - 1) ใหญ่ถึง 10¹⁹ เกิน long long ทั้งที่คำตอบจริงเก็บได้ ใส่วงเล็บให้ชัด

ดูเฉลย

#include <stdio.h>

int main()
{
    int q;
    scanf("%d", &q);
    for (int k = 0; k < q; k++) {
        long long first, step, days;
        scanf("%lld %lld %lld", &first, &step, &days);
        long long total = days * first + step * (days * (days - 1) / 2);
        printf("%lld\n", total);
    }
    return 0;
}

ข้อ 7 เขียนเป็นผลคูณของจำนวนเฉพาะ

ระดับกลาง เวลาไม่เกิน 1 วินาที

ครูคณิตศาสตร์ออกข้อสอบให้เขียนจำนวนเต็มเป็นผลคูณของจำนวนเฉพาะ และต้องการเฉลยของตัวเลข Q ตัว ให้เขียนแต่ละตัวในรูป

N = p1^e1 * p2^e2 * ... * pk^ek

โดยที่ p1 < p2 < ... < pk เป็นจำนวนเฉพาะ และ e1 ถึง ek เป็นเลขชี้กำลังที่มากกว่า 0 ตัวประกอบที่มีเลขชี้กำลังเป็น 1 ไม่ต้องเขียน ^1 เช่น 360 เขียนเป็น 360 = 2^3 * 3^2 * 5 และ 97 ซึ่งเป็นจำนวนเฉพาะเขียนเป็น 97 = 97

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม Q โดยที่ 1 ≤ Q ≤ 10

อีก Q บรรทัด บรรทัดละหนึ่งจำนวน คือจำนวนเต็ม N โดยที่ 2 ≤ N ≤ 10¹²

ข้อมูลออก

Q บรรทัด ตามรูปแบบข้างบน มีช่องว่างหนึ่งช่องทั้งสองข้างของ = และ * ไม่มีช่องว่างรอบ ^

360 = 2^3 * 3^2 * 5
97 = 97
1024 = 2^10

1
2

2 = 2

ดูคำใบ้

แยกตัวประกอบแบบหน้า 12.2 ลองหารตั้งแต่ 2 แค่ p * p <= n ถ้า N เป็นจำนวนเฉพาะใกล้ 10¹² การลองหารไปจนถึง N ต้องวนเกือบ 10¹² รอบ พอลูปจบแล้ว n ยังเหลือมากกว่า 1 ที่เหลือคือจำนวนเฉพาะอีกตัวที่ต้องพิมพ์ด้วย เรื่องรูปแบบ ให้ใช้ตัวแปรจำว่าพิมพ์ตัวประกอบตัวแรกไปหรือยัง แล้วพิมพ์ * ก่อนตัวประกอบทุกตัวที่ไม่ใช่ตัวแรก

ดูเฉลย

#include <stdio.h>

int main()
{
    int q;
    scanf("%d", &q);
    for (int k = 0; k < q; k++) {
        long long n;
        scanf("%lld", &n);
        printf("%lld =", n);
        int printed = 0;
        for (long long p = 2; p * p <= n; p++) {
            if (n % p == 0) {
                int power = 0;
                while (n % p == 0) {
                    n /= p;
                    power++;
                }
                if (printed) {
                    printf(" *");
                }
                printf(" %lld", p);
                if (power > 1) {
                    printf("^%d", power);
                }
                printed = 1;
            }
        }
        if (n > 1) {
            if (printed) {
                printf(" *");
            }
            printf(" %lld", n);
        }
        printf("\n");
    }
    return 0;
}

ข้อ 8 แบคทีเรียแบ่งตัว

ระดับยาก เวลาไม่เกิน 1 วินาที

ห้องแล็บชีววิทยาเลี้ยงแบคทีเรียหลายสายพันธุ์ ทุกการทดลองเริ่มจากแบคทีเรีย 1 ตัว แบคทีเรียสายพันธุ์หนึ่งแบ่งตัวทุกชั่วโมง แต่ละตัวกลายเป็น A ตัว นักวิทยาศาสตร์มีคำถาม Q ข้อ แต่ละข้อถามว่าสายพันธุ์ที่แบ่งเป็น A ตัว เมื่อผ่านไป N ชั่วโมงจะมีแบคทีเรียกี่ตัว ตัวเลขใหญ่มาก จึงให้ตอบเป็นเศษจากการหารด้วย 1000000007

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม Q โดยที่ 1 ≤ Q ≤ 100000

อีก Q บรรทัด แต่ละบรรทัดมีจำนวนเต็ม A และ N คั่นด้วยช่องว่าง โดยที่ 1 ≤ A ≤ 10¹⁸ และ 0 ≤ N ≤ 10¹⁸

ข้อมูลออก

Q บรรทัด บรรทัดที่ i เป็นจำนวนแบคทีเรียของคำถามที่ i หารด้วย 1000000007 เหลือเศษเท่าไร

1024
1
125

1
2 100

976371285

ดูคำใบ้

หลัง N ชั่วโมงมีแบคทีเรีย A^N ตัว ลูปคูณ N รอบไม่ทันเมื่อ N ถึง 10¹⁸ ใช้ยกกำลังแบบเร็วในหน้า 12.1 หรือหน้า 12.3 ซึ่งวนแค่ราว 60 รอบต่อคำถาม A ใหญ่ถึง 10¹⁸ ต้อง mod ก่อนเริ่มคูณ ไม่อย่างนั้นผลคูณจะล้น long long และ N = 0 ต้องได้ 1

ดูเฉลย

#include <stdio.h>
#define MOD 1000000007

long long power(long long base, long long exp)
{
    if (exp == 0) {
        return 1;
    }
    long long half = power(base, exp / 2);
    long long result = half * half % MOD;
    if (exp % 2 == 1) {
        result = result * base % MOD;
    }
    return result;
}

int main()
{
    int q;
    scanf("%d", &q);
    for (int k = 0; k < q; k++) {
        long long split, hours;
        scanf("%lld %lld", &split, &hours);
        printf("%lld\n", power(split % MOD, hours));
    }
    return 0;
}

ข้อ 9 จำนวนเฉพาะหลายช่วง

ระดับยาก เวลาไม่เกิน 1 วินาที

เกมทายเลขของชมรมคณิตศาสตร์มีรางวัลพิเศษให้ตั๋วที่หมายเลขเป็นจำนวนเฉพาะ ตั๋วมีหมายเลข 1 ถึง 10⁷ ผู้จัดมีคำถาม Q ข้อ แต่ละข้อถามว่าตั๋วหมายเลข A ถึง B (รวมทั้ง A และ B) มีตั๋วที่ได้รางวัลพิเศษกี่ใบ หรือก็คือ ตั้งแต่ A ถึง B มีจำนวนเฉพาะกี่ตัว

จำนวนเฉพาะคือจำนวนเต็มที่มากกว่า 1 และมีตัวหารที่เป็นจำนวนเต็มบวกแค่ 1 กับตัวมันเอง

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม Q โดยที่ 1 ≤ Q ≤ 100000

อีก Q บรรทัด แต่ละบรรทัดมีจำนวนเต็ม A และ B คั่นด้วยช่องว่าง โดยที่ 1 ≤ A ≤ B ≤ 10⁷

ข้อมูลออก

Q บรรทัด บรรทัดที่ i เป็นจำนวนของจำนวนเฉพาะตั้งแต่ A ถึง B ของคำถามที่ i

4
4
0

1
1 100

ดูคำใบ้

ตรวจทีละเลขในทุกช่วงแบบข้อสุดท้ายของบทที่ 4 ต้องทำซ้ำเป็นแสนครั้ง ช่วงละหลายล้านเลข ไม่ทัน สร้างตะแกรงในหน้า 12.2 ถึง 10⁷ ครั้งเดียว แล้วทำผลรวมสะสมแบบหน้า 5.4 ว่าตั้งแต่ 1 ถึง x มีจำนวนเฉพาะกี่ตัว แต่ละคำถามจึงตอบด้วยการลบครั้งเดียว อาเรย์ int สิบล้านช่องใช้ 40 MB ต้องประกาศนอก main และอย่าลืมว่า 1 ไม่ใช่จำนวนเฉพาะ

ดูเฉลย

#include <stdio.h>

#define LIMIT 10000000

char is_composite[LIMIT + 1];
int prime_count[LIMIT + 1];

int main()
{
    for (int i = 2; i * i <= LIMIT; i++) {
        if (!is_composite[i]) {
            for (int j = i * i; j <= LIMIT; j += i) {
                is_composite[j] = 1;
            }
        }
    }
    prime_count[0] = 0;
    prime_count[1] = 0;
    for (int x = 2; x <= LIMIT; x++) {
        prime_count[x] = prime_count[x - 1];
        if (!is_composite[x]) {
            prime_count[x]++;
        }
    }
    int q;
    scanf("%d", &q);
    for (int k = 0; k < q; k++) {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", prime_count[b] - prime_count[a - 1]);
    }
    return 0;
}

ข้อ 10 ทีมที่มีผู้หญิง

ระดับยาก เวลาไม่เกิน 1 วินาที

ชมรมหุ่นยนต์มีสมาชิกชาย N คน และหญิง M คน ทุกคนต่างกันหมด ครูจะเลือกสมาชิก K คนเป็นทีมไปแข่งขัน โดยทีมต้องมีผู้หญิงอย่างน้อยหนึ่งคน ทีมสองทีมถือว่าต่างกันเมื่อมีสมาชิกไม่ครบชุดเดียวกัน ลำดับการเลือกไม่มีผล ครูมีคำถาม Q ข้อ แต่ละข้อมีค่า N M K ของตัวเอง ให้ตอบว่าเลือกทีมได้กี่แบบ ตัวเลขใหญ่มาก จึงให้ตอบเป็นเศษจากการหารด้วย 1000000007

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม Q โดยที่ 1 ≤ Q ≤ 100000

อีก Q บรรทัด แต่ละบรรทัดมีจำนวนเต็ม N M K คั่นด้วยช่องว่าง โดยที่ 0 ≤ N ≤ 1000 และ 1 ≤ M ≤ 1000 และ 1 ≤ K ≤ N + M

ข้อมูลออก

Q บรรทัด บรรทัดที่ i เป็นจำนวนแบบของคำถามที่ i หารด้วย 1000000007 เหลือเศษเท่าไร

2
7
1

1
10 10 5

ดูคำใบ้

นับทีมที่ต้องการตรงๆ ยาก ให้นับกลับด้าน ทีมทั้งหมดคือ C(N + M, K) ทีมที่ไม่มีผู้หญิงเลยคือเลือกจากผู้ชายล้วน C(N, K) ซึ่งเป็น 0 ถ้า K > N คำตอบคือผลต่างของสองค่านี้ สร้างสามเหลี่ยมปาสกาลแบบ mod ในหน้า 12.4 ถึงแถวที่ 2000 ครั้งเดียว แล้วตอบทุกคำถามจากตาราง อย่าลืมว่าผลต่างหลัง mod อาจติดลบ ต้องบวก MOD กลับตามหน้า 12.1

ดูเฉลย

#include <stdio.h>
#define MOD 1000000007

int choose[2001][2001];

int main()
{
    for (int i = 0; i <= 2000; i++) {
        choose[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            choose[i][j] = (choose[i - 1][j - 1] + choose[i - 1][j]) % MOD;
        }
    }
    int q;
    scanf("%d", &q);
    for (int k = 0; k < q; k++) {
        int boys, girls, size;
        scanf("%d %d %d", &boys, &girls, &size);
        long long all = choose[boys + girls][size];
        long long boys_only = 0;
        if (size <= boys) {
            boys_only = choose[boys][size];
        }
        printf("%lld\n", (all - boys_only + MOD) % MOD);
    }
    return 0;
}