bzoj4806——炮

　　题目传送门：

　　这种题一看就是dp。。。我们可以设$ f[i][j][k] $表示处理到第$ i $行，有$ j $列没放炮，$ k $列只放了一个炮。接着分情况讨论：第$ i $行不放炮、放一个炮、放两个炮；放在只有一个炮的列上，还是放在没炮的列上。于是就可以快乐地列方程了：

　　$ \begin{equation} \begin{split} f[i][j][k] &= f[i-1][j][k] \\ &+ (j+1)\cdot f[i-1][j+1][k-1] \\ &+ (k+1)\cdot f[i-1][j][k+1] \\ &+ \binom{j+2}{2} \cdot f[i-1][j+2][k-2] \\ &+ (j+1)\cdot k\cdot f[i-1][j+1][k] \\ &+ \binom{k+2}{2}\cdot f[i-1][j][k+2] \end{split} \end{equation} $

　　另外，此题有双倍经验：（我是不会告诉你模数不一样的）

　　代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #define ll long long#define max(a,b) (a>b?a:b)#define min(a,b) (a
              
               1)f[i][j][k]+=f[i-1][j+2][k-2]*(j+2)*(j+1)/2; f[i][j][k]%=mod; } ll ans=0; for(j=0;j<=m;j++) for(k=0;k+j<=m;k++) ans=(ans+f[n][j][k])%mod; printf("%lld\n",ans); }
              
             
            
           
          
         
        
       
      

bzoj4807——车

　　题目传送门：

　　这题一看就是组合数。。。就是加了个高精度罢了。

　　代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
             
            
           
          
         
        
       
      

bzoj4808——马

　　题目传送门：

　　其实如果把棋盘相邻块黑白染色，那么我们可以发现马每跳一步只会跳到异色格，所以直接互相连边，跑二分图匹配就行了。

　　听说您像我一样用dinic跑二分图匹配？那得加当前弧优化。（至少我要加才能过）

　　另外，此题也有双倍经验：

　　代码：

#include
      
       #include
       
        #define min(a,b) (a
        
         =n||yy<0||yy>=m)continue;                    add(i*m+j+1,xx*m+yy+1,1);                 }            }    for(int i=0;i
        
       
      

bzoj4809——皇后

　　题目传送门：

　　其实数据水，爆搜就能过，而且这道题好像也没什么靠谱的解法。

　　代码：

#include
      
       int mp[20][20],vis0[20],vis1[40],vis2[40];int n,ans=0;void dfs(int now){    if(now>n){        ++ans; return;    }    for(int i=1;i<=n;i++)        if(!mp[now][i]&&!vis0[i]&&!vis1[now+i]&&!vis2[n+now-i]){            vis0[i]=1; vis1[now+i]=1; vis2[n+now-i]=1;            dfs(now+1);            vis0[i]=0; vis1[now+i]=0; vis2[n+now-i]=0;        }}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)            scanf("%d",&mp[i][j]);    dfs(1);    printf("%d\n",ans);}