显示原始代码
#include <bits/stdc++.h>
using namespace std;
long long mod = pow(2, 31) - 1;
long long b[100005];
long long t[100005];
long long c[10005][10005];
long long fc(int, int);
long long tol(int);
long long find(int);
int main() {
int t;
scanf("%d", &t);
while (t--) {
long long n;
scanf("%lld", &n);
printf("%lld\n", find(n));
}
return 0;
}
long long find(int n) {
if (n == 0)
return 1;
if (b[n] == 0)
b[n] = tol(n - 1);
b[n] %= mod;
return b[n];
}
long long tol(int n) {
if (n == 0)
return 1;
if (t[n] == 0) {
for (int k = 0; k <= n; k++) {
t[n] += find(k) * fc(n, k);
t[n] %= mod;
}
}
return t[n];
}
long long fc(int n, int k) {
if (n == k)
return 1;
if (k == 0)
return 1;
if (c[n][k] == 0) {
c[n][k] = fc(n - 1, k) + fc(n - 1, k - 1);
}
c[n][k] %= mod;
return c[n][k];
}