全程5小时，一题都没过。全靠队友带躺。
后来题解出来后，把比赛时两道没过的题目改了改，这里记录一下。
https://nanti.jisuanke.com/t/41299
这题在比赛时YY出了答案，。
类似题目 https://blog.csdn.net/zzkksunboy/article/details/78867686
然后就是幂塔函数求模运算，但是用扩展欧拉定理实现时，遇到了大量的坑。
图片.png
换句话说，我们就要考虑两种情况。
1 a、m互质。
2 a、m不互质。
第一种情况直接计算，第二种情况，根据上一层递归的返回值和当前层的phi(m)比较，确定是否要为结果加上phi(m)。
代码在实现时，使用了pair存储。first位置存储当前结果，second位置存储得到当前结果时，是否出现了超过phi(m)的情况。
其他坑：
1 b=0的情况，答案为1。
2 m=1的情况，答案为0。
3 a=1的情况，答案为1%m。
代码如下
/*
幂塔函数求模运算
类似题目 https://blog.csdn.net/zzkksunboy/article/details/78867686
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<ll,int> pii;
ll gcd(ll a,ll b) {
return !b?a:gcd(b,a%b);
}
ll phi(ll m) {
int ans=m;
for(ll i=2; i<=sqrt(m+0.5); i++) {
if(m%i==0) {
ans=ans/i*(i-1);
while(m%i==0) m/=i;
}
}
if(m>1) ans=ans/m*(m-1);
return ans;
}
pii ksm(ll a,ll b,ll MOD) { //计算a^b%MOD 并判断是否存在结果超出MOD的情况 pair的第二项为0表示存在
ll ans=1;
int flag=1;
while (b) {
if (b&1) {
if ((ans*=a)>=MOD) flag=0;
ans%=MOD;
}
b>>=1;
if (b) {
if ((a*=a)>=MOD) flag=0;
a%=MOD;
}
}
return make_pair(ans,flag);
}
pii solve(ll a,ll b,ll MOD) {
if (MOD==1) return make_pair(0,0); //模1结果肯定是0
if (b==0) { //特判b=0的情况
return make_pair(1,0);
}
if (b==1) { //b=1为边界
if(a<MOD) return make_pair(a%MOD,1);
else return make_pair(a%MOD,0);
}
pii res=solve(a,b-1,phi(MOD));
if (gcd(a,MOD)==1) return ksm(a,res.first,MOD); //a和m互质的情况
//接下来是不互质的情况
if (!res.second) res.first+=phi(MOD);
return ksm(a,res.first,MOD);
}
int main() {
//freopen("2.in","r",stdin);
int T;
ll a,b,m;
scanf("%d", &T);
while(T--) {
scanf("%lld%lld%lld", &a,&b,&m);
if(a!=1) printf("%lld\n", (solve(a,b,m).first+m)%m);
else printf("%lld\n",1%m);
}
return 0;
}
https://nanti.jisuanke.com/t/41301
这题和《绿豆蛙的归宿》不同，由于代价中存在到达某个顶点的天数。所以要先沿着DAG进行一次DP，求出到达每个点的期望天数。然后再次进行一次DP，根据期望天数，求出期望的耐久度消耗。（比赛时将天数直接作为dfs的深度或者bfs的层数计算，所以无法跑出样例）
官方题解是如下这么说的。
图片.png
看起来不难，只要分两次做即可。但在实现时，为了让递推方便，需要将dp[u]移项。
我们设到达u点的期望时间为f[u]，期望耐久度消耗为g[u]。
将
化简后得到
同理可得
化简得
注意这里是f[u]，不是f[v]。因为我们认为此时处在u点。
如此一来，通过从1号点开始dfs，回溯时计算答案即可（代码中对应method_1）。
但是，这样虽然能算出答案，实际运行结果确时TLE。
原因暂时不清楚。可能是因为dfs会对一些点进行额外访问。
由于是DAG，所以可以用bfs维护拓扑序，做到每个点只访问一次。
但实现时需要对上述转移做修改。
因为bfs时，唯一确定答案的是终点n（f[n]=g[n]=0.0）。所以要建反图，在反图上从n向1进行拓扑序DP。（对应代码中method_2）
这样一来，我们在转移时，对于反图上的边u->v，就需要计算u对v的贡献。
因此我们调整转移方程如下。
化简得
同理
化简得
注意两点
1 关于g数组的递推式中，用到的是f[v]而不是f[u]，因为我们认为此时处在v点（因为在算v）。
2 由于是在拓扑排序中计算每个点对后继点的贡献，所以做不到在算完原图中某个点的所有后继点之后追加常数。所以要将贡献项移入中。
代码如下
/*
*/
#define method_2
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
int n,m,cnt,T,du[maxn],head[maxn];
double f[maxn],g[maxn]; //f[i]表示到i的期望天数
struct node {
int from,to;
} edge[maxn*2];
inline void add(int from,int to) {
edge[++cnt].to=to;
edge[cnt].from=head[from];
head[from]=cnt;
}
inline void init() {
memset(head,0,sizeof(head));
memset(du,0,sizeof(du));
cnt=1;
}
inline double dfs1(int x){
f[x]=0;
if(x==n){
return 0;
}
for(int i=head[x]; i; i=edge[i].from){
int y=edge[i].to;
f[x]+=dfs1(y)/du[x];
}
f[x]+=((double)du[x]+1)/du[x];
return f[x];
}
inline double dfs2(int x){
g[x]=0;
if(x==n){
return 0;
}
for(int i=head[x]; i; i=edge[i].from){
int y=edge[i].to;
g[x]+=dfs2(y)/du[x];
}
g[x]+=((double)du[x]+1)/du[x]*f[x];
return g[x];
}
int main() {
//freopen("4.in","r",stdin);
scanf("%d",&T);
while(T--) {
init();
scanf("%d%d",&n,&m);
int u,v;
for(int i=1; i<=m; i++) {
scanf("%d%d",&u,&v);
add(u,v);
du[u]++;
}
dfs1(1);
dfs2(1);
printf("%.2lf\n",g[1]);
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
int n,m,cnt,T,du[maxn],ru1[maxn],ru2[maxn],head[maxn];
double f[maxn],g[maxn]; //f[i]表示到i的期望天数
queue<int>q;
struct node {
int from,to;
} edge[maxn*2];
inline void add(int from,int to) {
edge[++cnt].to=to;
edge[cnt].from=head[from];
head[from]=cnt;
}
inline void init() {
memset(head,0,sizeof(head));
memset(du,0,sizeof(du));
memset(ru1,0,sizeof(ru1));
memset(ru2,0,sizeof(ru2));
for(int i=1;i<=n;i++) f[i]=g[i]=0;
cnt=1;
}
inline void bfs1(){
while(q.size()) q.pop();
q.push(n);
while(q.size()){
int x=q.front();q.pop();
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to;
f[y]+=(f[x]+1+(1.0/du[y]))/(du[y]);
if(--ru1[y]==0) q.push(y);
}
}
}
inline void bfs2(){
while(q.size()) q.pop();
q.push(n);
while(q.size()){
int x=q.front();q.pop();
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to;
g[y]+=(g[x]+f[y]+(f[y]/du[y]))/(du[y]);
if(--ru2[y]==0) q.push(y);
}
}
}
int main() {
//freopen("4.in","r",stdin);
scanf("%d",&T);
while(T--) {
init();
scanf("%d%d",&n,&m);
int u,v;
for(int i=1; i<=m; i++) {
scanf("%d%d",&u,&v);
add(v,u);
ru1[u]++,ru2[u]++,du[u]++;
}
bfs1();
bfs2();
printf("%.2lf\n",g[1]);
}
return 0;
}
#endif
#ifdef method_3
/*
*/
#endif
