fork download
copy 
  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<cmath>
  4. #include<string>
  5. #include<cstring>
  6. #include<algorithm>
  7. #include<vector>
  8. #include<map>
  9. #include<utility>
  10. #define PB push_back
  11. #define MP make_pair
  12. #define LL long long int
  13. #define M 1000000007
  14. using namespace std;
  15.  
  16. LL ways[100001][30];
  17. int fib[25]={1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393};
  18.  
  19. void solve()
  20. {
  21. 	int i,j,d,k,f;
  22. 	for(j=0;j<30;j++)
  23. 	{
  24. 		ways[0][j] = 0;
  25. 		ways[1][j] = 1;
  26. 	}
  27. 	for(i=0;i<24;i++)
  28. 	{
  29. 		for(j=0;j<25;j++)
  30. 		{
  31. 			if(fib[i] != fib[j])
  32. 			ways[fib[i]][j]=1;
  33. 		}
  34. 	}
  35.  
  36. 	ways[1][0] = 0;
  37. 	for(f=0;f<25;f++)
  38. 	{
  39. 		k = fib[f];
  40. 		for(i=2;i<=100000;i++)
  41. 		{
  42. 			//if(binary_search(fib,fib+26,i))
  43. 			{
  44. 				for(j=0;j<25;j++)
  45. 				{
  46.  
  47. 					if(fib[j] > i/2)
  48. 					break;
  49. 					if(fib[j] == k )
  50. 					continue;
  51. 					ways[i][f] = ways[i][f] + ways[i-fib[j]][f];
  52. 					//if(i == fib[j])
  53. 					//ways[i][f]++;
  54. 					if(i == 8)
  55. 					cout<<i<<" "<<f<<" "<<fib[j]<<" "<<ways[i][f]<<endl;
  56.  
  57. 					//cout<<i<<" "<<k<<" "<<fib[j]<<" "<<ways[i][f]<<endl;
  58. 					//system("pause");
  59. 					ways[i][f] %= M;
  60.  
  61. 				}
  62. 			}
  63. 		}
  64. 	}
  65. }
  66.  
  67.  
  68. int main()
  69. {
  70. 	int t,i,j,k,n;
  71. 	solve();
  72. 	cin>>t;
  73. 	while(t--)
  74. 	{
  75. 		cin>>n>>k;
  76. 		for(i=0;i<25;i++)
  77. 		{
  78. 			if(fib[i] == k)
  79. 			{
  80. 				cout<<ways[n][i]<<endl;
  81. 				break;
  82. 			}
  83. 		}
  84. 		//cout<<ways[n][k]<<endl;
  85. 	}
  86. 	return 0;
  87. }
  88.  
Time limit exceeded #stdin #stdout 15s 26168KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
8 0 2 3
8 0 3 5
8 1 1 8
8 1 3 11
8 2 1 19
8 2 2 30
8 3 1 30
8 3 2 46
8 3 3 54
8 4 1 31
8 4 2 48
8 4 3 57
8 5 1 32
8 5 2 49
8 5 3 58
8 6 1 32
8 6 2 49
8 6 3 58
8 7 1 32
8 7 2 49
8 7 3 58
8 8 1 32
8 8 2 49
8 8 3 58
8 9 1 32
8 9 2 49
8 9 3 58
8 10 1 32
8 10 2 49
8 10 3 58
8 11 1 32
8 11 2 49
8 11 3 58
8 12 1 32
8 12 2 49
8 12 3 58
8 13 1 32
8 13 2 49
8 13 3 58
8 14 1 32
8 14 2 49
8 14 3 58
8 15 1 32
8 15 2 49
8 15 3 58
8 16 1 32
8 16 2 49
8 16 3 58
8 17 1 32
8 17 2 49
8 17 3 58
8 18 1 32
8 18 2 49
8 18 3 58
8 19 1 32
8 19 2 49
8 19 3 58
8 20 1 32
8 20 2 49
8 20 3 58
8 21 1 32
8 21 2 49
8 21 3 58
8 22 1 32
8 22 2 49
8 22 3 58
8 23 1 32
8 23 2 49
8 23 3 58
8 24 1 32
8 24 2 49
8 24 3 58
https://ideone.com/erENot
language:
C++ 4.3.2 (gcc-4.3.2)
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!