1393 - Highways(问题抽象)(容斥原理计数)

1393 - Highways(问题抽象)(容斥原理计数)

问题的方向是对称的，统计\*2即可，当gcd(a,b)>1及重复，

证：a*b满足gcd(a,b)>1,在他对角线和a'和b'对角线是同一条直线(a'=a/gcd(a,b)b'=b/gcd(a,b))

其次，如果放置位置不够靠左，也不够靠上，则它和它“左上方”的包围盒也重复了

假定左上角坐标(0,0)则对于左上角在(x,y)的包围盒，其左上方的包围盒的左上角为(x-a,y-b),这个左上角合法条件是x-a>=0,y-b>=0

包围盒本身不出界的条件是x+a<=m-1,y+b<=n-1,一共(m-a)*(n-b)个，而左上方有包围盒的情况，即a<=x<=m-a-1

且b<=y<=n-b-1,有c=max(0,m-2*a)*max(0,n-2b)种放法，相减得到：a*b的包围盒有(m-a)(n-b)-c

另外注意应预处理保存所有的gcd，而不是边枚举边算,否则会超时。

分两步，首先计算出从点[1, 1]到[n, m]格子组成的边界的连线，然后这是需要容斥去重的，这个有新的数能加的可能是当维度i和j是互质的时候就会多一个， 然后就是递推n*m的格子的总个数，也要容斥去重，这个就是减去减半的数，这个是因为会重线，最后是对称，从左上到右下，和从坐下到右上

#include#include#include#includeusing namespace std;typedef long long ll;const int maxn=310;int n,m;ll dp[maxn][maxn],ans[maxn][maxn];int gcd(int a,int b){ return b==0?a:gcd(b,a%b);}void init(){ memset(dp,0,sizeof(dp)); memset(ans,0,sizeof(ans)); for(int i=1;i<=300;i++) for(int j=1;j<=300;j++) dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+(gcd(i,j)==1); for(int i=1;i<=300;i++) for(int j=1;j<=300;j++) ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1]+dp[i][j]-dp[i>>1][j>>1];}int main(){ init(); while(scanf("%d%d",&n,&m)!=EOF&&n+m){ printf("%lld\n",ans[n-1][m-1]*2); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。