이 솔루션에 대한 잘못된 답을 제공하는 SPOJ

Question

NGON 문제를 해결하려고합니다. 여기에 동적 프로그래밍을 사용하고 있습니다. 되풀이 함수는 다음과 같습니다.

f(a,b) = f(a-1,b) + f(a-1,b-1)*ai +f(a-1,b-2)*ai*(ai-1)/2, a>0,b>0 
f(a,0) = 1, 
f(0,b) = 0, 

ai가 ath면에있는 점입니다.

그러나 나는 틀린 답을 얻고 있습니다. 다른 사람의 코드를 읽는 것이 어렵다는 것을 알고 있지만 진정으로 도움을 주시면 감사하겠습니다. 나는 오버플로를 돌 보았다고 느낍니다. 또한 최적화가 가능한지 제안하십시오.

#include<stdio.h> 
#define MAX 1010 
#define MODULO 1000000007 

int main() 
{ 
    int test_cases,i,a,b; 
    int sides,points[MAX]; 
    unsigned long long int result[MAX][MAX],temp; 
    for(scanf("%d",&test_cases);test_cases>0;test_cases--) 
    { 
     scanf("%d",&sides); 
     for(i=0;i<sides;i++) 
     { 
      scanf("%d",&points[i]); 
     } 

     result[0][0]=1; 
     for(a=1;a<=sides;a++) 
     { 
      result[a][0]=1; 
      result[0][a]=0; 
     } 

     for(a=1;a<=sides;a++) 
     { 
      for(b=1;b<=sides;b++) 
      { 
       if(b>2*a) 
       { 
        result[a][b]=0; 
       } 
       else 
       { 
        result[a][b]=(result[a-1][b]+result[a-1][b-1]*points[a-1])%MODULO; 
        if(b>1) 
        { 
         temp=(result[a-1][b-2]*points[a-1]*(points[a-1]-1))%MODULO; 
         temp=temp>>1; 
         result[a][b]=(result[a][b]+temp)%MODULO; 
        } 
       } 
      } 
     } 
     printf("%lld\n",result[sides][sides-1]); 
    } 
    return 0; 
} 

Answer 1

나는이 라인에 문제가있을 수 있습니다 생각 :

temp=(result[a-1][b-2]*points[a-1]*(points[a-1]-1))%MODULO; 
temp=temp>>1; 

문제는 모듈로 연산을 사용하는 경우 분할 할 때 각별한주의를 취할 필요가 있다는 것입니다.

예를 들어,이 동일하지 않다 X/2 모듈 (100)을 고려 X 모듈 100 2.

가정하자 x로

x/2 % 100 = 100/2 % 100 = 50 % 100 = 50 

하지만

(x % 100)/2 = (100%100)/2 = 0/2 = 0 

100이었다 분할

모듈로를 계산하기 전에 나누기를 시도하십시오.

temp=(result[a-1][b-2]*((points[a-1]*(points[a-1]-1))>>1))%MODULO;