Codeforces1514B

问题描述

给你两个数n,k，问可以构造多少n个最大位数为k数按位与为0并且这n个数加起来最大的合法序列，答案对1e9 + 7取模。

思路分析

首先我们考虑这n个数按位与以后为0这个条件：我们可以知道，如果按位与为0的话，就代表着这n个数在每一位至少有一个数在这一位为0。
其次考虑和最大，那么我们就可以这样想，既然每一位都会至少有一个数在这一位上为0，那么肯定是刚好一一对应最好，不然这些数加起来不会是最大。
因此，我们对于每一位，都可以找到n个数来取0，所以答案就是n^k。

代码如下

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const ll mod = 1000000007;

ll qpow(ll a, ll b, ll p)

{

        ll ans = 1;

        while (b)

        {

                if (b & 1)

                        ans = ans * a % mod;

                a = a * a % mod;

                 b >>= 1;

        }

        return ans % mod;

}

signed main()

{

        ios::sync_with_stdio(0);

        cin.tie(0);

        cout.tie(0);

        int t;

        cin >> t;

        while (t--)

        {

                ll n, k;

                cin >> n >> k;

                ll ans = qpow(n, k, mod) % mod;

                cout << ans << endl;

        }

        return 0;

}

巴特西

Codeforces1514B

代码如下

最新文章

热门文章