题面传送门 https://vjudge.net/problem/UVA-12633
题目大意: 给你一张网格, 上面有很多骑士, 每个骑士能横着竖着斜着攻击一条直线上的格子, 求没被攻击的格子的数量总和
好神奇的卷积
假设骑士不能斜着攻击
那么答案就是没被攻击的 行数 * 列数
接下来考虑斜着攻击对答案的贡献
以左下角为坐标原点建立坐标系, 发现一条对角线的点的 $(x+y)$ 坐标是相同的
考虑卷积, 设计两个生成函数 $a,b$
如果第 i 行没骑士, 则 $a_{i}=1$, 反之为 $0$
如果第 i 列没骑士, 则 $b_{i}=1$, 反之为 $0$
我们对两个式子进行卷积, 可以求出每一条对角线上还有多少个空格子
答案就是 $\sum$ 没有骑士的对角线的空格子数
- #include <cmath>
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- #define N1 (1<<18)
- #define M1 (N1<<1)
- #define ll long long
- #define dd double
- #define idx(X) (X-'a')
- using namespace std;
- int gint()
- {
- int ret=0,fh=1; char c=getchar();
- while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();}
- while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}
- return ret*fh;
- }
- int T,n,m,num,r[N1];
- int nt[N1],x[N1],y[N1];
- const dd pi=acos(-1);
- struct cp{
- dd x,y;
- friend cp operator + (const cp &s1,const cp &s2){ return (cp){s1.x+s2.x,s1.y+s2.y}; }
- friend cp operator - (const cp &s1,const cp &s2){ return (cp){s1.x-s2.x,s1.y-s2.y}; }
- friend cp operator * (const cp &s1,const cp &s2){ return (cp){s1.x*s2.x-s1.y*s2.y,s1.y*s2.x+s1.x*s2.y}; }
- }a[N1],b[N1],c[N1];
- void init()
- {
- memset(a,0,sizeof(a));
- memset(b,0,sizeof(b));
- memset(c,0,sizeof(c));
- memset(nt,0,sizeof(nt));
- }
- void FFT(cp *s,int len,int type)
- {
- int i,j,k; cp wn,w,t;
- for(i=0;i<len;i++) if(i<r[i]) swap(s[i],s[r[i]]);
- for(k=2;k<=len;k<<=1)
- {
- wn=(cp){cos(2.0*type*pi/k),sin(2.0*type*pi/k)};
- for(i=0;i<len;i+=k)
- {
- w=(cp){1,0};
- for(j=0;j<(k>>1);j++,w=w*wn)
- {
- t=w*s[i+j+(k>>1)];
- s[i+j+(k>>1)]=s[i+j]-t;
- s[i+j]=s[i+j]+t;
- }
- }
- }
- }
- void FFT_Main(int len)
- {
- FFT(a,len,1); FFT(b,len,1);
- for(int i=0;i<len;i++) c[i]=a[i]*b[i];
- FFT(c,len,-1);
- for(int i=0;i<len;i++) c[i].x=c[i].x/len;
- }
- int main()
- {
- scanf("%d",&T); int t;
- for(t=1;t<=T;t++){
- init();
- scanf("%d%d%d",&n,&m,&num);
- int i,j,de,len,L; ll ans=0;
- for(i=1;i<=num;i++) x[i]=n-gint(), y[i]=gint()-1, a[x[i]].x=-1, b[y[i]].x=-1, nt[x[i]+y[i]]=1;
- for(i=0;i<n;i++) a[i].x++;
- for(i=0;i<m;i++) b[i].x++;
- for(len=1,L=0;len<n+m-1;len<<=1,L++);
- for(i=0;i<len;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));
- FFT_Main(len);
- for(i=0;i<=n+m-2;i++) if(!nt[i]) ans+=(int)(c[i].x+0.1);
- printf("Case %d: %lld\n",t,ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2945851.html