7月17作业的第二题 传送门：题目详情 - 整数划分 - JMYSOJ (jmfes.com) #include<bits/stdc++.h> using namespace std;

long long dp[1010]; const int N = 1e9 + 9;

int main(){ freopen("divide.in","r",stdin); freopen("divide.out","w",stdout); int v; cin >> v; for(int j = 1; j <= v; j ++){ memset(dp, 0, sizeof(dp)); dp[0] = 1; int n; cin >> n; for (int i = 1; i <= n; i ++) { for (int j = i; j <= n; j ++) { dp[j] = (dp[j - i] + dp[j]) % N; } } cout << dp[n] % N << endl; }

return 0;

}