fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. const long long MOD = 998244353;
  8.  
  9. long long solve(int n, int x) {
  10.     // Sử dụng dynamic programming
  11.     // dp[i][j] = số cách chọn i phần tử có tổng j
  12.     vector<vector<long long>> dp(n + 1, vector<long long>(x + 1, 0));
  13.  
  14.     dp[0][0] = 1; // Cách duy nhất để chọn 0 phần tử có tổng 0
  15.  
  16.     // Với mỗi số từ 1 đến x
  17.     for (int num = 1; num <= x; num++) {
  18.         // Duyệt ngược để tránh sử dụng cùng một số nhiều lần
  19.         for (int i = min(n, num); i >= 1; i--) {
  20.             for (int j = num; j <= x; j++) {
  21.                 dp[i][j] = (dp[i][j] + dp[i-1][j-num]) % MOD;
  22.             }
  23.         }
  24.     }
  25.  
  26.     long long result = 0;
  27.  
  28.     // Đếm các tập hợp có đúng n phần tử
  29.     for (int sum = n; sum <= x; sum++) {
  30.         result = (result + dp[n][sum]) % MOD;
  31.     }
  32.  
  33.     return result;
  34. }
  35.  
  36. int main() {
  37.     ios_base::sync_with_stdio(false);
  38.     cin.tie(NULL);
  39.  
  40.     int t;
  41.     cin >> t;
  42.  
  43.     while (t--) {
  44.         int n, x;
  45.         cin >> n >> x;
  46.  
  47.         cout << solve(n, x) << "\n";
  48.     }
  49.  
  50.     return 0;
  51. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VVnCGE
language:
C++ (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!