[1003 Sequence]
指数循环节，注意a mod p = 0的情况。此时你的循环节如果返回0，这时你会输出1，而实际上应该是0
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std; typedef long long ll;
ll n, a, b, c, p; struct Matrix{
ll a[3][3];
void clear(){memset(a, 0, sizeof a);}
void set(){clear(); a[0][0] = a[1][1] = a[2][2] = 1;}
}mat, ans; Matrix operator * (const Matrix& a, const Matrix& b){
Matrix c; c.clear();
for(int i = 0; i < 3; i ++)
for(int j = 0; j < 3; j ++)
for(int k = 0; k < 3; k ++)
(c.a[i][j] += a.a[i][k] * b.a[k][j]) %= (p-1);
return c;
} Matrix power(Matrix a, ll b){
Matrix ret; ret.set();
while(b > 0){
if(b & 1)ret = ret * a;
b >>= 1;
a = a * a;
}return ret;
} ll power_mod(ll a, ll b){
ll ret = 1;
while(b > 0){
if(b & 1)ret = ret * a % p;
b >>= 1;
a = a * a % p;
}return ret;
} int main(){
int test;
scanf("%d", &test);
while(test --){
cin >> n >> a >> b >> c >> p;
if(n == 1){
cout << 1 % p << endl;
continue;
}
if(a % p == 0){
cout << 0 << endl;
continue;
}
mat.clear();
mat.a[0][0] = c, mat.a[1][0] = 1, mat.a[2][0] = b;
mat.a[0][1] = 1;
mat.a[2][2] = 1;
ans.clear();
ans.a[0][0] = b, ans.a[0][1] = 0, ans.a[0][2] = 1;
ans = ans * power(mat, n - 2);
cout << power_mod(a, ans.a[0][0]) << endl;
}
return 0;
}
[1005 Road]
建立两棵线段树跑分层图(据说要Dijkstra+Heap？)。注意第二棵的叶子节点向第一棵的叶子节点连边。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#define maxn 800010
using namespace std;
int n, m, k;
struct Edge{
int to, next, dis;
}edge[maxn << 2];
int h[maxn], cnt, S, T, posT;
void add(int u, int v, int d){
cnt ++;
edge[cnt].to = v;
edge[cnt].next = h[u];
edge[cnt].dis = d;
h[u] = cnt;
} vector<int> v1, v2;
#define lc (id << 1)
#define rc (id << 1 | 1) void build(int id, int l, int r){
if(l == r){
if(l == 1)S = id;
posT = max(posT, id);
return;
}
int mid = l + r >> 1;
build(lc, l, mid);
build(rc, mid+1, r);
add(lc, id, 0);
add(rc, id, 0);
} void build2(int id, int l, int r){
if(l == r){
add(id + posT, id, 0);
if(l == n)T = id + posT;
return;
}
int mid = l + r >> 1;
build2(lc, l, mid);
build2(rc, mid+1, r);
add(id + posT, lc + posT, 0);
add(id + posT, rc + posT, 0);
} void ask1(int id, int l, int r, int L, int R){
if(l == L && r == R){
v1.push_back(id);
return;
}
int mid = l + r >> 1;
if(R <= mid)ask1(lc, l, mid, L, R);
else if(L > mid)ask1(rc, mid+1, r, L, R);
else ask1(lc, l, mid, L, mid), ask1(rc, mid+1, r, mid+1, R);
} void ask2(int id, int l, int r, int L, int R){
if(l == L && r == R){
v2.push_back(id);
return;
}
int mid = l + r >> 1;
if(R <= mid)ask2(lc, l, mid, L, R);
else if(L > mid)ask2(rc, mid+1, r, L, R);
else ask2(lc, l, mid, L, mid), ask2(rc, mid+1, r, mid+1, R);
} queue<pair<int, int> > Q;
int dis[maxn][11];
bool vis[maxn][11]; int main(){
int test;
scanf("%d", &test);
scanf("%d%d%d", &n, &m, &k);
build(1, 1, n);
build2(1, 1, n);
int a, b, c, d, w, tot = posT << 1;
for(int i = 1; i <= m; i ++){
scanf("%d%d%d%d%d", &a, &b, &c, &d, &w);
v1.clear(), v2.clear();
ask1(1, 1, n, a, b);
ask2(1, 1, n, c, d);
++ tot;
for(int j = 0; j < v1.size(); j ++) add(v1[j], tot, 0);
for(int j = 0; j < v2.size(); j ++) add(tot, v2[j] + posT, w); ++ tot;
for(int j = 0; j < v2.size(); j ++) add(v2[j], tot, 0);
for(int j = 0; j < v1.size(); j ++) add(tot, v1[j] + posT, w);
} memset(dis, 0x7f, sizeof dis);
Q.push(make_pair(S, 0)); dis[S][0] = 0;
while(!Q.empty()){
int u = Q.front().first, k_ = Q.front().second;
Q.pop(); vis[u][k_] = false;
for(int i = h[u]; i; i = edge[i].next){
int v = edge[i].to;
if(dis[v][k_] > dis[u][k_] + edge[i].dis){
dis[v][k_] = dis[u][k_] + edge[i].dis;
if(!vis[v][k_])vis[v][k_] = true, Q.push(make_pair(v, k_));
}
if(k_ < k && dis[v][k_+1] > dis[u][k_]){
dis[v][k_+1] = dis[u][k_];
if(!vis[v][k_+1])vis[v][k_+1] = true, Q.push(make_pair(v, k_+1));
}
}
} int ans = 0x7fffffff;
for(int i = 0; i <= k; i ++)
ans = min(ans, dis[T][i]);
if(ans > 1e8)printf("CreationAugust is a sb!");
else printf("%d\n", ans);
return 0;
}