#include #define ALL(A) (A).begin(), (A).end() #define ll long long #define rep(i, n) for (int i = 0; i < (n); i++) using namespace std; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } int dx[] = { 0, 1, -1, 0, 1, -1, 1, -1 }; // i<4:4way i<8:8way int dy[] = { 1, 0, 0, -1, 1, -1, -1, 1 }; const ll mod = 1e9 + 7; const ll INF = -1 * ((1LL << 63) + 1); const int inf = -1 * ((1 << 31) + 1); int ans; int n,s,k; int a[101][20001]; // a[i][j] := i人でちょうどj円支払う方法 int f(int n,int s){ // k = 0 のときn人でちょうどs円払う方法 if(a[n][s])return a[n][s]; // 0人で払えるのは0のみ s = 0 のとき 1 を返す if(n==0)return s==0; return a[n][s] = (f(n-1,s) + (s> n >> s >> k; s -= k*((n-1)*n)/2; if(s<0){ cout << 0 << endl; return 0; }else{ //cout << s << endl; cout << f(n,s) << endl; } }