Untitled
unknown
c_cpp
2 years ago
1.4 kB
3
Indexable
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; }
Editor is loading...
Leave a Comment