문자열로 스트로크 된 숫자의 모든 하위 시퀀스의 합

Question

모듈로 (10^9) +7로 저장된 숫자의 모든 하위 시퀀스의 합계를 찾습니다. 이 수는 N = 2 * (10^5) 자릿수까지 가질 수 있습니다.

예 - 문자열이 123 인 경우 하위 시퀀스는 1, 2, 3, 12, 23, 13, 123입니다.Ans = 1 + 2 + 3 + 12 + 23 + 13 + 123 = 177.

Answer 1

나는이 질문을 이해하지 못했지만 여기에 약간의 생각이있다.

n 개의 숫자 문자열에 대해 서브 시퀀스의 수는 지수 함수이므로 무차별 대입에 의존 할 수 없습니다. 그러나 우리는 동적 프로그래밍을 통해이를 수행 할 수 있습니다. F (i)는 마지막 요소가 문자열의 i 번째 자릿수 인 모든 하위 시퀀스의 합계를 나타냅니다. 우리는 O (i)에서 F (i + 1)의 값을 찾고, 마지막에 질문에 답하기 위해 총합 F (1) + ... + F (n)을 출력합니다.

i + 1 번째 숫자가 j라고 가정합니다. 이어서

F (i+1) =j+ (F (i)*10+ j)+(F (i-1)*10+ j)+...+(F (1)*10+ j) 
       = (i+1)j+ 10 Sum F (z) for 1<=z <= i 

그래서 최종 답변 1 ≤ I ≤ N 대 ∑ F (I)이다.

이것은 큰 정수의 합계가 이미 O (n)이고, 각 반복에서 O (n)과 같은 합계가 있고 O (n) 반복이 있으므로 O (n^3)), 이것은 매우 좋지는 않지만 지수 적 방법보다 훨씬 낫습니다.

Answer 2

하자가 N의 제 i 숫자의 합과 N의 k 번째 자릿수를 의미 N[k] 물품 T(i). 그런 다음

:

T(i)의 서브 시퀀스의 합이 T(i-1)의 서브 시퀀스의 합을 더한 그들에게 추가 k 일 자리와 T(i-1) 각각의 서브 시퀀스의 합이기 때문이다

T(0) = 0 
T(i) = T(i-1) + T(i-1) * 10 + N[k] * (2**i) 

. 2**i이 있고 합계가 10 분이 걸린 곱셈입니다.

코드로 퍼팅, 단순화 및 연산 모듈 k는 비교적 간단한 (자리의 수 및 선형 시간)을 제공하고있는 솔루션 :

def subsequences(n, k): 
    total = 0 
    pow2 = 1 
    for i, ds in enumerate(n): 
     total = (11 * total + pow2 * int(ds)) % k 
     pow2 = (2 * pow2) % k 
    return total 

print subsequences('123', 10**9 + 7) 

출력 :

177 

Answer 3

감사 폴 한킨. 당신의 설명은 아주 좋습니다. 알고리즘을 나중에 알았지 만. 여기 내가 한 일이있다. 접근 방식은 동일합니다.

static int mod = 1000000007; 
public static long solve(String s) { 
    long ans = 0; 
    int n = s.length(); 
    for(int i=0; i<n; i++) { 
     ans += (((Character.getNumericValue(s.charAt(i))*pow(11, n-i-1, mod))%mod)*pow(2, i, mod))%mod; 
     ans %= mod; 
    } 
    return ans; 
}