fork(16) download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. int memo[101][101][2];
  5. int n,k;
  6. void init()
  7. {
  8.     for(int i=0;i<=n;i++)
  9.         for(int j=0;j<=n;j++)
  10.             for(int k=0;k<2;k++)
  11.                 memo[i][j][k]=-1;
  12. }
  13. int dp(int index,int current_k,int prev_bit)
  14. {
  15.     if(index==n)
  16.         return current_k==k;
  17.     int &ret=memo[index][current_k][prev_bit];
  18.     if(ret==-1)
  19.     {
  20.  
  21.         ret=dp(index+1,current_k+prev_bit,1);
  22.         ret+=dp(index+1,current_k,0);
  23.     }
  24.     return ret;
  25. }
  26. int main()
  27. {
  28.     int test;
  29.     int data_set_number;
  30.     scanf("%d",&test);
  31.     while(test--)
  32.     {
  33.         scanf("%d %d %d",&data_set_number,&n,&k);
  34.         init();
  35.         int ans=dp(0,0,0);
  36.          printf("%d %d\n",data_set_number,ans);
  37.     }
  38. return 0;
  39. }
  40.  
Success #stdin #stdout 0s 3424KB
comments (?)
stdin
copy 
10
1 5 2
2 20 8
3 30 17
4 40 24
5 50 37
6 60 52
7 70 59
8 80 73
9 90 84
10 100 90
stdout
copy 
1 6
2 63426
3 1861225
4 168212501
5 44874764
6 160916
7 22937308
8 99167
9 15476
10 23076518
https://ideone.com/ei6KjP
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!