อัญมณีในท้องปลา: อย่าหักลบทีหลัง ให้ตั้งกฎว่าคำตอบเป็นของใครตั้งแต่แรก

// เฉลยชุดทดสอบย่อย K ไม่เกิน 20 (25 คะแนน)
// แต่ละชนิดให้กล่องหนึ่งใบ คำตอบคือขนาดของกล่องทุกใบรวมกัน หาด้วยการเพิ่มเข้าตัดออก
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int K; ll MOD, ans = 0;
vector<vector<ll>> hi;      // hi[t][s] = หยิบชนิด s ได้มากสุดกี่ชิ้น เมื่อจับชนิด t (ชนิด t นับตัวจับด้วย)

// เลือกทีละชนิดว่าจะเอาเข้าเซต S หรือไม่ up[s] กับ lo[s] คือขอบของกล่องที่ตัดกันมาถึงตอนนี้
void dfs(int t, int cnt, const vector<ll>& up, const vector<ll>& lo) {
    if (t == K) {
        if (cnt == 0) return;                       // เซตว่างไม่นับ
        ll sz = 1 % MOD;
        for (int s = 0; s < K; s++) {
            ll w = up[s] - lo[s] + 1;               // ชนิด s เลือกได้กี่ค่า
            if (w <= 0) return;                     // กล่องที่ตัดกันว่างเปล่า ไม่มีผล
            sz = sz * (w % MOD) % MOD;
        }
        if (cnt % 2 == 1) ans = (ans + sz) % MOD;   // เซตขนาดคี่บวก
        else ans = (ans - sz + MOD) % MOD;          // เซตขนาดคู่ลบ
        return;
    }
    dfs(t + 1, cnt, up, lo);                        // ไม่เอาชนิด t เข้าเซต
    vector<ll> up2(up), lo2(lo);
    for (int s = 0; s < K; s++) up2[s] = min(up2[s], hi[t][s]);
    lo2[t] = 1;                                     // ชุดของชนิด t ต้องมีอัญมณีของตัวจับอย่างน้อยหนึ่งชิ้น
    dfs(t + 1, cnt + 1, up2, lo2);
}

int main() {
    int F;
    if (scanf("%d %d %lld", &F, &K, &MOD) != 3) return 0;
    vector<int> L(F), T(F);
    vector<ll> B(K, 0);                             // B[t] = ปลาตัวยาวที่สุดของชนิด t
    for (int i = 0; i < F; i++) {
        scanf("%d %d", &L[i], &T[i]);
        T[i]--;
        B[T[i]] = max(B[T[i]], (ll)L[i]);
    }
    hi.assign(K, vector<ll>(K, 0));
    for (int t = 0; t < K; t++) {
        for (int i = 0; i < F; i++)
            if (2LL * L[i] <= B[t]) hi[t][T[i]]++;  // ปลาที่ยาวไม่เกินครึ่งของตัวจับ ถูกกลืนได้
        hi[t][t]++;                                 // บวกตัวจับเอง
    }
    dfs(0, 0, vector<ll>(K, LLONG_MAX), vector<ll>(K, 0));
    printf("%lld\n", ans % MOD);
}

