Cheerleaders UVA - 11806-白红宇

Cheerleaders UVA - 11806

阅读量：5146 次

发布时间：2019-06-13

本文共 1023 字，大约阅读时间需要 3 分钟。

题目大意是：

在一个m行n列的矩形网格中放置k个相同的石子，问有多少种方法？每个格子最多放一个石子，所有石子都要用完，并且第一行、最后一行、第一列、最后一列都要有石子。

容斥原理。如果只是n * m放石子,那么最后的结果，就是C(n*m,k).我们设A为第一行不放石头的总数,B为最后一行不放石子的总数,C为第一列不放石子的总数,D为最后一列不放石子的总数.则问题转化为在全集S中,求不在A,B,C,D部分的解.则答案为S - | A | - | B |- | C | - | D | + | A ^ B|......用一个二进制枚举状态,统计就可以了。

// Asimple#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #define INF 0x3f3f3f3f#define mod 1000007#define debug(a) cout<<#a<<" = "<
                 <
                  
                   > T; while( T-- ) { cin >> n >> m >> k; ans = 0; for(int s=0; s<16; s++) { cnt = 0; int r = n, c = m; if( s&1 ) { cnt++; r--; } if( s&2 ) { cnt++; r--; } if( s&4 ) { cnt++; c--; } if( s&8 ) { cnt++; c--; } if( cnt&1 ) ans = ( ans+mod - a[r*c][k])%mod; else ans = ( ans + a[r*c][k])%mod; } cout << "Case " << cas ++ << ": "; cout << ans << endl; }}int main() { input(); return 0;}

转载于:https://www.cnblogs.com/Asimple/p/7412588.html

你可能感兴趣的文章