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: 记忆化搜索
和异或有关拆成二进制，遇异或就拆位。
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 }