链接；https://nanti.jisuanke.com/t/31453
题意：n个人，2^k个数，从0 ~ 2^k -1编号。n个人坐成圈，每个人一个数，相邻的两人的数同或大于0。问一共有多少种分配方式。
思路：注意分类要分3类，一类值与第一个人相同，一类与第一个人同或为0，一类表示剩下的其他情况。
不明白怎么分类递推可以看看这个：https://www.cnblogs.com/the-way-of-cas/p/9636714.html
代码：
#include <iostream> #include <algorithm> #define MOD 1000000007 #define maxn 1000009 #define ll long long using namespace std; int k, n; ll same_one[maxn], xnoris0[maxn], oth[maxn]; ll biao[maxn + 100]; void setbiao() { biao[0] = 1; for (int i = 1; i <= maxn ; i++) { biao[i] = (biao[i - 1] << 1); if (biao[i] > MOD) biao[i] -= MOD; } } int main() { setbiao(); int t; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &k); ll t2 = (biao[k] - 2 + MOD) % MOD; ll t3 = (biao[k] - 3 + MOD) % MOD; ll ans; if (k == 1) { ans = 2; } else { oth[1] = biao[k]; oth[2] = (oth[1] * t2) % MOD; same_one[2] = oth[1]; for (int i = 3; i <= n; i++) { oth[i] = (same_one[i - 1] * t2) % MOD + (xnoris0[i - 1] * t2) % MOD + (oth[i - 1] * t3) % MOD; same_one[i] = (same_one[i - 1] + oth[i - 1]) % MOD; xnoris0[i] = (oth[i - 1] + xnoris0[i - 1]) % MOD; } ans = (oth[n] + same_one[n]) % MOD; } printf("%lld\n", ans); } return 0; }
原文：https://www.cnblogs.com/the-way-of-cas/p/9643250.html