• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

回归刷题记录

互联网 diligentman 4天前 10次浏览

看到之前发过的博客还是费用流和点双边双问题,感慨良多呀。

10.15中午

洛谷P1226 【模板】快速幂

快速幂代码:

int power (int a, int b, int p) {
   
   
 int ans = 1 % p;
 for (; b; b >>= 1) {
   
   
  if (b & 1) ans = (long long)ans * a % p;
  a = (long long)a * a % p;
 }
 return ans;
}

这里引用一下高中时代膜拜的大佬之一syq大佬的“一行快速幂”

typedef long long ll;
ll fast(ll a,ll b){
   
   ll ans=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ans=mul(ans,a);return ans;}

CH0102 快速乘

快速乘有两种写法,第一种是借鉴快速幂,利用二进制进行运算;第二种是利用 a × b     m o d   p = a × b − ⌊ a × b / p ⌋ × p atimes b bmod p =atimes b – lfloor atimes b /prfloor times p a×b modp=a×ba×b/p×p
代码如下:

long long mul (long long a, long long b, long long p) {
   
   
 a %= p; b %= p;
 long long c = (long double)a * b / p;
 long long ans = a * b - c * p;
 if (ans < 0) ans += p; else if (ans >= p) ans -= p;
 return ans;
}

syq大佬的一行快速乘

ll mul(ll x,ll y){
   
   return ((x*y-(ll)(((long double)x*y+0.5)/mod)*mod)%mod+mod)%mod;}

最短哈密顿路径

状态压缩DP题

memset (d, 0x3f, sizeof (d));
 d[1][0] = 0;
 for (int i = 1;i < 1 << n;i ++)
  for (int j = 0;j < n;j ++)
   if (i >> j & 1)
    for (int k = 0;k < n;k ++)
     if ((i ^ 1 << j) >> k & 1)
      d[i][j] = min (d[i][j], d[i ^ 1 << j][k] + a[k][j]);
 printf ("%d", d[(1 << n) - 1][n - 1]);

现在位运算真的不熟练。

POJ1995 Raising Modulo Numbers

也是快速幂的半裸题


喜欢 (0)