都是经典题了吧。。我好无聊。。
4806-1801是双倍经验。。DP方程看代码吧。。
/* http://www.cnblogs.com/karl07/ */
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std; #define ll long long
//#define P 9999973 //bzoj1801
#define P 999983 //bzoj4806
#define C(x) ((x)*(x-1)/2)
int n,m;
ll f[][][]; int main(){
scanf("%d%d",&n,&m);
f[][][]=;
for (int i=;i<=n;i++){
for (int j=;j<=m;j++){
for (int k=;k<=m-j;k++){
f[i][j][k]+=f[i-][j][k];
if (j>=) f[i][j][k]+=f[i-][j-][k]*(m-j-k+);
if (k>= && j<=m-)f[i][j][k]+=f[i-][j+][k-]*(j+);
if (j>=) f[i][j][k]+=f[i-][j-][k]*C(m-j-k+);
if (k>= && j<=m-)f[i][j][k]+=f[i-][j+][k-]*C(j+);
if (j>= && k>=) f[i][j][k]+=f[i-][j][k-]*j*(m-j-k+);
f[i][j][k]%=P;
}
}
}
ll ans=;
for (int i=;i<=m;i++){
for (int j=;j<=m-i;j++){
ans+=f[n][i][j];
ans%=P;
}
}
printf("%lld\n",ans);
return ;
}
炮
就是 max(m,n) C min (m,n)
/* http://www.cnblogs.com/karl07/ */
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
struct INT {
int b,a[];
INT (){b=; for (int i=;i<=;i++) a[i]=;}
};
int A,B,c,n,m;
int P[],p[],cnt[],ip[];
INT Int(int x){
INT a;
for (a.b= ; x ; a.a[++a.b]=x%,x/=);
return a;
} INT operator * (const INT &x,const INT &y){
INT a;
a.b=min(,x.b+y.b-);
for (int i=;i<=x.b;i++) for (int j=;j<=y.b;j++) if (i+j-<=) a.a[i+j-]+=x.a[i]*y.a[j];
for (int i=;i<=a.b;a.b+=(i==a.b && a.a[i+] && i+<=),i++) a.a[i+]+=a.a[i]/,a.a[i]%=;
for (;a.a[a.b]== && a.b!=; a.b--);
return a;
} void print_INT(INT x){
for (int i=min(x.b,);i>=;i--) printf("%d",x.a[i]);
puts("");
} void Prime(int n){
for (int i=;i<=n;i++){
if (!P[i]){
p[++c]=i,ip[i]=c;
for (int j=i+i;j<=n;j+=i) P[j]=;
}
}
} void pt(int x) {
printf("%d\n",x);
} void fac(int x,int y){
for (int i=;i<=c && P[x];i++) while (!(x%p[i])) x/=p[i],cnt[i]+=y;
cnt[ip[x]]+=y;
} INT ans=Int();
int main(){
scanf("%d%d",&A,&B);
n=max(A,B),m=max(max(A,B)-min(A,B),min(A,B));
Prime(n);
for (int i=m+;i<=n;i++) fac(i,);
for (int i=;i<=n-m;i++) fac(i,-);
for (int i=;i<=c;i++) while (cnt[i]--) ans=ans*Int(p[i]);
print_INT(ans);
return ;
}
车
黑白染色然后匈牙利
/* http://www.cnblogs.com/karl07/ */
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std; struct edge{
int next,to;
}e[];
int ade,n,m,cnt,T,c;
int x[]={,,-,-,-,,,-};
int y[]={,,-,-,,-,-,};
int mp[][],id[][],first[],vis[],match[]; void addedge(int x,int y){
e[++ade].next=first[x];
e[ade].to=y;
first[x]=ade;
} bool check(int x,int y){
return (x>= && x<=n && y>= && y<=m && !mp[x][y]);
} #define s e[x].to
bool hungary(int p){
for (int x=first[p];x;x=e[x].next){
if (vis[s]!=T){
vis[s]=T;
if (!match[s] || hungary(match[s])) {match[s]=p; return ;}
}
}
return ;
}
#undef s int main(){
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++){
for (int j=;j<=m;j++){
scanf("%d",&mp[i][j]);
cnt+=(!mp[i][j]);
id[i][j]=++c;
}
}
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
if (((i+j)&) && !mp[i][j])for (int k=;k<;k++) if (check(i+x[k],j+y[k])) addedge(id[i][j],id[i+x[k]][j+y[k]]);
for (int i=;i<=n;i++){
for (int j=;j<=m;j++){
if (!mp[i][j] && ((i+j)&)){
T=id[i][j];
cnt-=hungary(T);
}
}
}
printf("%d\n",cnt);
return ;
}
马
直接dfs
/* http://www.cnblogs.com/karl07/ */
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std; int n,ans;
int ban[][],y[],a[],b[]; void dfs(int i){
if (i>n) {ans++; return;}
for(int j=;j<=n;j++) if (!(ban[i][j] || y[j] || a[i+j-] || b[n-i+j] )){
y[j]=a[i+j-]=b[n-i+j]=;
dfs(i+);
y[j]=a[i+j-]=b[n-i+j]=;
}
} int main(){
scanf("%d",&n);
for (int i=;i<=n;i++) for (int j=;j<=n;j++) scanf("%d",&ban[i][j]);
dfs();
printf("%d\n",ans);
return ;
}
皇后