本文共 5212 字，大约阅读时间需要 17 分钟。
题目链接：
题意：在如下的图中放车使得不相互攻击。求放K个车的方案数。
思路：有如下三种情况。分成左中右三段，竖直方向分成上中下。
#include #include #include #include #include #include #include #include #include #include #include #define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))#define abs(x) ((x)>=0?(x):-(x))#define i64 long long#define u32 unsigned int#define u64 unsigned long long#define clr(x,y) memset(x,y,sizeof(x))#define CLR(x) x.clear()#define ph(x) push(x)#define pb(x) push_back(x)#define Len(x) x.length()#define SZ(x) x.size()#define PI acos(-1.0)#define sqr(x) ((x)*(x))#define MP(x,y) make_pair(x,y)#define FOR0(i,x) for(i=0;i =0;i--)#define DOW1(i,x) for(i=x;i>=1;i--)#define DOW(i,a,b) for(i=a;i>=b;i--)using namespace std;void RD(int &x){scanf("%d",&x);}void RD(i64 &x){scanf("%I64d",&x);}void RD(u32 &x){scanf("%u",&x);}void RD(double &x){scanf("%lf",&x);}void RD(int &x,int &y){scanf("%d%d",&x,&y);}void RD(i64 &x,i64 &y){scanf("%I64d%I64d",&x,&y);}void RD(u32 &x,u32 &y){scanf("%u%u",&x,&y);}void RD(double &x,double &y){scanf("%lf%lf",&x,&y);}void RD(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}void RD(i64 &x,i64 &y,i64 &z){scanf("%I64d%I64d%I64d",&x,&y,&z);}void RD(u32 &x,u32 &y,u32 &z){scanf("%u%u%u",&x,&y,&z);}void RD(double &x,double &y,double &z){scanf("%lf%lf%lf",&x,&y,&z);}void RD(char &x){x=getchar();}void RD(char *s){scanf("%s",s);}void RD(string &s){cin>>s;}void PR(int x) {printf("%d\n",x);}void PR(i64 x) {printf("%I64d\n",x);}void PR(u32 x) {printf("%u\n",x);}void PR(u64 x) {printf("%llu\n",x);}void PR(double x) {printf("%.4lf\n",x);}void PR(char x) {printf("%c\n",x);}void PR(char *x) {printf("%s\n",x);}void PR(string x) {cout< < temp.a[0]) p=a[0]; else p=temp.a[0]; for(i=a[0],j=temp.a[0],k=p;j>=1&&i>=1;i--,j--,k--) ans.a[k]=a[i]+temp.a[j]; if(j==0) { while(i>=1) ans.a[i]=a[i--]; } else { while(j>=1) ans.a[j]=temp.a[j--]; } ans.a[0]=0; for(i=p;i>=1;i--) { ans.a[i-1]+=ans.a[i]/MOD; ans.a[i]%=MOD; } if(ans.a[0]) { for(i=p+1;i>=1;i--) ans.a[i]=ans.a[i-1]; ans.a[0]=p+1; } else ans.a[0]=p; return ans; } BigNum operator-(BigNum temp) { BigNum ans; int i,j; for(i=0;i<=a[0];i++) ans.a[i]=a[i]; for(i=ans.a[0],j=temp.a[0];i>=1&&j>=1;i--,j--) ans.a[i]-=temp.a[j]; for(i=ans.a[0];i>=1;i--) if(ans.a[i]<0) { ans.a[i]+=MOD; ans.a[i-1]--; } for(i=1;i<=a[0];i++) if(ans.a[i]) break; if(i>a[0]) { ans.a[0]=1; ans.a[1]=0; return ans; } for(j=i;j<=a[0];j++) ans.a[j+1-i]=ans.a[j]; ans.a[0]=a[0]-i+1; return ans; } BigNum operator*(BigNum temp) { BigNum ans; int i,j,p=a[0]+temp.a[0]-1; memset(ans.a,0,sizeof(ans.a)); for(i=a[0];i>=1;i--) for(j=temp.a[0];j>=1;j--) ans.a[i+j-1]+=a[i]*temp.a[j]; ans.a[0]=0; for(i=p;i>=1;i--) { ans.a[i-1]+=ans.a[i]/MOD; ans.a[i]%=MOD; } if(ans.a[0]) { for(i=p;i>=0;i--) ans.a[i+1]=ans.a[i]; ans.a[0]=p+1; } else ans.a[0]=p; return ans; } BigNum operator*(int temp) { BigNum ans; int i; for(i=1;i<=a[0];i++) ans.a[i]=a[i]*temp; ans.a[0]=0; for(i=a[0];i>=1;i--) { ans.a[i-1]+=ans.a[i]/MOD; ans.a[i]%=MOD; } if(ans.a[0]) { for(i=a[0];i>=0;i--) ans.a[i+1]=ans.a[i]; ans.a[0]=a[0]+1; } else ans.a[0]=a[0]; if(ans.a[1]>=MOD) { for(i=ans.a[0];i>=0;i--) ans.a[i+1]=ans.a[i]; ans.a[0]++; } return ans; } BigNum operator/(int x) { BigNum ans; int i,j; i64 p; for(i=1;i<=a[0];i++) { if(i==1) { ans.a[i]=a[i]/x; p=a[i]%x; } else { ans.a[i]=(p*MOD+a[i])/x; p=(p*MOD+a[i])%x; } } for(i=1;i<=a[0];i++) if(ans.a[i]) break; if(i>a[0]) { ans.a[0]=1; ans.a[1]=0; return ans; } for(j=i;j<=a[0];j++) ans.a[j+1-i]=ans.a[j]; ans.a[0]=a[0]-i+1; return ans; } BigNum operator/(BigNum temp) { BigNum ans,t; BigNum low=BigNum(1),high,mid; int i; for(i=1;i<=a[0];i++) t.a[i]=high.a[i]=a[i]; t.a[0]=high.a[0]=a[0]; while(!(low>high)) { mid=(low+high)/2; if(mid*temp>t) high=mid-BigNum(1); else low=mid+BigNum(1); } if(!(low>t)&&!(temp*low>t)) return low; return high; } void operator+=(BigNum a) { *this=*this+a; } BigNum operator%(BigNum temp) { int i; BigNum t; for(i=1;i<=a[0];i++) t.a[i]=a[i]; t.a[0]=a[0]; return t-t/temp*temp; } BigNum power(int n) { BigNum ans=BigNum(1),temp=*this; while(n) { if(n&1) ans=ans*temp; temp=temp*temp; n>>=1; } return ans; } public: BigNum() { a[0]=1; a[1]=0; } BigNum(int x) { if(x>=MOD) a[0]=2,a[1]=x/MOD,a[2]=x%MOD; else a[0]=1,a[1]=x; } BigNum(i64 x) { stack s; while(x) { s.push(x%MOD); x/=MOD; } a[0]=s.size(); int k=0; while(!s.empty()) { a[++k]=s.top(); s.pop(); } } BigNum(string str) { int i; for(i=0;i (BigNum temp) { if(a[0]>temp.a[0]) return 1; if(a[0] temp.a[i]; return 0; } void print() { int i=1; while(i<=a[0]&&a[i]==0) i++; if(i>a[0]) { puts("0"); return; } printf("%lld",a[i++]); while(i<=a[0]) printf("%07lld",a[i++]); puts(""); } };BigNum f[2][22][22][22],ans;int n,m,w,h,K;int main(){ scanf("%d%d%d%d%d",&n,&m,&w,&h,&K); if(w>n)w=n; if(h>n)h=n; int i,j,k,t; int left,mid,right,u,d; f[0][0][0][0]=1; left=0; mid=min(n-w,m); right=max(m-(n-w),0); u=1;d=m-(n-h); if(m+h 0) f[i&1][j][k][t+1]+=f[(i-1)&1][j][k][t]*(right-t); f[i&1][j][k][t]+=f[(i-1)&1][j][k][t]; } } left=w;mid=min(n-w,m);right=abs(n-w-m); for(t=0;t<=left;t++) for(j=0;j<=mid;j++) for(k=0;k<=right;k++) { if(t+k+j==K) { ans+=f[d&1][t][j][k]; } } ans.print(); return 0;}
转载地址：http://qgkya.baihongyu.com/
