51nod_3209 康托展開
沒有了解康托展開的可以先去看看：都能看懂的康托展開.
題目對康托展開進行了拓展：有重復數字的康托展開，
參考思路如下：
但是上面說的太過粗略，接下來較為嚴謹的分析下：
- 題目中的
t
o
t
a
l
total
total指的是總排列數量：
s
u
m
!
sum!
sum!是所有元素的排列組合的方式，除以每個元素所占的數量的階乘，就是去除這個元素的重復所帶來的多的排列的方式(高中知識)，
得出：
-
首先，要注意的是，一定可以除盡，為什么？從客觀的角度想，sum!一定是大于后面的，并且一定含有后面的因子，但是這樣想未免太過僵硬，不妨主主觀上想，要求的是方案數丫，方案數有不是整數的嗎？木有!所以，一定能除盡，
-
Pn = total / sum * cntn，這個公式，可以從多方面思考，total 是總排列數，除以總元素數量，乘以某個元素的個數有什么具體含義呢 ? total / sum 可以看作是任意一個元素在首位置時的排列數，乘以這個的數量，就是這個元素在首位的總排列數，
但是要注意，total / sum 不一定可以整除，但是 Pn = total * cetn / sum 一定可以整除（這個的答案也是方案數，從主觀上看，所得一定是個整數解），
所以第二個公式更應該這么寫：
- 這里，n是在不斷縮小的，對應的，total也是不斷變化的，cnt也是變化的，所以我們要動態處理，每一次，都要重新求一下對應的值，
- OK，
沒看懂也沒關系，代碼如下
#include<bits/stdc++.h>
#define fi first
#define endl "\n"
#define se second
#define PI acos(-1)
#define int long long
#define inf 0x3f3f3f3f
#define mm(a, b) memset(a, b, sizeof(a))
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define debug freopen("1.in", "r", stdin), freopen("1.out", "w", stdout);
using namespace std;
typedef long long ll;
typedef pair<int , int> PII;
const int P = 1000000007;
const int N = 100010;
int a[N];
int ck[N];
bool vis[15];
void init()
{
ck[0] = 0;ck[1] = 1;
for(int i = 2;i <= 12;i ++)ck[i] = ck[i - 1] * i;
}
signed main()
{
ios//關流，加快輸入速度，
init();//預處理所有階乘，
int t;cin >> t;
while(t --)
{
int n;cin >> n;
int sum = ck[n];//這里的sum 和 上文提到的 total 一樣，
int cnt[15];//記錄每個數字出現的次數，
mm(cnt , 0);//初始化次數
mm(vis , false);//初始化數字出現狀態，
for(int i = 0;i < n;i ++)//讀入每一個數字，并且記錄出現次數，
{
cin >> a[i];
cnt[a[i]]++;
}
int nn = n;//備份一下n, n表示當前排列的長度，nn表示總共有多少個數
int res = 0;//初始化答案，
for(int i = 0;i < nn;i ++)
{
mm(vis , false);
//計算total，如果一個數已經算過了，就沒必要除兩次，vis陣列用于記錄狀態，
for(int k = i;k < nn;k ++)
{
if(!vis[a[k]])
{
sum = sum / ck[cnt[a[k]]];
vis[a[k]] = true;
}
}
mm(vis , false);
//如果后面的數小于當前第一位的數，后面這個數的放在首位的全排列全部都是字典序小于當前排列的答案，每個都要加，
for(int j = i + 1;j < nn;j ++)
{
if(a[j] < a[i] && !vis[a[j]])
{
//滿足條件，就計算答案，
res = res + sum *cnt[a[j]] / n;
vis[a[j]] = true;
}
}
//去下一個排列前的初始化
n --;//排列長度減少1.
sum = ck[n];//sum 要重新計算
cnt[a[i]] --;//當前這個數已經木得價值，就cnt減去1，
}
//排序是從0開始，所以答案+1.
cout << res + 1 << endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/262117.html
標籤：其他