莫的难题

我觉得这是本场比赛最好的题目

题意

题目其实有点没说清楚，其实就是给定,，要求第大的数。

排序规则是：

取两个 5，则组合为：55；取 2 与 1，则组合为：21。

思路

一句话概括：五进制，但是起点是1，而不是0。

看到了吗？五进制下对应的是。

如果你还不明白，我们从头开始推：

1 2 3 5 9
11 12 13 15 19
21 22 23 25 29
31 32 33 35 39
51 52 53 55 59
91 92 93 95 99
111

你会发现数据规律是： 个一位数，个两位数，个三位数，个四位数。

明白了吗，本题就是转化成五进制数，然后再把字符串转化回1，2，3，5，9和0，1，2，3，4对应的字符串。

而坑点就在于：五进制，但是起点是1，而不是0。

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
using namespace std;
typedef long long ll;
ll mod=1e9+7;
ll qkpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
ll getInv(ll a) { return qkpow(a, mod - 2); }  //求一个数的逆元
ll C(ll n, ll m) {                             //组合数 C(n,m)
    if (m < 0) return 0;
    if (n < m) return 0;
    if (m > n - m) m = n - m;
    ll up = 1, down = 1;
    for (ll i = 0; i < m; i++) {
        up = up * (n - i) % mod;
        down = down * (i + 1) % mod;
    }
    return up * getInv(down) % mod;
}
char mp[5]={&#39;1&#39;,&#39;2&#39;,&#39;3&#39;,&#39;5&#39;,&#39;9&#39;};
int main() {
    ll t;sc(t);
    while (t--) {
        ll n, m; sc(n), sc(m);
        ll a = C(n, m);
        string ans="";
        while(a>0){
            --a;//精髓
            ans+=mp[a%5];
            a/=5;
        }
        reverse(ans.begin(),ans.end());
        cout<<ans<<endl;
    }
    return 0;
}