把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。
题目大意：
CF 1557C Moamen and XOR
题目大意：给你一个n和k（范围均为2e5），表示一个数组中有n个大小范围为2^k-1的数，问有多少个这样的数组，使得数组的与值大于其异或值，取模1e9+7。
解：
注意到，一个数位的与值只有当其全为1是才为1，而异或值则是有偶数个1时为0，奇数个时为1，所以我们可以把题目的n按奇偶性划分情况：
①n为奇数，这个时候数位全为1时AND和XOR都为1，而有偶数个1时AND和XOR都为0，其余情况都是AND为0，XOR为1。
②n为偶数，这个时候数位全为1时AND为1，XOR为0，也是唯一一种AND可以大于XOR的情况，有偶数个1且并不全是1的时候AND和XOR都为0，其余情况AND为0，XOR为1。
使用dp[i]来记录从右边起第i为合格的方案数，可以发现，如果n个数全是0的时候是符合条件的，所以首先预设dp[0]=1。
接下来就分奇偶讨论了：
n奇数的时候，这时无论如何数位上的AND值都不会超过XOR值，所以只能保证在AND和XOR值相等的情况下继续归于下一位，情况数量是C(n,2)+C(n,4)+…+C(n,n-1)，这个和等于2^(n-1)（自己推），加上全1和全0的情况，也就是2^(n-1)+1。
而n为偶数的时候，全1时AND是可以大于XOR的，这样的话比这位小的数位就随便分配了，而除了全1以外处理是和奇数一样的，递推的乘数变为2^(n-1)-1，多了一个加数为2^(k*n)，k表示比他小的位数数量。
虽然很简单，不过是div2的C题，一定要尽快出才行，还是比较吃位运算的熟练度的，细节上也有一些讲究。
代码
代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#define ll long long
#define maxn 200005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define inc(i,a,n) for(ll i=a;i<n;i++)
#define vset(a,n,m) for(ll i=0;i<n;i++)a[i]=m;
using namespace std;
ll cpow(ll x, ll n) {
ll ans = 1;
while (n > 0) {
if (n & 1) ans = (ans * x) % mdl;
x = (x * x) % mdl;
n >>= 1;
}
return ans;
}
ll dp[maxn];
int main() {
cfast;
int t;
cin >> t;
while (t--) {
ll n, k;
cin >> n >> k;
ll ans = 0;
ll ev = 0;
if (n % 2 == 0)ev++;
dp[0] = 1;
inc(i, 1, k + 1) {
ll bkw = i - 1;
dp[i] = ev * cpow(cpow(2, bkw), n) % mdl +(cpow(2, n - 1) +1- 2*ev) * dp[i-1] % mdl;
dp[i] %= mdl;
}
cout << dp[k] << endl;
}
}
|
Copyright Notice: 此文章版权归EmiteInna所有，多看看吧。
