6415 Rikka with Nash Equilibrium

题意：已知n， m， k，求仅有一个  pure strategy Nash equilibriums（六花选行号， 勇太选列号，对应数字即为结果，psne即对于当前矩阵，两人都无法通过单独改变自己的选择增大结果）的n*m矩阵有几种，答案模k。

（1. Each integer in [1,nm] occurs exactly once in A.

2. The game has at most one pure strategy Nash equilibriums.）

思路：dp[i][j][k]表示（从大到小）放置第i个数字于某j行k列合法。

其中，dp[1][1][1] = (n*m) , i|2...n*m, j|1...n, k|1...m; 

j*k > i-1时有如下

dp[i][j][k] = (dp[i-1][j-1][k] * k * (n-j+1)//贡献一个额外的可行列， 可行列k*可行列上未使用行（n -（j-1））。

              +  dp[i-1][j][k-1] * j * (m-k+1)//同上。

              +  dp[i-1][j][k]    * (j*k - (i-1))//无贡献（置于交叉点上）， j*k个可行交叉点 - （i-1）个已使用交叉点。

ps：中途转long long每次只取一次模可大大减少耗时。

 

 

1 #include 
      
        2 #include 
       
         3 #include
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 #include 
                  
                 
                
               
              
             
            
           
          
         
        
       
      

算出样例之后就沉浸于递归的思路无法自拔，然而。。。递归->记忆化搜索->（递推？）动态规划。。。想到递归之后上手写一下记忆化搜索的话可能就想到dp了，脑速不够还不动手就很不ok。。。 

就算不推dp，直接记忆化搜索也能过，啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊。。。为啥窝不写啊啊啊啊啊啊啊啊啊啊啊啊啊。。。总是拿窝的算法太暴力当借口不写题到最后毛都不会。。。

1 #include
      
        2 using namespace std; 3 typedef long long ll; 4 ll mod,n,m; 5 const ll N=6405; 6 ll dp[85][85][85*85]; 7 ll dfs(ll x,ll y,ll z){
    //占领了x行，y列。已经放进去了z个数字 8     if(dp[x][y][z]!=-1) return dp[x][y][z]; 9     ll tmp=0;10     if(x
       
        z) tmp=(tmp+(x*y-z)%mod*dfs(x,y,z+1))%mod;13     return dp[x][y][z]=tmp;14 }15 int main()16 {17     ll t;18     scanf("%lld",&t);19     while(t--){20         memset(dp,-1,sizeof(dp));21         scanf("%lld%lld%lld",&n,&m,&mod);22         dp[n][m][n*m]=1;23         ll ans=m*n%mod*dfs(1,1,1)%mod;24         printf("%lld\n",ans);25     }26 }
       
      

（但是真的很慢，4000+ms卡过。）

hdu 6406 Taotao Picks Apples 思路：二分吖upper_bound吖～模拟吖！！！（手残党，WA地一声哭出来。）

 

1 #include 
      
        2 #include 
       
         3 #include
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 #include 
                  
                 
                
               
              
             
            
           
          
         
        
       
      

 

 

hdu6400 Parentheses Matrix

思路：牺牲小我，拯救全家。

1 #include 
      
        2 #include 
       
         3 #include
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 #include