QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#345934 | #3202. Pascal's Hyper-Pyramids | KhNURE_KIVI# | AC ✓ | 1ms | 3860kb | C++20 | 2.2kb | 2024-03-07 17:25:51 | 2024-03-07 17:25:52 |
Judging History
answer
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#include <bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<typename T>
bool umin(T &a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool umax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif
const int max_n = 32, inf = 1000111222;
__int128 f[max_n];
int d,h;
int buf[max_n];
vector<ll> ans;
void add_buf_to_ans()
{
int s=0;
for (int i=0;i<d;i++){
s+=buf[i];
}
__int128 res=f[s];
for (int i=0;i<d;i++){
res/=f[buf[i]];
}
ans.pb(ll(res));
// for (int i=0;i<d;i++){
// cout<<buf[i]<<" ";
// }
// cout<<"\n";
}
void rec(int pos,int sum)
{
if (sum>h || (pos!=d-1 && sum+(pos+1)*buf[pos+1]<h)){
return;
}
if (pos==-1){
assert(sum==h);
add_buf_to_ans();
return;
}
for (int i=0;sum+i<=h && (pos==d-1 || buf[pos]+i<=buf[pos+1]);i++){
buf[pos]+=i;
rec(pos-1,sum+i);
buf[pos]-=i;
}
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
f[0]=1;
for (int i=1;i<max_n;i++){
f[i]=f[i-1]*i;
}
cin>>d>>h;
h--;
for (int i=0;i<d;i++){
buf[i]=0;
}
rec(d-1,0);
sort(all(ans));
ans.resize(unique(all(ans))-ans.begin());
for (auto i:ans){
cout<<i<<"\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3548kb
input:
2 2
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
2 6
output:
1 5 10
result:
ok 3 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
3 2
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
3 3
output:
1 2
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
3 4
output:
1 3 6
result:
ok 3 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
3 7
output:
1 6 15 20 30 60 90
result:
ok 7 lines
Test #7:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
4 3
output:
1 2
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 1ms
memory: 3608kb
input:
4 4
output:
1 3 6
result:
ok 3 lines
Test #9:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
5 5
output:
1 4 6 12 24
result:
ok 5 lines
Test #10:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
5 8
output:
1 7 21 35 42 105 140 210 420 630 840 1260
result:
ok 12 lines
Test #11:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
5 31
output:
1 30 435 870 4060 12180 24360 27405 109620 142506 164430 328860 593775 657720 712530 1425060 2035800 2850120 3562650 4275180 5852925 8550360 8906625 11875500 14250600 14307150 17813250 30045015 35626500 42751800 46823400 53439750 54627300 71253000 85503600 86493225 106879500 119759850 128764350 1454...
result:
ok 543 lines
Test #12:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
10 5
output:
1 4 6 12 24
result:
ok 5 lines
Test #13:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
10 10
output:
1 9 36 72 84 126 252 504 630 756 1260 1512 1680 2520 3024 3780 5040 7560 10080 15120 22680 30240 45360 60480 90720 181440 362880
result:
ok 27 lines
Test #14:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
10 20
output:
1 19 171 342 969 2907 3876 5814 11628 15504 23256 27132 46512 50388 58140 75582 92378 93024 116280 162792 232560 348840 352716 406980 542640 604656 697680 813960 831402 923780 1058148 1395360 1627920 1763580 2116296 2441880 3255840 3325608 4157010 4232592 4883760 5290740 6651216 7054320 7759752 8314...
result:
ok 257 lines
Test #15:
score: 0
Accepted
time: 1ms
memory: 3500kb
input:
10 25
output:
1 24 276 552 2024 6072 10626 12144 42504 63756 127512 134596 212520 255024 346104 425040 735471 807576 850080 1275120 1307504 1961256 2018940 2422728 2496144 2550240 2691920 2704156 4037880 5100480 5883768 7268184 8075760 11767536 12113640 14536368 16151520 19612560 20593188 24227280 27457584 324498...
result:
ok 632 lines
Test #16:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
20 10
output:
1 9 36 72 84 126 252 504 630 756 1260 1512 1680 2520 3024 3780 5040 7560 10080 15120 22680 30240 45360 60480 90720 181440 362880
result:
ok 27 lines
Test #17:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
20 20
output:
1 19 171 342 969 2907 3876 5814 11628 15504 23256 27132 46512 50388 58140 75582 92378 93024 116280 162792 232560 348840 352716 406980 542640 604656 697680 813960 831402 923780 1058148 1395360 1627920 1763580 2116296 2441880 3255840 3325608 4157010 4232592 4883760 5290740 6651216 7054320 7759752 8314...
result:
ok 296 lines
Test #18:
score: 0
Accepted
time: 1ms
memory: 3860kb
input:
21 21
output:
1 20 190 380 1140 3420 4845 6840 15504 19380 29070 38760 58140 77520 116280 125970 155040 167960 184756 232560 310080 465120 542640 581400 775200 930240 1007760 1162800 1511640 1627920 1847560 1860480 2325600 2713200 3255840 3488400 3527160 4651200 6046560 6976800 7054320 8139600 8314020 8817900 923...
result:
ok 366 lines
Test #19:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
31 10
output:
1 9 36 72 84 126 252 504 630 756 1260 1512 1680 2520 3024 3780 5040 7560 10080 15120 22680 30240 45360 60480 90720 181440 362880
result:
ok 27 lines
Test #20:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
31 20
output:
1 19 171 342 969 2907 3876 5814 11628 15504 23256 27132 46512 50388 58140 75582 92378 93024 116280 162792 232560 348840 352716 406980 542640 604656 697680 813960 831402 923780 1058148 1395360 1627920 1763580 2116296 2441880 3255840 3325608 4157010 4232592 4883760 5290740 6651216 7054320 7759752 8314...
result:
ok 296 lines
Test #21:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
31 21
output:
1 20 190 380 1140 3420 4845 6840 15504 19380 29070 38760 58140 77520 116280 125970 155040 167960 184756 232560 310080 465120 542640 581400 775200 930240 1007760 1162800 1511640 1627920 1847560 1860480 2325600 2713200 3255840 3488400 3527160 4651200 6046560 6976800 7054320 8139600 8314020 8817900 923...
result:
ok 366 lines