algorithm - 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 是 th 边的点。

但是我得到了错误的答案。我知道很难通过别人的代码，但我真的很感激任何帮助。我觉得我已经处理了溢出问题。也请建议是否也可以进行任何优化。

#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 为 100，

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

但是

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

尝试在计算模数之前进行除法:

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