问题描述
- 给你两个数n,k,问可以构造多少n个最大位数为k数按位与为0并且这n个数加起来最大的合法序列,答案对1e9 + 7取模。
思路分析
- 首先我们考虑这n个数按位与以后为0这个条件:我们可以知道,如果按位与为0的话,就代表着这n个数在每一位至少有一个数在这一位为0。
- 其次考虑和最大,那么我们就可以这样想,既然每一位都会至少有一个数在这一位上为0,那么肯定是刚好一一对应最好,不然这些数加起来不会是最大。
- 因此,我们对于每一位,都可以找到n个数来取0,所以答案就是n^k。
代码如下
#include
#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;
}
Original: https://www.cnblogs.com/csu-yuuki/p/15371211.html
Author: zhy-cx
Title: Codeforces1514B
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/713472/
转载文章受原作者版权保护。转载请注明原作者出处!