// เฉลยชุดทดสอบย่อย K ไม่เกิน 7,000 (70 คะแนน)
// สูตรเดียวกับเฉลยเต็ม ต่างแค่ไม่ยกเซกเมนต์ทรีมาใช้ คูณไล่เอาตรง ๆ เป็น O(K^2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int F, K; ll MOD;
    scanf("%d %d %lld", &F, &K, &MOD);
    vector<int> L(F), T(F);
    vector<vector<int>> byType(K + 1);
    for (int i = 0; i < F; i++) { scanf("%d %d", &L[i], &T[i]); byType[T[i]].push_back(L[i]); }
    for (int t = 1; t <= K; t++) sort(byType[t].begin(), byType[t].end());

    vector<int> ord(K); for (int t = 1; t <= K; t++) ord[t - 1] = t;
    sort(ord.begin(), ord.end(), [&](int a, int b) { return byType[a].back() < byType[b].back(); });
    vector<int> posOf(K + 1); vector<ll> B(K);
    for (int i = 0; i < K; i++) { posOf[ord[i]] = i; B[i] = byType[ord[i]].back(); }

    vector<pair<int,int>> fish(F);
    for (int i = 0; i < F; i++) fish[i] = {L[i], T[i]};
    sort(fish.begin(), fish.end());

    vector<ll> m(K, 0), val(K, 1 % MOD);        // val[p] = m[p] + 1 คือจำนวนทางเลือกของชนิดนั้น
    int ptr = 0; ll ans = 0;
    for (int i = 0; i < K; i++) {
        while (ptr < F && 2LL * fish[ptr].first <= B[i]) {
            int p = posOf[fish[ptr].second]; m[p]++; val[p] = (m[p] + 1) % MOD; ptr++;
        }
        ll left = 1 % MOD;
        for (int j = 0; j < i; j++) left = left * val[j] % MOD;     // คูณไล่แทนการถามเซกเมนต์ทรี
        ans = (ans + m[i] % MOD * left) % MOD;

        const vector<int>& v = byType[ord[i]];
        int xi = (int)(lower_bound(v.begin(), v.end(), B[i] / 2 + 1) - v.begin());
        int J = (int)(lower_bound(B.begin(), B.end(), 2LL * v[xi]) - B.begin());
        if (J < i + 1) J = i + 1;
        ll mid = 1 % MOD;
        for (int j = i + 1; j < J; j++) mid = mid * val[j] % MOD;
        ans = (ans + left * mid) % MOD;
    }
    printf("%lld\n", ans % MOD);
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int SZ; ll MOD; vector<ll> seg;                 // เซกเมนต์ทรีเก็บ "ผลคูณ" เพราะหารเอาเศษด้วย M แล้วหารกลับไม่ได้
void build(int k){ SZ=1; while(SZ<k) SZ<<=1; seg.assign(2*SZ,1%MOD); }
void setv(int p,ll v){ p+=SZ; seg[p]=v%MOD; for(p>>=1;p;p>>=1) seg[p]=seg[2*p]*seg[2*p+1]%MOD; }
ll prod(int l,int r){ if(l>r) return 1%MOD; ll a=1%MOD,b=1%MOD; for(l+=SZ,r+=SZ+1;l<r;l>>=1,r>>=1){ if(l&1) a=a*seg[l++]%MOD; if(r&1) b=seg[--r]*b%MOD; } return a*b%MOD; }
int main(){
    int F,K; if(scanf("%d %d %lld",&F,&K,&MOD)!=3) return 0;
    vector<int> L(F),T(F);
    vector<vector<int>> byType(K+1);
    for(int i=0;i<F;i++){ scanf("%d %d",&L[i],&T[i]); byType[T[i]].push_back(L[i]); }
    for(int t=1;t<=K;t++) sort(byType[t].begin(),byType[t].end());
    vector<int> ord; ord.reserve(K);
    for(int t=1;t<=K;t++) ord.push_back(t);
    sort(ord.begin(),ord.end(),[&](int a,int b){ return byType[a].back()<byType[b].back(); });
    vector<int> posOf(K+1); vector<ll> B(K);
    for(int i=0;i<K;i++){ posOf[ord[i]]=i; B[i]=byType[ord[i]].back(); }

    vector<pair<int,int>> fish(F);               // (ความยาว, ชนิด) เรียงตามความยาว
    for(int i=0;i<F;i++) fish[i]={L[i],T[i]};
    sort(fish.begin(),fish.end());

    build(K);
    vector<ll> m(K,0);                           // m[p] = จำนวนปลาชนิด ord[p] ที่ตัวแทนของแถวปัจจุบันกลืนได้
    int ptr=0; ll ans=0;
    for(int i=0;i<K;i++){
        while(ptr<F && 2LL*fish[ptr].first<=B[i]){ int p=posOf[fish[ptr].second]; m[p]++; setv(p,(m[p]+1)%MOD); ptr++; }
        ll own=m[i];
        ll left=prod(0,i-1);
        ans=(ans+own%MOD*left)%MOD;              // กรณี (ข) นับชนิดตัวเองไม่เต็มเพดาน
        // กรณี (ก) นับชนิดตัวเองเต็มเพดาน  ต้องหา J = ชนิดแรกที่ตัวแทนกลืนปลา x ได้
        const vector<int>& v=byType[ord[i]];
        ll bt=B[i];
        int xi=(int)(lower_bound(v.begin(),v.end(),bt/2+1)-v.begin());   // ตัวแรกที่ 2L > bt
        ll need=2LL*v[xi];
        int J=(int)(lower_bound(B.begin(),B.end(),need)-B.begin());
        if(J<i+1) J=i+1;
        ans=(ans+left*prod(i+1,J-1))%MOD;
    }
    printf("%lld\n",ans%MOD);
}

