[二维DP][组合计数][利用对称性简化问题] UVALive 3295

https://vjudge.net/problem/UVALive-3295

这个题目和3720很像，尤其是在应用对称性的时候。这种题目有个很有趣的地方就是他每次都是对局部进行刻画然后得到了全局的信息，或者可以这么说，按照某一种策略使得某种属性所有的状态都被考虑进去。在这里就是计算一个共线的点的问题，按照和题目3720算法本身的推其实是只能算出来“斜率为正”的一类斜线，但是算的是“所有的斜率为正”的斜线，也就是覆盖了每一种情况，那么剩下的情况其实只有水平竖直和斜率为负的斜线，但是由对称性可知斜率为负的斜线一定和斜率为正的斜线数量相等，因此只需要*2即可，而我自己一开始一直在纠结的问题就是怎么算出来这些反向斜线，其实最后全局考虑只需要把算出来的正向斜线情况*2即可。最后的结果就是C(3,(m+1)*(n+1))-共线的三点数量。
wa的话有一个问题是，在gcd的算法中如果a和b有一个数字为0那么返回值就会是0，这种情况在这里的递推过程中是会出现问题的，需要注意让循环从2开始，也算是一个小小的坑吧。。以前没有注意到。

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn=1e3+5;
const int mod=1e9+7;

LL pp[maxn][maxn];
LL dp[maxn][maxn];
LL cnt[maxn][maxn];

LL gcd(LL a,LL b)
{
    return b?gcd(b,a%b):a;
}

LL c3(LL a)
{
    if(a<3)return 0;
    return (a*(a-1)/2)*(a-2)/3;
}

void pre()
{
    for(int i=2;i<maxn;i++)
        for(int j=2;j<maxn;j++)
        dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+max(0LL,gcd(i-1,j-1)-1);
    for(int i=1;i<maxn;i++)
        for(int j=1;j<maxn;j++)
        cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+dp[i][j];
}

int main()
{
    pre();
    int n,m,cs=0;;
    while(~scanf("%d%d",&n,&m)&&n)
    {
        cs++;
        LL ans=c3((n+1)*(m+1));
        ans-=c3(n+1)*(m+1);
        ans-=c3(m+1)*(n+1);
        ans-=2*cnt[n+1][m+1];
        printf("Case %d: %lld\n",cs,ans);
    }
    return 0;
}