随笔-141  评论-9  文章-3  trackbacks-0

/*
ID: lorelei3
TASK: nocows
LANG: C++
*/


#include 
<fstream>

using namespace std;

const int K = 105;
const int N = 205;
const int MOD = 9901;

int dp[K][N];
int s[K][N];

int k,n;

int main(){

    
int i,j,m,c;

    ifstream 
in("nocows.in");
    ofstream 
out("nocows.out");

    
in>>n>>k;

    dp[
1][1]=1;

    
for(i=2; i<=k; ++i){
        
for(j=1; j<=n; j+=2)
            
for(m=1; m<=j-1-m; m+=2){
                
if(m==j-1-m)    c=1;
                
else    c=2;

                dp[i][j] 
+= c* ( dp[i-1][m]*s[i-2][j-1-m] +
                                dp[i
-1][j-1-m]*s[i-2][m] +
                                dp[i
-1][m]*dp[i-1][j-1-m] );
                dp[i][j] 
%= MOD;
            }

    
        
for(j=0; j<=n; ++j){
            s[i
-1][j] += dp[i-1][j] + s[i-2][j];
            s[i
-1][j] %= MOD;
        }

    }


    
out<<dp[k][n]<<endl;
    
return 0;
}
posted on 2010-12-21 10:17 小阮 阅读(188) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理