// ตัวตรวจ: ไล่ทุกชุดของทุกตัวจับแล้วโยนลง set ไม่มีทฤษฎีกันนับซ้ำเลย
// ใช้ได้แค่ทะเลสาบเล็ก ๆ เพราะจำนวนชุดโตแบบทวีคูณ
#include <bits/stdc++.h>
using namespace std;
int F, K; long long MOD;
set<vector<int>> seen;
vector<int> hi, cur;
int catcher;

void rec(int s) {
    if (s == K) {
        if (cur[catcher] >= 1) seen.insert(cur);   // ต้องมีอัญมณีของตัวจับเอง
        return;
    }
    for (int v = 0; v <= hi[s]; v++) { cur[s] = v; rec(s + 1); }
}

int main() {
    if (scanf("%d %d %lld", &F, &K, &MOD) != 3) return 0;
    vector<int> L(F), T(F);
    for (int i = 0; i < F; i++) { scanf("%d %d", &L[i], &T[i]); T[i]--; }
    for (int x = 0; x < F; x++) {                  // ลองให้ปลาทุกตัวเป็นตัวจับ ไม่ใช่แค่ตัวยาวสุดของชนิด
        hi.assign(K, 0);
        for (int i = 0; i < F; i++)
            if (2 * L[i] <= L[x]) hi[T[i]]++;
        hi[T[x]]++;
        catcher = T[x];
        cur.assign(K, 0);
        rec(0);
    }
    printf("%lld\n", (long long)(seen.size() % MOD));
}

// ตัวตรวจชั้นที่สอง: จำลองการกินกันจริงทุกลำดับ แล้วเก็บถุงอัญมณีของปลาทุกตัวที่ยังว่ายอยู่ในทุกสภาพ
#include <bits/stdc++.h>
using namespace std;
int F, K; long long MOD;
vector<int> L, T;
typedef vector<int> State;   // แต่ละตัว: -1 ถ้าถูกกินแล้ว ไม่งั้นคือรหัสถุง (จำนวนต่อชนิด เข้ารหัสฐาน 16)
int main() {
    if (scanf("%d %d %lld", &F, &K, &MOD) != 3) return 0;
    L.resize(F); T.resize(F);
    for (int i = 0; i < F; i++) { scanf("%d %d", &L[i], &T[i]); T[i]--; }
    vector<int> pw(K, 1);
    for (int s = 1; s < K; s++) pw[s] = pw[s - 1] * 16;
    State st(F);
    for (int i = 0; i < F; i++) st[i] = pw[T[i]];
    set<State> vis{st};
    vector<State> q{st};
    set<int> bags;
    while (!q.empty()) {
        State c = q.back(); q.pop_back();
        for (int i = 0; i < F; i++) if (c[i] >= 0) bags.insert(c[i]);
        for (int a = 0; a < F; a++) if (c[a] >= 0)
            for (int b = 0; b < F; b++) if (b != a && c[b] >= 0 && L[a] >= 2 * L[b]) {
                State n = c; n[a] += c[b]; n[b] = -1;
                if (vis.insert(n).second) q.push_back(n);
            }
    }
    printf("%lld\n", (long long)(bags.size() % MOD));
}