4039. Sum of Decoded Numbers
You are given an integer array nums.
Each nums[i] is an encoded integer representing two positive integers x_i and y_i. To decode nums[i], define:
width_i = nums[i] % 10.d_i = floor(nums[i] / 10).x_i as the integer formed by the first width_i digits of the decimal representation of d_i.y_i as the integer formed by all remaining digits of the decimal representation of d_i.
It is guaranteed that the decimal representation of d_i contains more than width_i digits. Therefore, both x_i and y_i contain at least one digit.
The decoded value of nums[i] is x_i^y_i.
Return the sum of the decoded values of all elements in nums, modulo 10^9 + 7.
The floor() function returns the integer part of the division.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
class Solution {
long long mod = 1e9 + 7;
pair<long long, long long> query(long long n) {
long long width = n % 10, d = n / 10;
long long x = 0, y = 0;
string s = to_string(d);
for(int i = 0; i < width and i < s.length(); i++) {
x = x * 10 + s[i] - '0';
}
for(int i = width; i < s.length(); i++) {
y = y * 10 + s[i] - '0';
}
return {x,y % (mod - 1)};
}
long long modpow(long long n, long long x, long long mod) {
if(x<0){
return modpow(modpow(n,-x,mod),mod-2,mod);
}
n%=mod;
long long res=1;
while(x){if(x&1){res=res*n%mod;}n=n*n%mod;x>>=1;}return res;
}
public:
int sumDecoded(vector<long long>& nums) {
long long res = 0;
for(auto& n : nums) {
auto [x,y] = query(n);
res = (res + modpow(x,y,mod)) % mod;
}
return res;
}
};
|
