画山 paint

有一张大小为n*m的白纸，小R想在纸上画一片绵延的群山。

为了描述方便，我们将纸张表示在坐标系上，四个顶点的坐标分别为(0,0)，(n,0)，(0,m)，(n,m)。

小R有一只神奇的画笔，能画p种不同的线段，每种线段用两个参数a，b表示，若画笔停留的位置为(x,y)，则能画一条从(x,y)到(x+a,y+b)的线段，然后画笔停留在(x+a,y+b)，每种线段能画任意次。

小R需要从(0,0)开始，在(n,0)结束，在不超过纸张大小的范围内(可以在边界上)画一片绵延的群山。求一共有多少种本质不同的山形(亦即我们不认为画两次(1,1)和画一次(2,2)有任何区别)。由于结果可能会很大，你只需输出对1,000,000,007取模后的值。

【数据范围】

对于40%的数据，n,m,p≤10

对于100%的数据，n,m,p≤100，1≤ai≤10，-10≤bi≤10

这数据范围看着就很佛系

先把斜率相同的画笔归类，处理处该画笔可以画多少不同的长度。

可以令f[x][y][i]表示画到（x,y），最后一次用的笔种类是i的方案数

再记s[x][y]表示画到（x,y）总方案数

转移的时候取两个差值，避免同一种笔画两次就行。

 #include<cstdio>

 #include<iostream>

 #include<cstdlib>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #define mod 1000000007

 #define ll long long

 using namespace std;

 int n,m,p,flag[][],tot,sum[],id[][];

 ll f[][][],S[][];

 struct node{

     int x,y;double k;

 }s[],a[];

 bool cmp(node a,node b){return a.k<b.k;}

 bool pd(int x,int y){

     if(x>=&&x<=n&&y>=&&y<=m)return ;

     return ;

 }

 int gcd(int x,int y){

     if(!y)return x;

     return gcd(y,x%y);

 }

 int main(){

     cin>>n>>m>>p;

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

         scanf("%d%d",&s[i].x,&s[i].y);

         s[i].k=(double)s[i].y/s[i].x;

     }

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

         int g=gcd(s[i].x,abs(s[i].y));

         s[i].x/=g;s[i].y/=g;

         int nx=s[i].x+,ny=s[i].y+;

         if(!id[nx][ny])id[nx][ny]=++tot,a[tot].x=s[i].x,a[tot].y=s[i].y;

         int t=id[nx][ny];

         flag[t][]=;

         for (int l=g;l*s[i].x<=n;l++)

             flag[t][l]|=flag[t][l-g];

     }

     S[][]=;

     for(int x=;x<=n;x++)

     for(int y=;y<=m;y++){

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

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

                 int nx=x-a[i].x*j,ny=y-a[i].y*j;

                 if(nx>= && nx<=n && ny>= && ny<=m){

                 //cxout<<nx<<' '<<ny<<' '<<f[x][y][i]<<endl;

                 if(flag[i][j])f[x][y][i]=(f[x][y][i]+S[nx][ny]-f[nx][ny][i])%mod;

                 }

                 else break;

             }

             S[x][y]+=f[x][y][i];S[x][y]%=mod;

         }

     }

     cout<<S[n][]<<endl;

     return ;

 }

巴特西

画山 paint

画山 paint

最新文章

热门文章