全场六零赛(1.29)
T1
【题目描述】
吾乃闪耀知识的灯塔。
B 君有个n个点,m个边的仙人掌。所谓仙人掌,就是任何一个点至多属于一个环。
每条边有 1/2 的概率被删掉。问期望剩下多少个边联通块。所谓边联通块,就是问剩下的边,构成多少个联通块,单独一个点不算做联通块。
B君不喜欢实数,B君想知道答案乘以之后mod 1000000007 的结果。
【输入格式】
第一行两个整数n,m。以下m行,每行两个整数x,y,表示树的一条边。
【输出格式】
一个整数表示答案。
【样例输入】
3 2
1 2
2 3
【样例输出】
3
【数据规模与约定】
对于 100% 的数据,满足1<=n<=1000000
对于 40% 的数据,满足1<=n<=15
对于 70% 的数据,满足1<=n<=1000
分析:
边连通块的数量期望等于总连通块的个数期望减去单点的个数期望
期望是可以直接相加的:
单点的个数的期望=每个点单独的概率和
度数为的点,独立的概率为
树:总联通块个数的期望为
假设没有环,那么初始有个连通块,条边
每多一条边,就少一个联通块,联通块个数为
如果有环的话,相当于连接连通块的边变少了
假设有个环,连通块个数为
其中等于每个环出现的概率和,长度为的环,出现概率为
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int p=1e9+7;
const int N=1000010;
vector<pair<int, int> > a[N];
vector<int> z;
int n,m,x,y;
int d[N],f[N],b[N],e[N<<1][2];
bool vis[N<<1];
void bfs()
{
queue<int> q;
q.push(1);
d[1]=1;
while (!q.empty())
{
int now=q.front(); q.pop();
for (int i=0;i<a[now].size();i++)
{
if (d[a[now][i].first]==0)
{
f[a[now][i].first]=now;
d[a[now][i].first]=d[now]+1;
vis[a[now][i].second]=1;
q.push(a[now][i].first);
}
else continue;
}
}
}
int dis(int x,int y)
{
int z=0;
while (x!=y) //两个结点的距离
{
if (d[x]<d[y]) swap(x,y);
x=f[x];
z++;
}
return z;
}
int main()
{
freopen("licht.in","r",stdin);
freopen("licht.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=0;i<m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
a[x].push_back(make_pair(y,i));
a[y].push_back(make_pair(x,i));
e[i][0]=x; e[i][1]=y;
assert(1<=x&&x<=n);
assert(1<=y&&y<=n);
assert(x!=y);
}
bfs();
for (int i=0;i<m;i++)
{
if (vis[i]){
} else {
z.push_back(dis(e[i][0],e[i][1])+1);
}
}
assert(z.size()==m-n+1);
b[0]=1;
for (int i=0;i<m;i++)
{
b[i+1]=b[i]*2%p;
}
ll ans=(ll)b[m-1]*(2*n-m)%p;
for (int i=1;i<=n;i++)
{
ans-=b[m-a[i].size()];
if (ans<0) ans+=p;
}
for (int i=0;i<z.size();i++)
{
ans+=b[m-z[i]];
if (ans>=p) ans-=p;
}
printf("%lld\n",ans);
return 0;
}
T2
【题目描述】
我爱北京*。
去年的暑假到现在,B君在北京读大四,对*制度的「优越性」有了深刻的认识。
输入5个整数。
定义
换句话说相当于以为初始值的一个线性递推数列。
换句话说相当于把个函数嵌套使用。
B君想知道 mod p 的结果。
【输入格式】
第一行一个整数表示数据组数。
接下来组数据,每组数据为一行五个整数,含义见题目描述。
【输出格式】
对于每组数据,输出一个整数表示答案。
【样例输入】
1
0 1 2 2 1000
【样例输出】
8
【数据规模与约定】
对于100% 的数据,满足。
对于20%的数据,满足。
对于60%的数据,满足。
分析:
一开始想的很简单,直接用矩阵快速幂
但是答案要求只能对最后答案取%,所以普通的矩阵快速幂只能解决的情况
正解
找循环节。
最简单的直接矩阵乘法。
如果已知模数,可以暴力,不知道模数的话,BSGS。
#include<bits/stdc++.h>
#define ll long long
#define X first
#define Y second
using namespace std;
const int N=1000010;
ll A,B,n,k,p,b[220];
int lc;
typedef pair<ll,ll> LL;
typedef pair<int,int> ii;
map<ll,ll> mp;
pair<LL,int> l[N];
ll mul(ll x,ll y)
{
return x*y-(ll)((long double)x*y/p)*p;
}
LL operator *(const LL &A,const LL &B)
{
return ii((mul(A.X,B.X)+mul(A.Y,B.Y))%p,(mul(A.X,B.Y)+mul(A.Y,(B.X-B.Y+p)))%p);
}
LL F(ll n)
{
if (n==-1)
return LL(1,0);
if (n==0)
return LL(0,1);
if (n%2){
LL u=F(n-1);
return LL(u.Y,(u.X+u.Y)%p);
} else {
LL u=F(n/2);
return LL(mul(2*u.Y+p-u.X,u.X),(mul(u.X,u.X)+mul(u.Y,u.Y))%p);
}
}
ll G(ll n)
{
LL u=F(2*n-1);
return (mul(A,u.X)+mul((B-A),u.Y))%p;
}
ll P(ll p)
{
if (p%10==1||p%10==9)
return p-1;
if (mp.find(p)!=mp.end())
return mp[p];
::p=p;
lc=0;
LL u(1,1),w(1,0);
int x=int(sqrt(2*p))+1;
for (int i=0;i<x;i++)
{
l[lc++]=make_pair(w,-i);
w=w*u;
}
sort(l,l+lc);
u=w;
for (ll i=x;;i+=x)
{
int t=lower_bound(l,l+lc,make_pair(w,-1000000))-l;
if (t<lc&&l[t].X==w)
return mp[p]=i+l[t].Y;
w=w*u;
}
assert(0);
}
ll gcd(ll x,ll y)
{
ll r=x%y;
while (r)
{
x=y;
y=r;
r=x%y;
}
return y;
}
ll lcm(ll x,ll y)
{
return x/gcd(x,y)*y;
}
ll cal(ll n)
{
if (mp.find(n)!=mp.end())
return mp[n];
int N=n;
ll z=1;
for (int i=2;i*i<=n;i++)
{
if (n%i==0)
{
ll w=P(i);
for (n/=i;n%i==0;n/=i)
w*=i;
z=lcm(z,w);
}
}
if (n>1) z=lcm(z,P(n));
return mp[N]=z;
}
int main()
{
//freopen("erinnerung.in","r",stdin);
//freopen("erinnerung.out","w",stdout);
int T;
scanf("%d",&T);
while (T--)
{
scanf("%lld%lld%lld%lld%lld",&A,&B,&n,&k,&p);
b[0]=p;
for (int i=1;i<=k;i++)
b[i]=cal(b[i-1]);
n%=b[k];
for (int i=k-1;i>=0;i--)
{
p=b[i];
n=G(n);
}
printf("%lld\n",n);
}
return 0;
}
T3
【题目描述】
金钱与死亡紧密相连。
去年的现在,B君还在丹麦进行交换学习,对资本主义制度的「优越性」有了深刻的认识。
欧元是很重要的货币,他有15种面额,我们以分 (cent) 来考虑面额。
面额是
B 君当前有一个面值为的货币,为以上十五个数之一。
B 君希望去自动贩卖机上买一个价值为的商品,但是自动贩卖机收钱的时候,只收恰好为的货币,不能多也不能少。
B君决定去旁边的商店买一些东西,B君可以买价值为整数分的东西。
店家会用以上15种货币来找钱,然后B君一店家找的钱去自动贩卖机上购买价值为的东西。
但是,店家是充满恶意的,店家会以尽量差的形式给B君找钱使得B君不能去⾃动贩卖机上购买东西。假如说刚开始B君拿着一张分巨款,然后B君希望买的的东西,B君必须去店家买至少49997分的商品才可以。如果B君买的更少,即找钱的额度超过了4分,店家便可以只找给B君2分和5分,来阻止B君买1分的商品。
B君希望知道,他至少要在店家花多少分,才能得到恰好的零钱,去自动贩卖机上买自己想要的东西。
B 君只能去店家购买一次。
B君确信,直接去店家购买的商品,会被恰好找回的钱,所以这个问题一定有解。
【输入格式】
第一行一个整数表示数据组数。
接下来组数据,每组数据为一行两个整数和,含义见题目。
【输出格式】
对于每组数据,输出⼀个整数表⽰最少的花费。
【样例输入】
2
2 1
50000 1
【样例输出】
1
49997
【数据规模与约定】
对于100%的数据,满足题目中关于和的限制,并且。
对于 70% 的数据,满足只出现前12种面额,即。
对于 40% 的数据,满足只出现前9种面额,即。
分析:
精妙的搜索,直接枚举找钱的所有拆分,做一次背包。验证
是否有解。
更精妙的搜索,注意到店家不可能找钱时给2个1 分。
最精妙的搜索,一位一位搜。
上一篇: 使用axis2传输附件
下一篇: 埃森哲发布2015年五大IT趋势预测
推荐阅读