D Makoto and a Blackboard
2 seconds
256 megabytes
standard input
standard output
Makoto has a big blackboard with a positive integer nn written on it. He will perform the following action exactly kk times:
Suppose the number currently written on the blackboard is vv. He will randomly pick one of the divisors of vv (possibly 11 and vv) and replace vv with this divisor. As Makoto uses his famous random number generator (RNG) and as he always uses 5858 as his generator seed, each divisor is guaranteed to be chosen with equal probability.
He now wonders what is the expected value of the number written on the blackboard after kk steps.
It can be shown that this value can be represented as PQPQ where PP and QQ are coprime integers and Q≢0(mod109+7)Q≢0(mod109+7). Print the value of P⋅Q−1P⋅Q−1 modulo 109+7109+7.
The only line of the input contains two integers nn and kk (1≤n≤10151≤n≤1015, 1≤k≤1041≤k≤104).
Print a single integer — the expected value of the number on the blackboard after kk steps as P⋅Q−1(mod109+7)P⋅Q−1(mod109+7) for PP, QQ defined above.
6 1
3
6 2
875000008
60 5
237178099
In the first example, after one step, the number written on the blackboard is 11, 22, 33 or 66 — each occurring with equal probability. Hence, the answer is 1+2+3+64=31+2+3+64=3.
In the second example, the answer is equal to 1⋅916+2⋅316+3⋅316+6⋅116=1581⋅916+2⋅316+3⋅316+6⋅116=158.
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=;
const long long mod=;
int k,pri[MAXN];
bool exist[MAXN];
long long n,inv[],f[][];
long long pOw(long long a,long long m)
{
long long pro;
for(pro=1LL;m;m>>=,a=a*a%mod)
if(m&)
pro=pro*a%mod;
return pro;
}
void pre_calc()
{
memset(exist,true,sizeof(exist));
pri[]=;
for(int i=;i<MAXN;i++)
{
if(exist[i]) pri[++pri[]]=i;
for(int j=;j<=pri[]&&(long long)i*pri[j]<MAXN;j++)
{
exist[i*pri[j]]=false;
if(i%pri[j]==)
break;
}
}
inv[]=;
for(int i=;i<;i++)
inv[i]=pOw(i,mod-);
return;
}
long long calc(long long p,int num)
{
f[][]=1LL;
for(int i=;i<=num;i++)
f[][i]=f[][i-]*p%mod;
for(int t=;t<=k;t++)
{
f[t][]=f[t-][];
for(int i=;i<=num;i++)
f[t][i]=(f[t][i-]+f[t-][i])%mod;
for(int i=;i<=num;i++)
f[t][i]=f[t][i]*inv[i+]%mod;
}
return f[k][num];
}
int main()
{
int num;
pre_calc();
cin>>n>>k;
long long ans=1LL;
for(int i=;i<=pri[]&&(long long)pri[i]*pri[i]<=n;i++) if(n%pri[i]==)
{
for(num=;n%pri[i]==;n/=pri[i],num++);
ans=ans*calc(pri[i],num)%mod;
}
if(n!=) ans=ans*calc(n,)%mod;
cout<<ans;
fclose(stdin);
fclose(stdout);
return ;
}
学习一下 Dinic+当前弧优化
网络流的dinic算法详解以及当前弧优化备注:点开
/*
最大流 Dinic */
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<queue>
#include<cstring>
#define min(x,y) ((x<y)?(x):(y))
#define rev(i)(i&1?(i+1):(i-1))
using namespace std;
typedef long long ll;
int dis[]; //分层图,距源点距离
int cur[]; //当前弧优化
int n,m,ans,st,ed;
struct node{
int x,y,len,nxt;
node(){}
node(int nx,int ny,int nlen,int nnxt){
x=nx;y=ny;len=nlen;nxt=nnxt;
}
} E[];
int head[],cnt;
int bfs(){
for (int i=;i<=n;i++) dis[i]=-;
queue<int> Q;
dis[st]=;Q.push(st);
while (!Q.empty()){
int j=Q.front();
Q.pop();
for (int i=head[j];i;i=E[i].nxt)
if (dis[E[i].y]<&&E[i].len>){
dis[E[i].y]=dis[j]+;
Q.push(E[i].y);
}
}
if (dis[ed]>) return ;
else return ;
}
int find(int x,int low){
int res=;
if (x==ed) return low;
for (int i=cur[x];i;i=E[i].nxt){
cur[x]=i;
if (E[i].len>&&dis[E[i].y]==dis[x]+&&(res=find(E[i].y,min(low,E[i].len))))
{
E[i].len-=res;
E[i^].len+=res;
return res;
}
}
return ;
}
inline void link(int x,int y,int z){
E[++cnt]=node(x,y,z,head[x]);
head[x]=cnt;
E[++cnt]=node(y,x,,head[y]);
head[y]=cnt;
}
int main(){
scanf("%d%d%d%d",&n,&m,&st,&ed);
cnt=;
for (int i=;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
link(a,b,c);
}
ans=;int tans=;
while(bfs()){
for (int i=;i<=n;i++) cur[i]=head[i];
while (tans=find(st,2e6)) ans+=tans;
} printf("%d\n",ans);
return ;
}
网络流
https://www.cnblogs.com/SYCstudio/p/7260613.html
经典的最大流题POJ1273
最新文章
- CocoaPods升级,升级以后出现bug的解决方法(升级必看!)
- Hadoop NameNode的ZKFC机制
- track message forwards, avoiding request loops, and identifying the protocol capabilities of all senders along the request/response chain
- HashMap学习
- 深度优先搜索 codevs 1065 01字符串
- Storm实时流处理Hello World
- centos7上源码安装mysql5.7.11
- PCB正片和负片有什么区别
- 2014 android毕设代做 代做Android毕设 安卓毕设
- 浅谈HTML之模仿人人网登陆界面(新手必学)
- Webdriver其他定位方式
- CRM权限管理
- MQTT 简介
- Spider_Man_5.2 の Mongodb_使用
- 用API给用户添加职责
- SQLServer Merger Using语法使用和注意点
- 基于 websocket 实现的 im 实时通讯案例
- Django3 Django 路由分发,反向解析,2.0版本的path
- 在线HTML编辑器KindEditor
- c# Session写入读取操作
热门文章
- 可决系数R^2和方差膨胀因子VIF
- 【LuoguP2792 】[JSOI2008]小店购物(最小树形图)
- ESP8266-01
- springboot自定义异常数据
- #452 Div2 Problem C Dividing the numbers ( 思维 || 构造 )
- codeforces 868C - Qualification Rounds(构造)
- 【PowerOJ1752&;网络流24题】运输问题(费用流)
- Solr Windows环境安装配置
- Spring Boot 中使用 spring-boot-devtools (使用 Gradle 作为构建工具)
- Flask中的实例化配置