【模板】康拓展开与康拓逆展开

【模板】康拓展开与康拓逆展开

康拓展开与逆展开链接：.html(标准模板)

康拓展开：比当前位置小的数的个数*阶乘 

习题：/problem/139

#include <iostream>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstdio>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const ll maxn = 1e5+100;
const ll mod = 998244353;
const ld pi = acos(-1.0);
const ll inf = 1e18;ll n,fac[15];
bool flag[15];void getnum()
{fac[0] = 1;fac[1] = 1;for(ll i = 2; i <= 15; i++){fac[i] = fac[i-1]*i;}return ;
}int main()
{ios::sync_with_stdio(false);getnum();	// 获取阶乘结果 cin >> n;while(n--){memset(flag,0,sizeof(flag));string s;cin >> s;ll ans = 0;for(ll i = 0; i < s.size()-1; i++){ll num = 0;flag[ s[i]-'a' ] = 1;  //标记出现过 for(ll j = 0; j < s[i]-'a'; j++)  //枚举比s[i]小的字符 {if(flag[j] == 0)num++;    }ans += num*fac[ 12 - i - 1 ];  //个数*阶乘 }	cout << ans+1 << endl;	}return 0;
}

康拓逆展开：

习题：/problem/143

 注意阶乘数组 fac[0] = 1

#include <iostream>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstdio>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const ll maxn = 1e5+100;
const ll mod = 998244353;
const ld pi = acos(-1.0);
const ll inf = 1e18;ll n,fac[15],T;
bool flag[15];void getnum()
{fac[0] = 1;fac[1] = 1;for(ll i = 2; i <= 15; i++){fac[i] = fac[i-1]*i;}return ;
}int main()
{ios::sync_with_stdio(false);getnum();	// 获取阶乘结果 cin >> T;while(T--){memset(flag,0,sizeof(flag));cin >> n;n--;ll len = 12;  //字符串长度 string ans;for(ll i = 1; i <= len; i++){ll t = n/fac[len - i]; //代表有t个数字比当前数字小 n = n%fac[len-i];ll temp = 0,num = 0;  //temp表示用过的数，num表示没用过的 for(ll j = 0; j < len; j++){if(num > t)  //找到t个没用过的数字就可以停止了 break;if(flag[j] == 1) // 用过的 {temp++;}else{num++;}}flag[temp+num-1] = 1;ans += char('a'+ (temp+num-1) );//cout << ans << endl;}cout << ans << endl;}return 0;
}