题解

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int MAXN = 55;

long long pow_mod(long long a, long long b) {
long long res = 1;
a %= MOD;
while (b) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}

int main() {
int N, K;
cin >> N >> K;
vector<int> L(N), R(N);
set<int> points;
points.insert(0);
points.insert(100);
for (int i = 0; i < N; i++) {
cin >> L[i] >> R[i];
points.insert(L[i]);
points.insert(R[i]);
}
vector<int> breaks(points.begin(), points.end());
sort(breaks.begin(), breaks.end());

vector<long long> inv(MAXN+1);
for (int i=1; i<=MAXN; i++) {
    inv[i] = pow_mod(i, MOD-2);
}

long long ans = 0;
for (int i=0; i<breaks.size()-1; i++) {
    int l = breaks[i], r = breaks[i+1];
    vector<vector<long long>> dp(N+1, vector<long long>(MAXN, 0));
    dp[0][0] = 1;
    
    for (int idx=0; idx<N; idx++) {
        vector<vector<long long>> ndp(N+1, vector<long long>(MAXN, 0));
        int L_i = L[idx], R_i = R[idx];
        int type;
        if (r <= L_i) type = 1;
        else if (l >= R_i) type = 0;
        else type = 2;
        
        long long a, b, c, d;
        if (type == 2) {
            long long len = R_i - L_i;
            long long inv_len = pow_mod(len, MOD-2);
            a = (MOD - inv_len) % MOD;
            b = (long long)R_i * inv_len % MOD;
            c = inv_len;
            d = (-L_i * inv_len) % MOD;
            if (d < 0) d += MOD;
        }
        
        for (int j=0; j<=N; j++) {
            for (int k=0; k<MAXN; k++) {
                if (dp[j][k] == 0) continue;
                if (type == 0) {
                    ndp[j][k] = (ndp[j][k] + dp[j][k]) % MOD;
                } else if (type == 1) {
                    if (j+1 <= N) {
                        ndp[j+1][k] = (ndp[j+1][k] + dp[j][k]) % MOD;
                    }
                } else {
                    ndp[j][k] = (ndp[j][k] + dp[j][k] * d) % MOD;
                    if (k+1 < MAXN) {
                        ndp[j][k+1] = (ndp[j][k+1] + dp[j][k] * c) % MOD;
                    }
                    if (j+1 <= N) {
                        ndp[j+1][k] = (ndp[j+1][k] + dp[j][k] * b) % MOD;
                        if (k+1 < MAXN) {
                            ndp[j+1][k+1] = (ndp[j+1][k+1] + dp[j][k] * a) % MOD;
                        }
                    }
                }
            }
        }
        dp = ndp;
    }
    
    vector<long long> F(MAXN, 0);
    for (int j=K; j<=N; j++) {
        for (int k=0; k<MAXN; k++) {
            F[k] = (F[k] + dp[j][k]) % MOD;
        }
    }
    
    long long I = 0;
    for (int k=0; k<MAXN; k++) {
        if (F[k] == 0) continue;
        long long term1 = pow_mod(r, k+1);
        long long term2 = pow_mod(l, k+1);
        long long diff = (term1 - term2 + MOD) % MOD;
        I = (I + F[k] * diff % MOD * inv[k+1]) % MOD;
    }
    ans = (ans + I) % MOD;
}
cout << ans << endl;
return 0;

}