[阶乘进位制] UOJ82. 【UR #7】水题生成器

大暴力可过,但题解有更高姿势的做法

阶乘进位制,大概是 \(\sum_i i!*a_i \ (a_i<i+1)\)

把阶乘进位制倒过来,即用下降幂:\(\sum_i n^{\underline i}a_i \ (a_i<n-i)\) ,就能满足是 \(n!\) 的约数,很神奇。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long uLL;
uLL n,m,N;
int main(){
scanf("%llu%llu",&n,&m);
N=1; for(int i=2;i<=n;i++) N=N*i;
for(int i=1;i<=n;i++){
N/=i;
if(m>N){
printf("%llu\n",(m/N)*N);
m-=(m/N)*N;
}
}
if(m) printf("1");
return 0;
}