Untitled

mail@pastecode.io avatar
unknown
c_cpp
7 months ago
1.4 kB
1
Indexable
Never
int mod = 998244353;

long long helper(int i, bool one, bool flag, int count, long long ans, string& s){
	if(count > 3) return 0;
	if(i == s.size()){
		if(count == 0) return 0;
		long long a = ans%mod;
		a = (((a*a)%mod)*a)%mod;
		return a;
	}
	long long a = 0;
	if(one){
		if(flag){
			a += helper(i + 1, one, flag, count + 1, ans, s);
			a += helper(i + 1, one, flag, count, ans + (1LL << (63 - i)), s);
		}
		else{
			if(s[i] == '1'){
				a += helper(i + 1, one, true, count + 1, ans, s);
				a += helper(i + 1, one, flag, count, ans + (1LL << (63 - i)), s);
			}
			else{
				a += helper(i + 1, one, flag, count + 1, ans, s);
			}
		}
		return a%mod;
	}
	else if(flag){
		a += helper(i + 1, true, flag, count, ans + (1LL << (63 - i)), s);
		a += helper(i + 1, one, flag, count, ans, s);
		return a%mod;
	}
	else if(s[i] == '0') return helper(i + 1, one, flag, count, ans, s);
	a += helper(i + 1, true, flag, count, ans + (1LL << (63 - i)), s);
	a += helper(i + 1, one, true, count, ans, s);
	return a%mod;

}

vector<int> sumBeautifulNumbers(int Q, vector<vector<long long>>& query){
	vector<int> arr;
	for(int i = 0; i < Q; i++){
		long long l = query[i][0];
		long long r = query[i][1];
		string s = bitset< 64 >(l - 1).to_string();
		string s2 = bitset< 64 >(r).to_string();
		long long ans = (helper(0, false, false, 0, 0, s2) - helper(0, false, false, 0, 0, s) + mod)%mod;
		arr.push_back(ans%mod);
	}
	return arr;
}
Leave a Comment