种树 & 乱搞

题意:

　　在一个(n+1)*(m+1)的网格点上种k棵树,树必须成一条直线,相邻两棵树距离不少于D,求方案数.

SOL:

　　这题吧...巨坑无比,本来我的思路是枚举每一个从(0,0)到(i,j)的矩形,然后在对角线上容斥....这他妈太麻烦了吧...

　　首先我们要避免重复,其次我们要方便统计,然后就滚去想啊...横竖不说了吧...对于对角线我们枚举(0,0)--->(i,j) 的矩阵,并且0,0和(i,j)均中上树,那么剩下的树只可能在对角线上,然后组合数乱搞----->真乱啊...都搞不出来...++--真是让人心累...

Code:

　　贴一发政委巨巨的代码...看起来短...自己打真的是乱得一笔啊...

#include<cstdio>

#include<iostream>

#include<cmath>

using namespace std;

const int mo=1000000000;

int k,n,m,d;

int C[1510][1510];

int gcd(int i,int j) { return j?gcd(j,i%j):i;}

int main()

{

    scanf("%d%d%d%d",&k,&n,&m,&d);

    if (k==1) { printf("%d\n",1LL*(n+1)*(m+1)%mo);return 1;}

    C[0][0]=1;

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

    for (int j=0;j<=1500;j++)

        C[i][j]=(j)?(C[i-1][j-1]+C[i-1][j])%mo:1;

    int ans=0;

    if (m+1-(k-1)*(d-1)>=0) ans=(ans+1LL*(n+1)*C[m+1-(k-1)*(d-1)][k])%mo;

    if (n+1-(k-1)*(d-1)>=0) ans=(ans+1LL*(m+1)*C[n+1-(k-1)*(d-1)][k])%mo;

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

    for (int j=1;j<=m;j++)

    {

        int g=gcd(i,j);

        int p=sqrt(1LL*(d*d-1)*g*g/(i*i+j*j))+1;

        if (g-1-(k-1)*(p-1)<0) continue;

    //  printf("%d %d %d %d\n",i,j,g,p);

        ans=(ans+2LL*(n+1-i)*(m+1-j)*C[g-1-(k-1)*(p-1)][k-2])%mo;

    }

    printf("%d\n",ans);

    return 0;

}

题意:

SOL:

Code:

相关文章