4.16

HDU 5667 

强行费马小定理+矩乘+快速幂。

trick是费马小定理前提(a,p)=1，需要特判a mod p = 0的情况。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5 typedef long long LL; 6 const int maxn = 4; 7 LL mod; 8  9 struct Matrix10 {11     LL m[maxn][maxn];12     Matrix(){memset(m, 0, sizeof(m));}13     void E(){
    for(int i = 0; i < maxn; i++) m[i][i] = 1;}14 };15 16 Matrix M_mul(Matrix a, Matrix b)17 {18     Matrix ret;19     for(int i = 0; i < maxn; i++)20         for(int j = 0; j < maxn; j++)21             for(int k = 0; k < maxn; k++)22                 ret.m[i][j] = ( ret.m[i][j] + (a.m[i][k] * b.m[k][j]) % mod ) % mod;23     return ret;24 }25 26 Matrix M_qpow(Matrix P, LL n)27 {28     Matrix ret;29     ret.E();30     while(n)31     {32         if(n & 1LL) ret = M_mul(ret, P);33         n >>= 1LL;34         P = M_mul(P, P);35     }36     return ret;37 }38 39 LL qpow(LL a, LL b)40 {41     LL ret = 1LL;42     while(b)43     {44         if(b & 1LL) ret = ret * a % mod;45         a = a * a % mod;46         b >>= 1LL;47     }48     return ret;49 }50 51 int main(void)52 {53     int T;54     scanf("%d", &T);55     while(T--)56     {57         LL n, a, b, c, p;58         cin >> n >> a >> b >> c >> p;59         if(a % p == 0) puts("0");60         else61         {62             Matrix A, B;63             A.m[1][1] = A.m[2][3] = A.m[3][1] = A.m[3][2] = 1LL;64             A.m[3][3] = c;65             mod = p - 1LL;66             B = M_qpow(A, n - 1LL);67             LL e = b * (B.m[2][1] + B.m[2][3]) % mod;68             mod = p;69             LL ans = qpow(a, e);70             cout << ans << endl;71         }72     }73     return 0;74 }
        
       
      

 

4.20

HDU 5668 

一般模线性方程组模板。

现已加入肯德基豪华午餐。

1 #include 
      
        2 #include 
       
         3 using namespace std; 4 typedef long long LL; 5  6 LL exgcd(LL a, LL b, LL & x, LL & y) 7 { 8     if(!b) {x = 1LL; y = 0LL; return a;} 9     int r = exgcd(b, a % b, x, y);10     int t = x; x = y; y = t - a / b * y;11     return r;12 }13 14 LL solve(LL b[], LL n[], int num)15 {16     LL n1 = n[1], b1 = b[1], x, y;17     for(int i = 2; i <= num; i++)18     {19         LL n2 = n[i], b2 = b[i], bb = b2 - b1;20         LL d = exgcd(n1, n2, x, y);21         if(bb % d) return -1LL; // non-solution22         LL k = bb / d * x, t = n2 / d;23         if (t < 0) t = -t;24         k = (k % t + t) % t;25         b1 = b1 + n1 * k;26         n1 = n1 / d * n2;27     }28     if(!b1) b1 = n1; // positive!29     return b1; // solution : b1 + Z * n130 }31 32 int main(void)33 {34     int T, id[22], used[22];35     LL B[22], N[22];36     scanf("%d", &T);37     while(T--)38     {39         int n, x, pos = 0;40         scanf("%d", &n);41         for(int i = 1; i <= n; i++) used[i] = 0;42         for(int i = 1; i <= n; i++)43         {44             int x;45             scanf("%d", &x);46             id[x] = i;47         }48         for(int i = 1; i <= n; i++)49         {50             int cnt = 0;51             while(pos != id[i])52             {53                 if(!used[pos]) cnt++;54                 pos = pos % n + 1;55             }56             used[id[i]] = 1;57             B[i] = cnt + 1, N[i] = n - i + 1;58         }59         LL ans = solve(B, N, n);60         if(ans == -1) puts("Creation August is a SB!");61         else printf("%I64d\n", ans);62     }63     return 0;64 }
       
      

 

4.24

ZOJ 3946 

？？？？

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 using namespace std; 7 typedef long long LL; 8 const int maxn = 2e5 + 10; 9 const LL INF = 1e12;10 typedef pair
           
             pll;11 typedef pair
            
              plli;12 LL dist[maxn], cost[maxn];13 int cnt, h[maxn];14 15 struct edge16 {17 int to, pre;18 LL D, C;19 } e[maxn<<1];20 21 void init()22 {23 cnt = 0;24 memset(h, 0, sizeof(h));25 }26 27 void add(int from, int to, LL d, LL c)28 {29 cnt++;30 e[cnt].pre = h[from];31 e[cnt].to = to;32 e[cnt].D = d;33 e[cnt].C = c;34 h[from] = cnt;35 }36 37 void dijkstra(int s)38 {39 priority_queue
             
              , greater
              
                > pq;40 fill(dist, dist + maxn, INF);41 fill(cost, cost + maxn, INF);42 dist[s] = cost[s] = 0LL;43 pq.push(plli(pll(0LL, 0LL), s));44 while(!pq.empty())45 {46 plli tmp = pq.top(); pq.pop();47 int v = tmp.second;48 for(int i = h[v]; i; i = e[i].pre)49 {50 int to = e[i].to;51 LL d = e[i].D, c = e[i].C;52 if(dist[to] > dist[v] + d)53 {54 dist[to] = dist[v] + d;55 cost[to] = c;56 pq.push(plli(pll(dist[to], cost[to]), to));57 }58 else if(dist[to] == dist[v] + d && cost[to] > c)59 {60 cost[to] = c;61 pq.push(plli(pll(dist[to], cost[to]), to));62 }63 }64 }65 }66 67 int main(void)68 {69 int T;70 scanf("%d", &T);71 while(T--)72 {73 init();74 int N, M;75 scanf("%d %d", &N, &M);76 for(int i = 0; i < M; i++)77 {78 int X, Y;79 LL D, C;80 scanf("%d %d %lld %lld", &X, &Y, &D, &C);81 add(X, Y, D, C);82 add(Y, X, D, C);83 }84 dijkstra(0);85 LL a1 = 0LL, a2 = 0LL;86 for(int i = 1; i < N; i++) a1 += dist[i], a2 += cost[i];87 printf("%lld %lld\n", a1, a2);88 }89 return 0;90 }
              
             
            
           
          
         
        
       
      

 

4.27

ZOJ 3940 

暴力大法好。不是很懂复杂度。

1 #include 
      
        2 #include 
       
         3 #include