A - 越狱

题目链接

题目分析：
如果正面去想越狱的方案可能有点不好想，何必不转换个思路：

用所有状态数减去不会越狱的状态数不就是越狱的状态数吗

所有状态数：m^n，因为每个房间的犯人可以信仰m种宗教，根据乘法原理可得不会越狱的状态数：

m *（m-1）^（n-1），对于第一个房间，可以选m种，对于第二个房间，为了不越狱，那么则只能放m-1种，依次类推，再根据乘法原理可得在相减的时候有可能为负数，那么加上mod再取模
本质还是一道水题，引入快速幂

代码

#include 
using namespace std;
const int mod = 100003;
typedef long long ll;
int solve1(ll a, ll b)
{
    ll ra = 1;
    while (b > 0)
    {
        if (b & 1)
            ra = (ra * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ra;
}
int main()
{
    ll n, m;
    cin >> m >> n;
    ll a = solve1(m, n);
    ll b = solve1(m - 1, n - 1);
    b = (b * m) % mod;
    cout << (a - b + mod) % mod;

    return 0;
}

 B - Special Numbers

题目链接

题目大意

T 组数据，给定 n , k(2≤n≤10^9,1≤k≤10^9）。定义一个正整数为 special 当且仅当其可以表示为若干个互不相同的 n 的非负整数次幂之和。

输出从小到大的第 k 个 special 数。

思路

我们拿 n=2n=2 举例，

序列为 2^0,2^1,2^1+2^0,2^2,2^2+2^0,2^2+2^1,2^2+2^1+2^0,2^3 . . . .

我们设二进制位的每一位 i 表示 n^i 这一位选不选。

将上述序列表示一下，

1,10,11,100,101,110,111,1000…

将这个二进制序列转化为十进制，1,2,3,4,5,6,7,8,…

我们发现，其实第 k 位其实就是其对应的二进制的对应的位选与不选。

比如 k=5 也就是 n^2+n^0

对于这种多个不同位的数相加的题，可以考虑由对应的二进制0 ，1 表示是与否

代码

#include 
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;

ll solve1(ll a, ll b)
{
    ll ra = 1;
    while (b > 0)
    {
        if (b & 1)
            ra = (ra * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ra;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        ll a, k, ans = 0;
        cin >> a >> k;
        ll m = 0;
        while (k > 0)
        {
            if (k & 1)
            {
                ans += solve1(a, m);
                ans %= mod;
            }
            k >>= 1;
            m++;
        }
        cout << ans << endl;
    }
    return 0;
}