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;

}

#include<bits/stdc++.h> #define int long long using namespace std; const int inf = 0x3f3f3f3f; const int N = 1001; int dp[N][N]; //vector<int> c[N];//重量 //vector<int> w[N];//价值 //int sum[N]; int c[N]; int w[N]; const int ans = 1e9 + 9; //int s[N];//数量 //dp[i][j] //代表前i个物品时背包体积最大为j时物品最大价值 //dp[i - 1][j] 不选 //dp[i - 1][j - c[i]] + w[i] 选 signed main(){ freopen("divide.in" , "r" , stdin); freopen("divide.out" , "w" , stdout); int m; cin >> m; //dp[i][j] //表示前i个数和刚好为j的方案数 while(m --){ memset(dp , 0 , sizeof(dp)); int n; cin >> n; dp[0][0] = 1; for(int i = 1 ; i <= n ; i ++){//数 for(int j = 0 ; j <= n ; j ++){//容量 if(j >= i){ dp[i][j] = (dp[i - 1][j] + dp[i][j - i]) % ans; }else{ dp[i][j] = dp[i - 1][j]; } } }

cout << dp[n][n] % ans << endl; 
}
return 0;

}