UVaLive 7365

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <cmath> #include <vector> #include <map> using namespace std; typedef long long LL; bool vis[37]; LL dp[37][37]; LL kase; template <class TTT> inline void read(TTT &num) { char ch; while(ch = getchar(), ch < '0' || ch > '9'); num = ch-'0'; while(ch = getchar(), ch >= '0' && ch <= '9') num = num*10+ch-'0'; } int c[100007]; int main() { read(kase); while(kase--) { memset(vis, false, sizeof vis); memset(dp, 0, sizeof(dp)); int K, n, m,k; read(K); read(n); read(m); read(k); for(int i = 0; m+i*k <= n; ++i) vis[m+i*k] = true; int len = 0; for(int i = 1; i <= n; ++i) if(!vis[i]) c[len++] = i; //前i, c[j]开头 for(int i = 1; i <= n; ++i) { for(int j = 0; j < len; ++j) { if(i == c[j]) dp[i][c[j]] = 1; for(int k = 0; k < len; ++k) { if(i > c[j]) dp[i][c[j]] += dp[i-c[j]][c[k]]; } } } LL ans = 0; for(int i = 0; i < len; ++i) { ans += dp[n][c[i]]; // printf("%lld ", dp[n][c[i]]); } // puts(""); // printf("ans: %d %lld\n", K, ans); printf("%d %lld\n", K, ans); } }