微信用网站怎么做,phpcms 适合什么的网站,外贸推广平台,南京网站运营公司cf1557 C. Moamen and XOR
题意#xff1a;
一个n位数#xff0c;每一位小于2k2^k2k,如果a1a2…ana1⊕a2…⊕an,则获胜 现在给你n和k#xff0c;问能构造多少个序列是获胜的
题解#xff1a;
奇偶分类二进制考虑 我们现在认为每个数的第k位都是1
如果n为…cf1557 C. Moamen and XOR
题意
一个n位数每一位小于2k2^k2k,如果a1a2…ana1⊕a2…⊕an,则获胜 现在给你n和k问能构造多少个序列是获胜的
题解
奇偶分类二进制考虑 我们现在认为每个数的第k位都是1
如果n为奇数的结果为1⊕的结果也为1此时第k位没有区别我们去看第k-1位如果n为偶数的结果为1⊕的结果为0此时式子一定成立剩下k-1位01随便填(因为第k位已经确定大小)方案就是(2k−1)n({2^{k-1}})^{n}(2k−1)n,
现在我们认为每个数的第k位不完全是1
如果n是奇数此时结果是0要让大于等于⊕我们就要让⊕等于0说明就有偶数个1所以每次选取n中x个数使其为0剩下为1(x为奇数)。sumCn1Cn3..CnnC_{n}^{1}C_{n}^{3}..C_{n}^{n}Cn1Cn3..Cnn如果n为偶数同理sumCn2Cn4..CnnC_{n}^{2}C_{n}^{4}..C_{n}^{n}Cn2Cn4..Cnn
注意x是从1开始的因为x等于0就是全为1的情况就是我们一开始讨论的 此时答案sum*次高位的答案贡献
dp[i]表示第i位(二进制)的方案数 答案是dp[k] 如果i是奇数dp[i]dp[i−1]∗(sum1)dp[i]dp[i-1]*(sum1)dp[i]dp[i−1]∗(sum1) .其中1为第i位全1时的方案, sum为第i位不全为1时的方案. 如果i是偶数dp[i]dp[i−1]∗sum(2i−1)ndp[i]dp[i-1]*sum({2^{i-1}})^{n}dp[i]dp[i−1]∗sum(2i−1)n,其中 (2i−1)n({2^{i-1}})^{n}(2i−1)n为第i位全1时的方案, sum为第i位不全为1时的方案. 这种问题就要看作二进制每一位每一位的考虑对于存在异或的要注意奇偶性
代码
// Problem: C. Moamen and XOR
// Contest: Codeforces - Codeforces Round #737 (Div. 2)
// URL: https://codeforces.com/contest/1557/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Data:2021-08-23 14:30:40
// By Jozky#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef LOCALstartTime clock();freopen(in.txt, r, stdin);
#endif
}
void Time_test()
{
#ifdef LOCALendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn 2e5 9;
const int mod 1e9 7;
ll fac[maxn];
ll infac[maxn];
ll poww(int a, int b)
{ll ans 1;while (b) {if (b 1)ans ans * 1ll * a % mod;a 1ll * a * a % mod;b 1;}return ans;
}
int C(int a, int b)
{return 1ll * fac[a] % mod * infac[a - b] % mod * infac[b] % mod;
}
ll dp[maxn];
void solve()
{int n, m;read(n, m);int res 0;dp[0] 1;if (n % 2) { //n为奇数int sum 0;for (int i 1; i n; i 2) {sum (sum C(n, i)) % mod;}for (int i 1; i m; i) {dp[i] 1ll * dp[i - 1] * (1 sum) % mod;}}else if (n % 2 0) { //n为偶数int sum 0;for (int i 2; i n; i 2) {sum (sum C(n, i)) % mod;}for (int i 1; i m; i) {dp[i] 1ll * dp[i - 1] * sum % mod;dp[i] (dp[i] poww(poww(2, i - 1), n)) % mod;}}printf(%d\n, dp[m]);
}
int main()
{//rd_test();fac[0] infac[0] 1;for (int i 1; i maxn; i) {fac[i] 1ll * fac[i - 1] * i % mod;infac[i] 1ll * infac[i - 1] * poww(i, mod - 2) % mod;}int t;read(t);while (t--) {solve();}return 0;//Time_test();
}
