题解 | #猴子排序的期望#

#include <bits/stdc++.h>
using namespace std;
int arr[26]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
vector<int> mul(vector<int> &v,int b){
    int i,t=0;
    vector<int> sum;
    for(i=0;i<v.size()||t;i++){
        if(i<v.size()) t+=v[i]*b;
        sum.push_back(t%10);
        t/=10;
    }
    return sum;
}
vector<int> f(int n){
    vector<int> sum;
    sum.push_back(1);
    for(int i=1;i<=n;i++){
        sum=mul(sum,i);
    }
    return sum;
}
void print(vector<int> &sum){
    for(int i=sum.size()-1;i>=0;i--){
        printf("%d",sum[i]);
    }
    printf("\n");
}
vector<int> div(vector<int> v,int b){
    int r=0,i;
    vector<int> sum;
    for(i=v.size()-1;i>=0;i--){
        r=r*10+v[i];
        sum.push_back(r/b);
        r%=b;
    }
    reverse(sum.begin(),sum.end());
    while(sum.size()>=1&&sum.back()==0) sum.pop_back();
    return sum;
}
int main(){
    int n,i,j;
    scanf("%d",&n);
    string str;
    cin>>str;
    vector<int> sum=f(n);
    for(i=0;i<str.size();i++){
        arr[str[i]%65]++;
    }
    for(i=0;i<26;i++){
        if(arr[i]>1){
            j=arr[i];
            for(j;j>1;j--){
                sum=div(sum,j);
            }
        }
    }
    cout<<"1/";
    print(sum);
    return 0;
}