我是用类似与P4317的数位dp做的, 但不知道为什么最后的$21\sim 27$号点$\color{Blue}{\text{TLE}}$了, 求大佬帮助.

我的代码:

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

long long f1[4000][4000], f2[4000][4000], P;

inline long long mod(long long n, long long p){
	return (n % p + p) % p;
}

long long mul(long long a, long long b, long long p){
	long long ans = 0;
	
	while(b > 0){
		if(b & 1)
			ans = (ans + a) % p;
		
		a = (a + a) % p;
		b >>= 1;
	}
	
	return ans;
}

long long dfs1(vector<int>& number, int pos, int _1, bool limit){
	if(pos == -1) return _1 == 0;
	if(_1 < 0) return 0;
	
	if(limit == false && f1[pos][_1] != -1) return f1[pos][_1];
	
	long long res = 0;
	int end = (limit == true) ? number[pos] : 1;
	
	for(int i = 0; i <= end; i ++)
		res = mod(res + dfs1(number, pos - 1, _1 - i, limit & (i == end)), P);
	
    if(!limit) f1[pos][_1] = res;

	return res;
}

long long slove1(vector<int>& number, int _1){
	return dfs1(number, number.size() - 1, _1, true);
}

long long get_ans1(vector<int>& number){
	long long res = 0;
	
	for(int i = 1; i <= number.size(); i ++)
		res = mod(res + mul(i, slove1(number, i), P), P);
	
	return res;
}

long long quick_pow(long long a, long long k){
	long long ans = 1;

	while(k > 0){
		if(k & 1) ans = ans * a % P;
		a = a * a % P;
		k >>= 1;
	}
	
	return ans;
}

long long dfs2(vector<int>& number, int pos, int _1, bool limit){
	if(pos == -1) return _1 == 0;
	if(_1 < 0) return 0;
	
	if(limit == false && f2[pos][_1] != -1) return f2[pos][_1];
	
	long long res = 0;
	int end = (limit == true) ? number[pos] : 1;
	
	for(int i = 0; i <= end; i ++)
		res = mod(res + dfs2(number, pos - 1, _1 - i, limit & (i == end)), P - 1);
	
    if(!limit) f2[pos][_1] = res;

	return res;
}

long long slove2(vector<int>& number, int _1){
    return dfs2(number, number.size() - 1, _1, true);
}

long long get_ans2(vector<int>& number){
    long long res = 1;
	
	for(int i = 1; i <= number.size(); i ++)
		res = mod(res * quick_pow(i, slove2(number, i)), P);
	
	return res;
}

long long inv(long long a){
	return quick_pow(a, P - 2);
}

vector<int> change(string x, bool minus){
	reverse(x.begin(), x.end());
    int high = x.size() - 1;
	if(minus){
		x[0] --; int pos = 0;
		while(x[pos] < '0') x[pos + 1] --, x[pos] += 10, pos ++;
		if(x[high] == '0') high --;
	}

    vector<int> binary; binary.clear();

    while(high >= 0){
        int res = 0;
        for(int i = high; i >= 0; i --){
            res = res * 10 + x[i] - '0';
            x[i] = res / 2 + '0';
            res %= 2;
        }
        binary.push_back(res);
        if(x[high] == '0') high --;
    }

    return binary;
}

int main(){
	memset(f1, -1, sizeof(f1));
    memset(f2, -1, sizeof(f2));
	
	int T, type; cin >> T >> P >> type;
	
	while(T --){
		string L, R; cin >> L >> R;

		vector<int> l = change(L, 1), r = change(R, 0);
		
		cout << mod(get_ans1(r) - get_ans1(l), P) << ' ' << mod(mul(get_ans2(r), inv(get_ans2(l)), P), P) << endl;
	}
	
	return 0;
}