题目描述：
有一张大小为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取模后的值。
输入：
三个整数n，m，p分别描述纸张的大小和可画线段的总数。
接下来p行每行两个参数ai,bi描述画笔可画的第i种线段。
输出：
一个整数表示本质不同的山形数对1,000,000,007取模后的值。
数据范围：
对于40%的数据，n,m,p≤10
对于100%的数据，n,m,p≤100，1≤ai≤10，-10≤bi≤10
算法标签：DP，背包
思路：
难点在如何把斜率相同的去掉，于是我们xiq神犇可以想到把每个斜率能走到的用背包预处理出来。但是，我们掐指一算，妈呀 n5于是出现了一个优化可以省去一个n，用f[i][j][k]表示在i,j这个位置，有斜率为k的线画出的方案数，用s[i][j]表示所有能走到i,j这个位置的方案数，于是f[i][j][k]=s[i'][j']-f[i'][j'][k]。总体还是很妙的！
代码：
#include<bits/stdc++.h> #define il inline #define LL long long #define _(d) while(d(isdigit(ch=getchar()))) using namespace std; const int N=103,mod=1e9+7; LL f[N][N][N],s[N][N];int n,m,p,b[N][N],q[N],tot,cnt;struct node{int a,b,st;}t[N];struct data{int a,b;bool c[N];}dd[N]; il int read(){int x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch-48;_()x=(x<<1)+(x<<3)+(ch^48);return f*x;} il int gcd(int x,int y){if(x>y)swap(x,y);if(x==0)return y;return gcd(y%x,x);} bool cmp(node t1,node t2){return (t1.a<t2.a||(t1.a==t2.a&&t1.b<t2.b));} int main() { n=read();m=read();p=read(); for(int i=1;i<=p;i++){int a=read(),b=read();t[i].st=gcd(abs(a),abs(b));t[i].a=a/t[i].st;t[i].b=b/t[i].st;} sort(t+1,t+1+p,cmp); for(int i=1;i<=p;i++){ if(t[i].a!=t[i+1].a||t[i].b!=t[i+1].b){ q[++cnt]=t[i].st;dd[++tot].c[0]=1;dd[tot].a=t[i].a;dd[tot].b=t[i].b; for(int j=1;j<=cnt;j++)for(int k=0;k+q[j]<=n;k++){ if(!dd[tot].c[k])continue; dd[tot].c[k+q[j]]=1; }cnt=0; } else q[++cnt]=t[i].st; }s[0][0]=1; for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)for(int k=1;k<=tot;k++){ for(int st=1;st<=n;st++){ if(i-st*dd[k].a<0)break;if(!dd[k].c[st])continue;if(j-st*dd[k].b<0||j-st*dd[k].b>m)continue; f[i][j][k]=(f[i][j][k]+s[i-st*dd[k].a][j-st*dd[k].b]-f[i-st*dd[k].a][j-st*dd[k].b][k])%mod; f[i][j][k]=(f[i][j][k]+mod)%mod; } s[i][j]=(s[i][j]+f[i][j][k])%mod; } printf("%lld ",s[n][0]); return 0; }