http://acm.hdu.edu.cn/showproblem.php?pid=6395
Sequence
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1475 Accepted Submission(s): 539
Your job is simple, for each task, you should output Fn module 109+7.
Then, for the next T lines, each line consists of 6 integers, A , B, C, D, P, n.
1≤T≤200≤A,B,C,D≤1091≤P,n≤109
3 3 2 1 3 5
3 2 2 2 1 4
24
商的个数很少 我们可以 分段矩阵快速幂 怕超时 可以先打1e5的表 一开始以为要用逆元解决问题 真的智障了
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define fillchar(a, x) memset(a, x, sizeof(a))
#define huan printf("\n");
#define debug(a,b) cout<<a<<" "<<b<<" "<<endl;
using namespace std;
typedef long long ll;
const ll maxn=,inf=0x3f3f3f3f,mod=1e9+;
bool Finish_read;
template<class T>inline void read(T &x)
{
Finish_read=;
x=;
int f=;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')f=-;
if(ch==EOF)return;
ch=getchar();
}
while(isdigit(ch))x=x*+ch-'',ch=getchar();
x*=f;
Finish_read=;
}
template<class T>inline void print(T x)
{
if(x/!=)print(x/);
putchar(x%+'');
}
template<class T>inline void writeln(T x)
{
if(x<)putchar('-');
x=abs(x);
print(x);
putchar('\n');
}
template<class T>inline void write(T x)
{
if(x<)putchar('-');
x=abs(x);
print(x);
}
ll n,a,b,c,d,p;
struct Matrix
{
ll m[maxn][maxn];
Matrix()
{
memset(m,,sizeof(m));
}
void init()
{
for(int i=; i<maxn; i++)
for(int j=; j<maxn; j++)
m[i][j]=(i==j);
}
Matrix operator +(const Matrix &b)const
{
Matrix c;
for(int i=; i<maxn; i++)
{
for(int j=; j<maxn; j++)
{
c.m[i][j]=(m[i][j]+b.m[i][j])%mod;
}
}
return c;
}
Matrix operator *(const Matrix &b)const
{
Matrix c;
for(int i=; i<maxn; i++)
{
for(int j=; j<maxn; j++)
{
for(int k=; k<maxn; k++)
{
c.m[i][j]=(c.m[i][j]+(m[i][k]*b.m[k][j])%mod)%mod;
}
}
}
return c;
}
Matrix operator^(const ll &t)const
{
Matrix ans,a=(*this);
ans.init();
ll n=t;
while(n)
{
if(n&) ans=ans*a;
a=a*a;
n>>=;
}
return ans;
}
};
ll f[];
pair<ll,ll> solve(ll x,ll y,ll z,ll m)
{
Matrix a,b,temp;
b.m[][]=d;b.m[][]=c;b.m[][]=;
b.m[][]=;b.m[][]=;
a.m[][]=x;
a.m[][]=y;
a.m[][]=z;
temp=b^(m);
temp=temp*a;
return mp(temp.m[][],temp.m[][]);
}
int main()
{
int t;
read(t);
while(t--)
{
read(a);read(b);read(c);read(d);read(p);read(n);
f[]=a;f[]=b;
for(int i=;i<=;i++)
f[i]=(c*f[i-]%mod+d*f[i-]%mod+p/i)%mod;
if(n<=)
writeln(f[n]);
else
{
ll l=;
pair<ll,ll> pp(f[l],f[l-]);l++;
while(l<=n)
{
ll temp=p/l;
if(temp==)
{
pp=solve(pp.fi,pp.se,temp,n-l+);
writeln(pp.fi);
break;
}
ll temp2=p/temp;
if(temp2>=n)
{
pp=solve(pp.fi,pp.se,temp,n-l+);
writeln(pp.fi);
break;
}
else
{
pp=solve(pp.fi,pp.se,temp,temp2-l+);
l=temp2+;
}
}
}
}
}
http://acm.hdu.edu.cn/showproblem.php?pid=6386
Age of Moyu
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 2237 Accepted Submission(s): 683
The i-th (1≤i≤M) line connects port Ai and Bi (Ai≠Bi) bidirectionally, and occupied by Ci Weitian (At most one line between two ports).
When Mr.Quin only uses lines that are occupied by the same Weitian, the cost is 1 XiangXiangJi. Whenever Mr.Quin changes to a line that is occupied by a different Weitian from the current line, Mr.Quin is charged an additional cost of 1 XiangXiangJi. In a case where Mr.Quin changed from some Weitian A's line to another Weitian's line changes to Weitian A's line again, the additional cost is incurred again.
Mr.Quin is now at port 1 and wants to travel to port N where live many fishes. Find the minimum required XiangXiangJi (If Mr.Quin can’t travel to port N, print −1instead)
For each test case,In the first line, two integers N (2≤N≤100000) and M (0≤M≤200000), representing the number of ports and shipping lines in the city.
In the following m lines, each contain three integers, the first and second representing two ends Ai and Bi of a shipping line (1≤Ai,Bi≤N) and the third representing the identification number Ci (1≤Ci≤1000000) of Weitian who occupies this shipping line.
1 2 1
1 3 2
2 3 1
2 0
3 2
1 2 1
2 3 2
-1
2
解析 这题标程有些错误 而且是原题 既然标程是错的 也就不用按照 题解来写了 感觉现在最靠谱的思路就是 建虚点了 边权相同且相邻的点 建立一个虚点x
其他点到x距离为1的单向边 x到其他点距离为0单向边 把原来的去掉 跑最短路就是答案。这道题真是服了。。。
#include <bits/stdc++.h>
#define Pii pair<int,int>
using namespace std;
typedef long long ll;
const int maxn=1e5+;
const int maxm=2e5+;
const int maxnn=1e6+;
const int inf=;
vector<int> GG[maxn];
int from[maxm],to[maxm],c[maxm];
int n,cnt,nowc,dis[maxnn]; //cnt:n+虚点数
bool v[maxm],vis[maxnn];
struct node{
int d,x;
bool operator < (const node& b) const
{return d>b.d;}
};
priority_queue<node> Q;
int _first[maxnn],_tip[maxnn],_w[maxnn],_next[maxnn],edge;
inline void dijk()
{
int i,u,vv,len,num;
node tmp;
for(i=;i<=cnt;i++) dis[i]=inf;
dis[]=;
Q.push((node){,});
while(!Q.empty())
{
tmp=Q.top();
Q.pop();
u=tmp.x;
if(vis[u]==true) continue;
vis[u]=true;
num=_first[u];
while(num!=-)
{
vv=_tip[num];
if(dis[u]!=inf&&dis[vv]>dis[u]+_w[num])
{
dis[vv]=dis[u]+_w[num];
Q.push((node){dis[vv],vv});
}
num=_next[num];
}
}
return;
}
inline void dfs(int x)
{
//add(x,cnt,1);
_tip[++edge]=cnt;
_w[edge]=;
_next[edge]=_first[x];
_first[x]=edge; //add(cnt,x,0);
_tip[++edge]=x;
_w[edge]=;
_next[edge]=_first[cnt];
_first[cnt]=edge; int i,len=GG[x].size(),num;
for(i=;i<len;i++)
{
num=GG[x][i];
if(c[num]==nowc&&!v[num])
{
v[num]=true;
if(from[num]==x) dfs(to[num]);
else dfs(from[num]);
}
}
return;
}
int main()
{
int i,m;
while(scanf("%d%d",&n,&m)==)
{
edge=;
cnt=n;
memset(v,,sizeof(v));
memset(vis,,sizeof(vis));
memset(_first,-,sizeof(_first));
for(i=;i<=m;i++)
{
scanf("%d%d%d",&from[i],&to[i],&c[i]);
GG[from[i]].push_back(i);
GG[to[i]].push_back(i);
}
for(i=;i<=m;i++)
if(!v[i])
{
cnt++;
nowc=c[i];
dfs(from[i]);
}
dijk();
if(dis[n]==inf) printf("-1\n");
else printf("%d\n",dis[n]);
//test();
for(i=;i<=n;i++) GG[i].clear();
}
return ;
}