同机房好友发了一个题单，然后。。本蒟蒻又来练DP啦！（被绿题狂虐中
今天继续讲题，又没学啥。。
P5104 红包发红包
拿到这题目，第一眼就发现，每次取的期望不是取一半吗？
然后瞄一眼样例，咦！好像我是对的！
就开始了漫长的证明旅途
嗯很好，我不会，可以转题解。。。
既然不会，就按着我的思路上代码吧！
等等，分数取模！！蒟蒻的我听都没听说过。。还是得靠度娘：
(~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~) 设 (a/bequiv x(mod~p))
(~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Rightarrow a imes b^{-1}equiv x(mod~p))
而(b^{-1})是啥？不就是(b)的逆元吗？
OK，所以答案就是分子乘以分母的逆元
手起，码落！
#include<bits/stdc++.h>
#define re register
#define mod 1000000007
using namespace std;
inline long long Pow(long long x,long long y)
{
re long long sum=1;
for(;y;x=(x*x)%mod,y>>=1)
if(y&1)sum=(sum*x)%mod;
return sum%mod;
}
long long w,n,k;
int main()
{
scanf("%lld%lld%lld",&w,&n,&k);
printf("%lld",w*Pow(Pow(2,k),mod-2)%mod);
return 0;
}
P6154 游走
一句话题意： 求一个有向无环图的路径长度期望。
这题就是图论期望DP的入门题了，答案就是路径总长除以路径条数，所以设(f[u])表示从(u)出发的路径总长，(g[u])表示从(u)出发的路径条数，所以(ans=frac{sum_{i=1}^{n}f[i]}{sum_{i=1}^{n}g[i]})。（注意：不走也是一条路径，即路径条数(+1)，而路径总长不加
状态定义好了，转移方程就简单了：
[g[u]=1+sum_{ver[u][v]==1}g[v]
]
[f[u]=sum_{ver[u][v]==1}f[v]+g[v]
]
最后的分数取模与上题一样，所以不再赘述。
讲完了，手起，码落：
#include<bits/stdc++.h>
#define re register
#define mod 998244353
using namespace std;
const int M=700005,N=100005;
struct egde{int v,net;}e[M];
inline long long Pow(long long x,long long y)
{
re long long sum=1;
for(;y;y>>=1,x=x*x%mod)
if(y&1)sum=sum*x%mod;
return sum;
}
long long f[N],g[N];
int n,m,cnt,hd[N];
inline void add(int u,int v){e[++cnt].v=v,e[cnt].net=hd[u],hd[u]=cnt;}
void dfs(int u)
{
g[u]=1;
for(re int v,i=hd[u];i;i=e[i].net)
{
v=e[i].v;
if(g[v]==0)dfs(v);
g[u]=(g[u]+g[v])%mod;
f[u]=(f[u]+f[v]+g[v])%mod;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(re int i=1,u,v;i<=m;i++)
{
scanf("%d%d",&u,&v);
add(u,v);
}
for(re int i=1;i<=n;i++)
if(g[i]==0)dfs(i);
for(re int i=1;i<=n;i++)f[0]=(f[0]+f[i])%mod,g[0]=(g[0]+g[i])%mod;
printf("%lld",f[0]*Pow(g[0],mod-2)%mod);
return 0;
}
SP1026 FAVDICE - Favorite Dice
一句话题意：一个(n)面的骰子，求期望掷几次能使得每一面都被掷到。（题目本就这一句话
第一眼看过去，擦，这么简单，期望不就是(n)吗？
然后我看着样例输出陷入了沉思。。
还是端正推柿子吧：
第一次取：有(frac{n}{n})的机会取到没取过的点
由于已经取了一个，所以第二次：有(frac{n-1}{n})的机会取到没取过的点，也就是要取(frac{n}{n-1})次。
同理，第三次：有(frac{n-2}{n})的机会取到没取过的点，要取(frac{n}{n-2})次。
......
第(n)次：有(frac{n-n+1}{n})的机会取到没取过的点，要取(n)次。
综上所述，(ans=sum_{i=1}^{n}frac{n}{i})。
SO？手起，码落：
#include<bits/stdc++.h>
#define re register
using namespace std;
int T,n,p;
double ans;
int main()
{
scanf("%d",&T);
for(;T--;)
{
ans=0;
scanf("%d",&n);
for(re int i=1;i<=n;i++)ans+=n*1.0/i;
printf("%.2lf
",ans);
}
return 0;
}