/* * File: main.cpp * Author: acm * dp[i][0][k]表示第i位为0时各位相乘结果为k的个数, * dp[i][1][k]表示第i位为1时各位相乘结果为k的个数，则最后的结果数为两者之和 * Created on 2011年2月26日, 下午4:05 */ #include <cstdlib> #include <stdio.h> using namespace std; int const maxn=101; int dp[maxn][2][maxn]; int main(int argc, char** argv) { int cas,m,n,k,i,j; int p,q,r; scanf("%d",&cas); for(j=1;j<=cas;j++) { scanf("%d %d %d",&m,&n,&k); dp[1][0][0]=1; dp[1][1][1]=1; dp[1][1][0]=0; dp[1][0][1]=0; dp[2][0][0]=2;dp[2][0][1]=0;dp[2][1][0]=1;dp[2][1][1]=1; //以上为初始化 for(i=3;i<=n;i++) { dp[i][0][0]=dp[i-1][0][0]+dp[i-1][1][0]; dp[i][1][0]=dp[i-1][0][0]; //各位相乘为0的需要特殊处理 for(p=1;p<=k;p++) { dp[i][0][p]=dp[i-1][0][p]+dp[i-1][1][p]; dp[i][1][p]=dp[i-1][1][p-1]+dp[i-1][0][p]; } // printf("*%d %d",dp[i][0][1],dp[i][1][1]); } printf("%d %d/n",j,dp[n][0][k]+dp[n][1][k]); } return 0; }
