2023-04-16
T1 seq:
一.：首先注意，子集不是子区间，可不连续；序列权值与min和max有关。
先进行排序,就可以找到这样的规律：
2 |4
2 3 |4+3*(2*1+3*1) = 19
2 3 4 | 19+(2*2+3*1+4*1) = 63
2 3 4 5 |63+(2*4+3*2+4*1+5*1) = 178
()中的式子则代表a为最小值的时候有b种情况，由于子集是不连续的，所以最小值在排序后后面的每一个数都是可有可无的，因此后面的数每个都有两个方案，就有了1 2 4 8的规律。代码中的cnt即为（）中的内容。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #define ll long long
6 using namespace std;
7 const int Z = 1000050;
8 const int mod = 998244353;
9
10 int n;
11 ll a[Z],sum,ans,cnt;
12
13 int main(){
14 cin>>n;
15 for(int i=1;i<=n;i++){
16 cin>>a[i];
17 }
18 sort(a+1,a+1+n);
19 sum = a[1] * a[1];//对1 预处理
20 for(int i=2;i<=n;i++){
21 a[i] % mod;//防止乘的时候就炸了
22 cnt = (cnt * 2 + a[i-1]) % mod;
23 sum = (sum + a[i] * (a[i] + cnt) % mod) % mod;
24 }
25 cout<<sum;
26 return 0;
27 }
法二：整数中可能有负数，用 (x+mod)%mod 减少这方面的数据运算错误.
权值和min和max有关，确定min和max后就进行统计，我们考虑先固定一个min,情况数就为2 ^j-i-1,(j-i-1表示中间数个数)，就为a[i] *a[j] *a^j-i-1；优化一下就是有一个delta[1] = 2 * 1 + 3 * 2 * 1 + 4 * 4 * 1，delta[2] = 3 * 1 + 4 * 2 = (3 * 1 * 2+ 4 * 4 *1）/2^1；除一个数等于乘上这个数的逆元，用费马小定理求逆元。
T2 game： 分层图跑最短路dij
分层图：两个大同小异的图通过某几个点连在一起，构成层。
因为权值只有0 1 ，所以可以直接输出权值为1 的边
deque双端队列优化，w=1 push_back
w=0 push_front
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 #include<algorithm>
6 using namespace std;
7 const int Z = 2e6 + 5e6;
8 const int MAX = 1000050;
9
10 int n,m,k,ans;
11 struct edge{
12 int u,v,w,nxt;
13 }e[Z << 2];
14 bool vis[Z];
15 int dis[Z],head[Z],cnt = 1;
16 deque <int> q;
17
18 inline int read( ){
19 int x = 0 ; short w = 0 /*1*/; char ch = 0;
20 while( !isdigit(ch) ) { w|=ch=='-';ch=getchar();}
21 while( isdigit(ch) ) {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
22 return w ? -x : x;/*x & -x*/
23 }
24 void add(int u,int v,int w){
25 e[++cnt] = (edge){u,v,w,head[u]};
26 head[u] = cnt;
27 }
28
29 int main(){
30 memset(dis,0x3f,sizeof(dis));
31 n = read(),m =read(),k = read();
32 for(int i=1;i<=m;i++){
33 int u,v,w;
34 u = read(),v = read(),w = read();
35 if(w == 1){
36 add(u,v,1);
37 add(v,u,1);
38 }
39 else{
40 add(u + n, v + n,1);
41 add(v + n,u + n,1);
42 }
43 }
44 for(int i=1;i<=k;i++){
45 int x = read();
46 add(x,x + n,0);
47 add(x + n,x,0);
48 }
49 dis[1] = 0;
50 q.push_front(1);
51 while(!q.empty()){
52 int x = q.front();
53 q.pop_front();
54 if(vis[x]) continue;
55 vis[x] = 1;
56 if(dis[n] < MAX || dis[n << 1] < MAX) break;
57 for(int i=head[x];i;i = e[i].nxt){
58 int y = e[i].v;
59 if(dis[y] > dis[x] + e[i].w){
60 dis[y] = dis[x] + e[i].w;
61 if(!e[i].w) q.push_front(y);
62 else q.push_back(y);
63 }
64 }
65 }
66 dis[n] = min(dis[n],dis[n * 2]);
67 ans = (dis[n] < MAX ? dis[n] : -1);
68 cout<<ans;
69 return 0;
70 }
T3 count：
因为要满足ai | ai+1，所以考虑寻找找质因数，pi是质数，j是长度，f[i] [j] 表示最后一个数pi的方案数。第一种情况，后几个数重复出现，所以f[i] [j] =f[i] [j-1]，第二种情况，最后两个数不同，倒数第二个为p^i-1，f[i] [j] = f[i-1] [j]，初始化f[0] [j] = 1；a = p1^k1 * p2*k2,方案数为f[k1] [j] *f[k2] [j]
代码待写
T4 gift: 记忆化搜索
5000最多有13位，异或和为0 ，1为偶数个，第一个1不能要。
和异或有关拆成二进制，遇异或就拆位。
k表示1的个数，p表示当前位置，1可以随便放，n个数，i个一放在n个位置中组合数找答案，k每次统计1的个数，每次加一保证了和为m。每一位之间因为被拆成了二进制，是独立的，可以用记忆化记录已经搜的答案。
代码待写
dp：f[i] [j]表示1-i位上和为j的方案数
k代表区间内1的个数，第i位上就有c[k] [n] 个方案数；第j位上的和为2^i-1 * k,剩下的1~j-1位的和就为j - (2^i-1 * k)。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #define ll long long
6 using namespace std;
7 const int Z = 5050;
8 const int mod = 998244353;
9
10 ll n,m,f[20][Z],c[Z][Z];
11 bool vis[20][Z];
12
13 void C(){//组合数求法
14 for(int i=1;i<=n;i++){
15 for(int j=1;j<=n;j++){
16 c[i][j] = (c[i-1][j-1] + c[i][j-1])% mod;
17 }
18 }
19 }
20 ll dfs(int x,int sum){
21 if(vis[x][sum]){
22 return f[x][sum];
23 }
24 if(sum == 0){
25 return f[x][sum] = 1;
26 }
27 if(x == 0){
28 return f[x][sum] = 0;
29 }
30 for(int i=0;i<=n && sum - i * (1 << (x - 1)) >= 0;i+=2){
31 f[x][sum] = (f[x][sum] + c[i][n] * dfs(x-1,sum-i*(1<<(x-1)))% mod) %mod;
32 }
33 vis[x][sum] = 1;
34 return f[x][sum];
35 }
36 int main(){
37 cin>>n>>m;
38 for(int i=0;i<=n;i++){
39 c[0][i] = 1;
40 }
41 C();
42 cout<<dfs(14,m);//数据范围在5000，拆换成二进制后最多有13位
43 return 0;
44 }
标签：4.12,const,min,int,笔记,ch,听课,include,dis From： https://www.cnblogs.com/FHHH127/p/17324051.html