炮(cannon)
【题目描述】
众所周知，双炮叠叠将是中国象棋中很厉害的一招必杀技。炮吃子时必须
隔一个棋子跳吃，即俗称“炮打隔子”。 炮跟炮显然不能在一起打起来，于是rly
一天借来了许多许多的炮在棋盘上摆了起来……他想知道，在N×M的矩形方格
中摆若干炮（可以不摆）使其互不吃到的情况下方案数有几种。
棋子都是相同的。
【输入说明】
一行，两个正整数N和M。
【输出说明】
一行，输出方案数mod 999983。
【样例输入】
1 3
【样例输出】
7
【数据范围】
对于40%的数据,N<=4,M<=4
对于70%的数据,N<=100,M<=8
对于100%的数据,N<=100,M<=100
/*
动态规划，状态的表示很巧妙
f[i][j][k]表示放了前i行，有j列放了1个，有k列放了2个，那么就有m-i-j列没放的方案数。然后完成转移。
*/
#include<cstdio>
#include<iostream>
#define mod 999983LL
#define N 110
using namespace std;
long long f[N][N][N],n,m;
int main()
{
//freopen("cannon.in","r",stdin);
//freopen("cannon.out","w",stdout);
cin>>n>>m;
f[][][]=;
for(long long i=;i<=n;i++)
for(long long j=;j<=m;j++)
for(long long k=;j+k<=m;k++)
{
f[i][j][k]=f[i-][j][k];f[i][j][k]%=mod;//不放
if(j>=)f[i][j][k]+=f[i-][j-][k]*(m-j-k+);f[i][j][k]%=mod;//空处放1个
if(k>=)f[i][j][k]+=f[i-][j+][k-]*(j+);f[i][j][k]%=mod;//1个处放1个
if(j>=)f[i][j][k]+=f[i-][j-][k]*(m-j-k+)*(m-j-k+)/;f[i][j][k]%=mod;//空处放2个
if(k>=)f[i][j][k]+=f[i-][j+][k-]*(j+)*(j+)/;f[i][j][k]%=mod;//1处放2个
if(k>=)f[i][j][k]+=f[i-][j][k-]*j*(m-j-k+);f[i][j][k]%=mod;//空处和1个处
}
long long ans=;
for(long long j=;j<=m;j++)
for(long long k=;j+k<=m;k++)
ans+=f[n][j][k],ans%=mod;
cout<<ans;
fclose(stdin);fclose(stdout);
return ;
}
车(rook)
【题目描述】
众所周知，车是中国象棋中最厉害的一子之一，它能吃到同一行或同一列
中的其他棋车。车跟车显然不能在一起打起来，于是rly一天又借来了许多许多
的车在棋盘上摆了起来……他想知道，在N×M的矩形方格中摆最多个数的车使
其互不吃到的情况下方案数有几种。但是，由于上次摆炮摆得实在太累，他为
了偷懒，打算增加一个条件：对于任何一个车A，如果有其他一个车B在它的上
方（车B行号小于车A），那么车A必须在车B的右边（车A列号大于车B）。
棋子都是相同的。
【输入说明】
一行，两个正整数N和M。
【输出说明】
一行，输出方案数的末尾50位（不足则直接输出）。
【样例输入】
2 2
【样例输出】
1
【数据范围】
对于20%的数据， N<=10， M<=10。
对于40%的数据， N<=40， M<=40。
对于70%的数据， N<=10000， M<=10000。
对于100%的数据， N<=1000000， M<=1000000。
/*
我们保证n<m，因为题目要求尽量多放，所以一定放n个，答案就是C(m,n)，直接上高精度会超时，要先分解一下质因数，然后再做。
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#define N 1000010
#define M 101
using namespace std;
int f[N],prime[N],p[N],c[N],n,m,num;
int a1[M],b1[M],c1[N];
struct node
{
node()
{
memset(q,,sizeof(q));len=;
}
int q[M],len;
};node ans;
void gprime()
{
for(int i=;i<=m;i++)
if(!f[i])
{
prime[++num]=i;p[i]=num;
for(int j=;i*j<=m;j++)
f[i*j]=;
}
}
void work1(int x)
{
for(int i=;i<=num;i++)
{
while(x%prime[i]==)c[i]++,x/=prime[i];
if(!f[x]){c[p[x]]++;break;}
if(x==)break;
}
}
void work2(int x)
{
for(int i=;i<=num;i++)
{
while(x%prime[i]==)c[i]--,x/=prime[i];
if(!f[x]){c[p[x]]--;break;}
if(x==)break;
}
}
node cheng(node a,int b)
{
memset(a1,,sizeof(a1));
memset(b1,,sizeof(b1));
node c;
int len=a.len;
for(int i=;i<=a.len;i++)a1[i]=a.q[len-i+];
for(int i=;i<=len;i++)
{
b1[i]+=a1[i]*b;
b1[i+]+=b1[i]/;
b1[i]%=;
}
while(b1[len+]>=)
{
b1[len+]=b1[len+]/;
b1[len+]%=;
len++;
}
if(b1[len+])len++;
c.len=min(,len);
for(int i=;i<=c.len;i++)c.q[i]=b1[c.len-i+];
return c;
}
int main()
{
//freopen("rook.in","r",stdin);
//freopen("rook.out","w",stdout);
scanf("%d%d",&n,&m);
if(n>m)swap(n,m);
gprime();
for(int i=m;i>=m-n+;i--)
work1(i);
for(int i=;i<=n;i++)
work2(i);
ans.len=;ans.q[]=;
for(int i=;i<=num;i++)
for(int j=;j<=c[i];j++)
ans=cheng(ans,prime[i]);
for(int i=max(,ans.len-);i<=ans.len;i++)
printf("%d",ans.q[i]);
return ;
}
皇后(queen)
【题目描述】
众所不知， rly现在不会玩国际象棋。但是，作为一个OIer， rly当然做过八
皇后问题。这里再啰嗦几句，皇后可以攻击到同行同列同对角线，在n*n的方格
中摆n个皇后使其互不攻击到，求不同的解的数量，这就是经典的n皇后问题。
现在问题推广到n皇后问题，这个问题对于你而言实在是小菜一叠。但因为上一
次rly把棋盘弄破了，又拿不出新的，所以rly打算难一点点，问题就是破棋盘上
的n皇后问题。他想知道……（你们懂的）。
棋子都是相同的。
【输入说明】
一行，一个正整数N。
接下来N行，每行N个数，要么为0，表示没坏，要么1，表示坏了。
【输出说明】
一行，输出不同的解的数量。
【样例输入】
4
1 0 1 1
1 1 1 0
0 1 1 1
1 1 0 1
【样例输出】
1
【数据范围】
对于40%的数据， N<=13。
对于100%的数据， N<=16。
其中有30%的数据，棋盘没有破（你可以认为rly又去买了一个新的）。
/*位运算优化n皇后*/
#include<cstdio>
#include<iostream>
#define N 20
using namespace std;
int hang[N],n,ans;
void dfs(int t,int a,int b,int c)//a，b，c都是二进制数，表示哪一列或对角线是否放过皇后，1为放过
{
if(t==n+)
{
ans++;return;
}
int S=((<<n)-)&(~(hang[t]|a|b|c));
/*
S是一个二进制数，表示当前可以往哪一列放皇后
(hang[t]|a|b|c)表示哪些列从列和对角线的角度来说都放过
加上~（取反），表示哪些列可以放皇后
*/
while(S)
{
int x=S&(-S);//x表示可以当前放皇后的位置
dfs(t+,a+x,(b+x)<<,(c+x)>>);
S-=x;
}
}
int main()
{
//freopen("queen.in","r",stdin);
//freopen("queen.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
int x;scanf("%d",&x);
hang[i]+=x<<(j-);
}
dfs(,,,);
printf("%d",ans);
return ;
}