0과 1의 형태로 돌연변이 찾기

Question

http://poj.org/problem?id=1426 (2002 년 다카 지역)을 해결하려고했습니다. 비록 정확한 알고리즘이 필요하지만 1에서 200까지 다양하게 나왔지만 이진수를 생성하고 divisibility를 확인하여 모든 값을 미리 계산했습니다. 이제 일정 시간 알고리즘을 가지고 있습니다 :) 그러나 이것이 확실합니다. 문제에 대한 올바른 접근법이 아닙니다. 나는이 문제가 사이트의 기본 수학에 속하기 때문에 그래프 검색 알고리즘을 사용하지 않기를 바랍니다. 그래서 TLE을 제공하지 않는이 문제에 대한 수학적 해결책이 있어야한다고 생각합니다. 만약 누군가가 올바른 방법으로 그것을 제안한다면 나는 감사 할 것입니다.

Answer 1

나머지 부분에서는 간단한 트릭입니다.

모든 배수를 0과 1로만 써야한다는 것을 의미합니다. 즉, 10의 몇 배를 합한 배수를 원한다는 의미입니다. 즉, 일부 {a (i)에 대해 x = \ sum {10^a (i))}. 우리가 원하는 적절한 인덱스를 찾으려면 숫자 n의 배수가 x 몬 n = 0이라는 것을 기억해야합니다.

그래서 10 mod n의 거듭 제곱을 쓰고 이 합은 0 mod n입니다. 의 19으로 해보자 :

Num -> Num mod 19 
1 -> 1 
10 -> 10 
10^2 -> 5 
10^3 -> 12 
10^4 -> 6 
10^5 -> 3 

을 지금, 우리는 0 모드 19 10^1 + 10^4 + 10^5 = 19, 그래서 우리의 솔루션은 110,010 것을 볼 수 있습니다. 리마인더 모드 19를 찾으려면 모든 단일 파워를 계산할 필요가 없습니다. 이전 값 mod 19에 10을 곱한 다음 모듈을 계산하면됩니다.

예를 들어, 10^4 mod 10 = 10^3 * 10 mod 19 = 12 * 10 mod 19 = 6, 10^4를 계산하는 것보다 쉽습니다 (작은 힘이 아닐 수도 있지만, calculato 100^100 mod 19로 만들기 전에).

EDIT

남은 유일한 문제는 서브 세트가 존재 가정 0 개조 N에 가산 서브 세트를 발견한다.

편집

좋아, 내가 N = 200까지 작동 및 선형 시간에 문제를 해결할 생각을 가지고있다. 기본적으로 mod n이 조만간 오버랩된다는 사실을 이용합니다. 이것은 hte pigeot 원칙 때문에 사실입니다. 그러나 특정 경우에는 100 개의 정수 만 가지고 작업하는 것은 단순한 경우에 불과합니다. 어쨌든, 이전에 표시된 것처럼 계산 된 미리 알림 목록이 주어지면 부분 합계를 계산합니다. 당신이 이미 가지고있는 가치를 만났다면, 당신은 해답을 얻습니다 (i-1 1은 j 0에 의해 추종됩니다). 당신이 0을 만난다면, 당신은 잘 끝났습니다. 내가 할 수있는 모든 집합을 얻을 수있는 방법의 수이고 명시 적으로 설정을하지 때문에,

 for (int n = 2; n <= 200; n++) 
     { 
      int[] reminder = new int[100]; 
      reminder[0] = 1; 
      for (int i = 1; i < 100; i++) 
      { 
       reminder[i] = (10 * reminder[i - 1]) % n; 
      } 
      var lst = reminder.Select((x, y) => new TenPower { Reminder = x, Pow = y }) 
       .ToList(); 

      bool cont = true; 
      for (int i = 1; (i < 100)&&cont; i++) 
      { 
       if (lst[i].Reminder == 0) 
       { 
        cont = false; 
        Console.WriteLine(n +" :: " + Math.Pow(10, lst[i].Pow)); 
       } 
       else 
       { 
        lst[i].Reminder = (lst[i].Reminder + lst[i - 1].Reminder) % n; 
        if (lst[i].Reminder == 0) 
        { 
         cont = false; 
         Console.WriteLine(n + " :: " + Math.Pow(10, lst[i].Pow)); 
        } 
        for (int j = i - 1; (j > 0) && cont; j--) 
        { 
         if (lst[i].Reminder == lst[j].Reminder) 
         { 
          cont = false; 
          Console.Write(n + " :: "); 
          for (int k = 0; k < i - j; k++) 
          { 
           Console.Write("1"); 
          } 
          for (int k = i - j-1; k < i; k++) 
          { 
           Console.Write("0"); 
          } 
          Console.WriteLine(); 
         } 
        } 
       } 
      } 
     }