动态规划（DP计数）：HDU 5116 Everlasting L

时间：2021-02-26 19:25:09
Matt loves letter L.

A point set P is (a, b)-L if and only if there exists x, y satisfying:

P = {(x, y), (x + 1, y), . . . , (x + a, y), (x, y + 1), . . . , (x, y + b)}(a, b ≥ 1)

A point set Q is good if and only if Q is an (a, b)-L set and gcd(a, b) = 1.

Matt is given a point set S. Please help him find the number of ordered pairs of sets (A, B) such that:

动态规划（DP计数）：HDU 5116 Everlasting L

 

Input

The first line contains only one integer T , which indicates the number of test cases.

For each test case, the first line contains an integer N (0 ≤ N ≤ 40000), indicating the size of the point set S.

Each of the following N lines contains two integers xi, yi, indicating the i-th point in S (1 ≤ xi, yi ≤ 200). It’s guaranteed that all (xi, yi) would be distinct.

 

Output

For each test case, output a single line “Case #x: y”, where x is the case number (starting from 1) and y is the number of pairs.
 

Sample Input

2

6

1 1

1 2

2 1

3 3

3 4

4 3

9

1 1

1 2

1 3

2 1

2 2

2 3

3 1

3 2

3 3

Sample Output

Case #1: 2

Case #2: 6

Hint

n the second sample, the ordered pairs of sets Matt can choose are: A = {(1, 1), (1, 2), (1, 3), (2, 1)} and B = {(2, 2), (2, 3), (3, 2)} A = {(2, 2), (2, 3), (3, 2)} and B = {(1, 1), (1, 2), (1, 3), (2, 1)} A = {(1, 1), (1, 2), (2, 1), (3, 1)} and B = {(2, 2), (2, 3), (3, 2)} A = {(2, 2), (2, 3), (3, 2)} and B = {(1, 1), (1, 2), (2, 1), (3, 1)} A = {(1, 1), (1, 2), (2, 1)} and B = {(2, 2), (2, 3), (3, 2)} A = {(2, 2), (2, 3), (3, 2)} and B = {(1, 1), (1, 2), (2, 1)} Hence, the answer is 6.
　　这道题DP计数，十分有意义。
　　dp[i][j]：表示a∈[1,i],b∈[1,j],sigma(a,b)==1
　　sum[i][j]：表示竖直部分穿过点(i,j)的L的个数
　　看代码就能懂了……
#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

const int N=;

typedef long long LL;

LL map[N][N],st[N],S,M;

LL f[N][N],dp[N][N],sum[N][N];

/*f[i][j]:[1,j]中与i互质的数的个数*/

LL dwn[N][N],rht[N][N];int T,cas,k,x,y;

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

void Prepare(){

    for(int i=;i<=;i++)

        for(int j=;j<=;j++){

            f[i][j]=f[i][j-]+(Gcd(i,j)==);

            dp[i][j]=dp[i-][j]+f[i][j];

        }

}

void Init(){S=M=;

    memset(map,,sizeof(map));

    memset(sum,,sizeof(sum));

    memset(dwn,,sizeof(dwn));

    memset(rht,,sizeof(rht));

}

int main(){

    Prepare();

    scanf("%d",&T);

    while(T--){

        Init();scanf("%d",&k);

        while(k--){scanf("%d%d",&x,&y);map[x][y]=;}

        for(int i=;i>=;i--)

            for(int j=;j>=;j--){

                if(!map[i][j])continue;

                if(map[i+][j])dwn[i][j]=dwn[i+][j]+;

                if(map[i][j+])rht[i][j]=rht[i][j+]+;

            }

        for(int i=;i<=;i++)

            for(int j=;j<=;j++){

                if(!map[i][j])continue;

                memset(st,,sizeof(st));

                for(int k=;k<=dwn[i][j];k++)

                    st[k]=f[k][rht[i][j]];

                for(int k=dwn[i][j];k>=;k--)

                    st[k-]+=st[k];

                for(int k=;k<=dwn[i][j];k++)

                    sum[i+k][j]+=st[k];

                S+=st[];

            }

        for(int i=;i<=;i++)

            for(int j=;j<=;j++){

                if(!dwn[i][j])continue;

                if(!rht[i][j])continue;

                LL tot=dp[dwn[i][j]][rht[i][j]];

                LL calc=sum[i][j]-tot;

                for(int k=;k<=rht[i][j];k++){

                    calc+=sum[i][j+k];

                    M+=*calc*f[k][dwn[i][j]];

                }

                M+=tot*tot;

            }

        printf("Case #%d: %lld\n",++cas,S*S-M);

    }

    return ;

}

相关文章