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

题意

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

排序规则是:

取两个 5,则组合为:55;取 2 与 1,则组合为:21。

思路

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

0 1 2 3 4 10 11 12 13 14
1 2 3 5 9 11 12 13 15 19

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

如果你还不明白,我们从头开始推:

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]={'1','2','3','5','9'};
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;
}