8.9日总结

C题：（三元环计数）
题意，给定一个图，求四元环的个数，这个四元环要求是由两个三元环相邻一条共同边组成的

解法：
①统计每个点的度数
②入度<=sqrt(m)的分为第一类，入度>sqrt(m)的分为第二类
③对于第一类，暴力每个点，然后暴力这个点的任意两条边，再判断这两条边的另一个端点是否连接
因为m条边最多每条边遍历一次，然后暴力的点的入度<=sqrt(m)，所以复杂度约为O(msqrt(m))
④对于第二类，直接暴力任意三个点，判断这三个点是否构成环，因为这一类点的个数不会超过sqrt(m)个，所以复杂度约为O(sqrt(m)3)=O(msqrt(m))
⑤判断两个点是否连接可以用set，map和Hash都行,根据具体情况而行
这种做法建的是双向边，常数很大

 1 //https://www.cnblogs.com/jiachinzhao/p/7474761.html
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<set>
 5 #include<cmath>
 6 #include<vector>
 7 using namespace std;
 8 typedef long long ll;
 9 const int maxn = 1e5 + 10;
10 set<ll>s;
11 int deg[maxn];
12 vector<int>g[maxn];
13 int vis[maxn], vi[maxn];
14 
15 int main() {
16     int n, m, u, v, sz;
17     while (scanf("%d%d", &n, &m) != EOF) {
18         sz = sqrt(m + 0.5);
19         s.clear();
20         for (int i = 1; i <= n; i++) {
21             vis[i] = vi[i] = deg[i] = 0;
22             g[i].clear();
23         }
24         for (int i = 0; i < m; i++) {
25             scanf("%d%d", &u, &v);
26             s.insert(u + 1ll * v*n);
27             s.insert(v + 1ll * u*n);
28             deg[u]++, deg[v]++;
29             g[u].push_back(v); g[v].push_back(u);
30         }
31         ll ans = 0;
32         for (int u = 1; u <= n; u++) {
33             vis[u] = 1;
34             for (auto v : g[u])vi[v] = u;
35             for (auto v : g[u]) {
36                 int cnt = 0;
37                 if (vis[v])continue;
38                 if (deg[v] <= sz) {
39                     for (auto vv : g[v])
40                         if (vi[vv] == u)cnt++;
41                 }
42                 else {
43                     for (auto vv : g[u]) {
44                         if (s.find(1ll * v*n + vv) != s.end())cnt++;
45                     }
46                 }
47                 ans += 1ll * cnt*(cnt - 1) / 2;
48             }
49         }
50         printf("%lld
", ans);
51     }
52     return 0;
53 }

D（矩阵快速幂）
题意：有一个4*n的矩阵，要求只能只能用2x1的木板覆盖，问一共有多少种覆盖的方法

解法：
当前一列已经铺满的时候，那么下一列一共有五种铺法，根据这五种铺发推出递推关系式，之后矩阵快速幂跑一下即可
博客链接

 1 //https://blog.csdn.net/elbadaernu/article/details/77825979
 2 
 3 #include <iostream> 
 4 #include <cstring>
 5 #include <cstdio>
 6 using namespace std;
 7 #define LL long long 
 8 const int mod = 1000000007;
 9 struct matrix
10 {
11     LL x[4][4];
12 };
13 matrix mutimatrix(matrix a, matrix b)
14 {
15     matrix temp;
16     memset(temp.x, 0, sizeof(temp.x));
17     for (int i = 0; i < 4; i++)
18         for (int j = 0; j < 4; j++)
19             for (int k = 0; k < 4; k++)
20             {
21                 temp.x[i][j] += a.x[i][k] * b.x[k][j];
22                 temp.x[i][j] %= mod;
23             }
24     return temp;
25 }
26 
27 matrix k_powmatrix(matrix a, LL n)//矩阵快速幂
28 {
29     matrix temp;
30     memset(temp.x, 0, sizeof(temp.x));
31     for (int i = 0; i < 4; i++)
32         temp.x[i][i] = 1;
33 
34     while (n)
35     {
36         if (n & 1)
37             temp = mutimatrix(temp, a);
38 
39         a = mutimatrix(a, a);
40         n >>= 1;
41     }
42     return temp;
43 }
44 
45 
46 int main(){
47     LL n;
48     while (scanf("%lld", &n) != EOF){
49         //前面四个手算下
50         if (n == 1){printf("1
");continue;}
51         if (n == 2){printf("5
");continue;}
52         if (n == 3){printf("11
");continue;}
53         if (n == 4){printf("36
");continue;}
54 
55         matrix st;
56         memset(st.x, 0, sizeof(st.x));
57         st.x[0][0] = 1;
58         st.x[1][0] = 5;
59         st.x[2][0] = 1;
60         st.x[3][0] = -1;
61 
62         st.x[0][1] = 1;
63         st.x[1][2] = 1;
64         st.x[2][3] = 1;
65 
66         matrix init;//初始矩阵
67         memset(init.x, 0, sizeof(init.x));
68 
69         init.x[0][0] = 36;
70         init.x[0][1] = 11;
71         init.x[0][2] = 5;
72         init.x[0][3] = 1;
73 
74         st = k_powmatrix(st, n - 4);//经过n-4次相乘
75         st = mutimatrix(init, st);//然后再乘上初始矩阵
76 
77         printf("%lld
", (st.x[0][0] + mod) % mod);
78     }
79     return 0;
80 }

E：
题意：
有一列数，每次询问随机的删掉一个数，求最后所有数且、或、异或的结果

解法：
按位处理，每一位统计一的个数，之后按一的个数为0，为1，为n，以及其他情况分类讨论即可

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 const int maxn = 1e6 + 5;
 5 
 6 int n, m;
 7 int a[maxn];
 8 int b[maxn];
 9 
10 int main() {
11     while (~scanf("%d %d", &n, &m)) {
12         memset(a, 0, sizeof(a)); 
13         memset(b, 0, sizeof(b));
14 
15         int AND = 0, OR = 0, XOR = 0;
16         for (int i = 1; i <= n; i++) {
17             scanf("%d", &a[i]);
18             int t = a[i], k = 0;
19             XOR ^= a[i];
20             while (t) { b[k++] += t % 2; t /= 2; }
21         }
22 
23         while (m--){
24             int x; scanf("%d", &x);
25             x = a[x];
26             int NXOR = XOR^x;
27             AND = 0, OR = 0;
28             for (int j = 0; j < 32; j++) {
29                 if (b[j] == 0)continue;
30                 else if (b[j] == 1) {
31                     if (x&(1 << j))continue;
32                     OR += (1 << j);
33                     if (n == 2)AND += (1 << j);
34                 }
35                 else if (b[j] == n) {
36                     AND += (1 << j); OR += (1 << j);
37                 }
38                 else {
39                     OR += (1 << j);
40                     if (b[j] == n - 1 && !(x&(1 << j)))
41                         AND += (1 << j);
42                 }
43             }
44             printf("%d %d %d
", AND, OR, NXOR);
45         }
46     }
47     return 0;
48 }

H：（打表+数论）
题意：
给定一个数n和a，问在 [1,1 << n] 的范围内有多少个b满足 a^b=b^a(mod 1 << n)

解法：
关键是思路！

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<string>
 6 #include<cmath>
 7 #include<stack>
 8 #include<vector>
 9 #include<queue>
10 #include<algorithm>
11 using namespace std;
12 const int MAXM=100010;
13 const long long MOD=1000000007;
14 const double PI=acos(-1);
15 
16 long long n,a;
17 
18 long long qpow(long long x,long long y,long long mod)
19 {
20     long long res=1;
21     while(y)
22     {
23         if (y&1) res=(res*x)%mod;
24         x=(x*x)%mod;
25         y=y>>1;
26     }
27     return res;
28 }
29 long long qpow(long long x,long long y)
30 {
31     long long res=1;
32     while(y)
33     {
34         if (y&1) res=res*x;
35         x=x*x;
36         y=y>>1;
37     }
38     return res;
39 }
40 int main()
41 {
42     while(scanf("%lld%lld",&n,&a)!=EOF)
43     {
44         if (a&1)
45         {
46             printf("1
");
47             continue;
48         }
49         else
50         {
51             long long m=1<<n;
52             long long ans=0;
53             for (long long i=1;i<=n;i++)
54                 if (qpow(a,i,m)==qpow(i,a,m))
55                 ans++;
56             long long b2=n/a;
57             if (b2*a<n) b2=b2+1;
58             long long b3=qpow(2,b2);
59             //int b4=qpow(2,a);
60             long long res=m/b3-n/b3;
61             ans=ans+res;
62             printf("%lld
",ans);
63         }
64     }
65     return 0;
66 }
67