不过稍微改动了一下,A掉了。
这里就把题解发出来,加点RP= =
具体细节在程序里面注释。
#include<iostream>
using namespace std;
const long nd=1001;
const long long maxi=1000000007;
long n,m,k;//= =
long long sum[nd][nd];//存储方案数的数组
void input();
void dp();
long getnum();
long gcd(long x,long y);
int main()
{
long a,b,c;
input();
dp();
a=getnum();
b=m*n*2+n+m;
c=gcd(a,b);
if(a==0)cout<<"0"<<endl;
else if(a==b)cout<<"1"<<endl;
else cout<<a/c<<"/"<<b/c<<endl;
return 0;
}
void input()
{
cin>>n>>m>>k;
long a,b,c;
for(a=0;a<=n;a++)
{
for(b=0;b<=m;b++)
{
sum[a][b]=0;
}
}
}
void dp()
{
long a,b,c;
sum[0][0]=1;
//下面的循环是推不删边情况下的方案数,若方案数大于1000000007则取模
for(a=0;a<=n;a++)
{
for(b=0;b<=m;b++)
{
if(a<n){sum[a+1][b]+=sum[a][b];if(sum[a+1][b]>=maxi)sum[a+1][b]-=maxi;}
if(b<m){sum[a][b+1]+=sum[a][b];if(sum[a][b+1]>=maxi)sum[a][b+1]-=maxi;}
}
}
}
long getnum()//获取可行边的数目。其实和上面的函数名字反了= =
{
long a,b;
long long z,x,c;
long num;
num=0;
//下面的循环是扫一遍所有纵向边
for(a=0;a<=n-1;a++)
{
for(b=0;b<=m;b++)
{
z=sum[n][m];
x=sum[a][b];
c=sum[n-a-1][m-b];
if((z-x*c)%maxi==k||(z-x*c)%maxi==k-maxi)
{
num++;
}
}
}
//下面的循环是扫一遍所有横向边
for(a=0;a<=n;a++)
{
for(b=0;b<=m-1;b++)
{
z=sum[n][m];
x=sum[a][b];
c=sum[n-a][m-b-1];
if((z-x*c)%maxi==k||(z-x*c)%maxi==k-maxi)
{
num++;
}
}
}
return num;
}
//最大公约数
long gcd(long x,long y)
{
if(x==0)return y;
if(y==0)return x;
else return gcd(y,x%y);
}
首先,整个图具有对称性,所以图内某点到右上角的方案数等于该点在图中对称点到左下角的方案数。
之后,来回道路可逆,所以该点在图中对称点到左下角的方案数等于左下角到该对称点的方案数。
再之后,根据乘法原理,删除某条边后,减去的方案等于靠左下点到左下角的方案数*靠右上点到右上角的方案数。
所以,删除某条边后所得的方案数就等于
总方案数-【左下角】到【该边左端或下端点】的方案数*【该边右端或上端点】到【右上角】的方案数
=总方案数-【左下角】到【该边左端或下端点】的方案数*【该边右端或上端点的对称点】到【左下角】的方案数。
左下角到任意点的方案已经在之前推出。
另外,由于之前计算方案时已经对1000000007取模,所以
总方案数<【左下角】到【该边左端或下端点】的方案数*【该边右端或上端点的对称点】到【左下角】的方案数
上述的计算结果有可能变为负数,因此在取模后必须看余数是否为k-1000000007。