寒假集训【1.24-1.25】
? 分享交流： ? （待书写） ? 附：可以贴各种资料或题解 1.24 0x01?位运算 快速幂取模： 要点： 1.通过对每个底数取模，降低底数规模。 ? 1 int sum=1;
2 a=a%mod; 3 for(int i=1;i<=b;i++) 4 sum*=a; 5 sum%=mod;
? 2.把指数转化为2进制，再通过手段缩小指数的规模，用1的方法进行取模。若指数为偶数，两两合并。如7^16%mod=(7%mod)^16=(49%mod)^4=(49%mod)*(49%mod)^2··· ? 1 #include <iostream>
2 using namespace std;
3 long long ksm(long long di,long long zhi,long long mod){ 4 if(zhi==0)return 1%mod; 5 long long ans=1; 6 while(zhi){ 7 if(zhi&1) 8 ans=ans*di%mod; 9 di=di*di%mod; 10 zhi>>=1; 11 } 12 return ans; 13 }
? 64位乘法：
? 1 long long gcqm(long long a,long long b,long long mod){//类似快速幂思想，把b转化为二进制
2 long long ans=0;
3 while(b){ 4 if(b&1) 5 ans=(ans+a)%mod; 6 a=a*2%mod; 7 b>>=1; 8 } 9 return ans; 10 }
2.a*b % mod=a*b-[a*b/mod]*p ?[]表示向下取整 ? 1 long long gcqm2(long long a,long long mod){//a*b % mod=a*b-[a*b/mod]*p []表示向下取整
2 a%=mod;
3 b%=mod; 4 long long c=(long double)a*b/mod; 5 long long ans=a*b-c*mod; 6 if(ans<0)ans+=mod; 7 else if (ans>=mod)ans-=mod; 8 return ans; 9 }
? 1.25 二进制状态压缩 ?
Hamilton路径 这道DP的思路是floyd，用二进制进行状态压缩。用一个n位的二进制数表示状态，若第i为为1，则表示第i个点已经被经过。因此我们定义一个数组f[i,j]表示”点被经过的状态”对应的二进制位为i，且目前处于点j时的最短路径。 此时DP方程为f[i][j=min(f[i][j],f[i^1<<j][k]+weight[j][k]),因为当前时刻被经过的点的二进制数为i，处于点j。故最终目标为f[(1<<n)-1][n-1]。因为j点恰好经过一次，所以一定是刚刚经过的，所以在上一时刻被经过的点对应的二进制状态i的第j位赋值一定为0。也就是i^(1<<j)。且上一个经过的点可能是i^(1<<j)中任意一个是1的数位k，所以可以考虑这样的状态是最小值。 ? 1 f[1][0]=0;
2 for(int i=1;i<1<<n;i++) 3 for(int j=0;j<n;j++) 4 if(i>>j&1) 5 for(int k=0;k<n;k++) 6 if((i^1<<j)>>k&1) 7 f[i][j]=min(f[i][j],f[i^1<<j][k]+weight[k][j]); 8 cout<<f[(1<<n)-1][n-1]<<endl;
? 逻辑运算的运算顺序 ?
成对变换 对于非负整数n 当n为偶数时，n xor 1=n+1 当n为奇数时，n xor 1=n-1 所以0与1,2与3，4与5?关于xor 1?的计算成为成对变换。 Lowbit运算 对于非负整数n在二进制表示下“最低位的1以及后面所以的0构成的数值”。 Lowbit（n）=n&(~n+1)=n&(-n) GCC编译器内置函数 Int_builtin_ctz(unsigned int x) Int_builtin_ctzll(unsigned long long x) 返回x的二进制表示下最低位的1后边有多少个0 Int_builtin_popcount(unsigned int x) Int_builtin_popcountll(unsigned long long x) Map ?
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
