fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define gc getchar_unlocked
  4. #define fo(i,n) for(i=0;i<n;i++)
  5. #define Fo(i,k,n) for(i=k;i<n;i++)
  6. #define ll long long
  7. #define si(x)	scanf("%d",&x)
  8. #define sl(x)	scanf("%I64d",&x)
  9. #define ss(s)	scanf("%s",s)
  10. #define pb push_back
  11. #define mp make_pair
  12. #define F first
  13. #define S second
  14. #define all(x) x.begin(), x.end()
  15. #define clr(x) memset(x, 0, sizeof(x))
  16. #define sortall(x) sort(all(x))
  17. #define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
  18. #define PI 3.1415926535897932384626
  19. typedef pair<int, int>	pii;
  20. typedef pair<ll, ll>	pll;
  21. typedef vector<int>		vi;
  22. typedef vector<ll>		vl;
  23. typedef vector<pii>		vpii;
  24. typedef vector<pll>		vpll;
  25. typedef vector<vi>		vvi;
  26. typedef vector<vl>		vvl;
  27. const int mod = 1000000007;
  28. const int N = 1e5+3;
  29. int a, b, k, T;
  30. ll dp[103][N];
  31. ll dp2[103][N];
  32. int go(int t, int score){
  33. 	if (t == 0 and score <= 0)return 1;
  34. 	if (t == 0)return 0;
  35.  
  36. 	int i;
  37. 	ll ans ;
  38. 	if (score>=0){
  39. 		ans = dp[t][score];
  40. 	}
  41. 	else ans = dp2[t][-score];
  42. 	if (ans != -1) return ans;
  43. 	ans = 0;
  44. 	for(i=-2*k; i <= 2*k; i++){
  45. 		ll ways = max(0, 2*k - abs(i) + 1);
  46. 		if (ways>0){
  47. 			ans += (ways*(go(t-1, score-i)) ) % mod;
  48. 			ans %= mod;	
  49. 		}
  50.  
  51. 	}
  52. 	if (score>=0) dp[t][score] = ans;
  53. 	else dp2[t][-score] = ans;
  54. 	return ans;
  55. }
  56. int main()
  57. {
  58. 	ios_base::sync_with_stdio(false);
  59. 	cin.tie(NULL);
  60. 	int i, j;
  61. 	cin>>a>>b>>k>>T;
  62. 	Fo(i, 0, 103)Fo(j, 0, N) dp[i][j] = dp2[i][j] = -1;
  63. 	cout<<go(T, b-a+1);
  64. 	return 0;
  65. }
  66.  
  67.  
Success #stdin #stdout 0.04s 164416KB
comments (?)
stdin
copy 
1 1 1 2
stdout
copy 
31
https://ideone.com/dIPFqM
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!