基准时间限制：1 秒 空间限制：131072 KB 分值: 20 难度：3级算法题
收藏
关注B国拥有n个城市，其交通系统呈树状结构，即任意两个城市存在且仅存在一条交通线将其连接。A国是B国的敌国企图秘密发射导弹打击B国的交通线，现假设每条交通线都有50%的概率被炸毁，B国希望知道在被炸毁之后，剩下联通块的个数的期望是多少？
Input
一个数n（2<=n<=100000） 接下来n-1行，每行两个数x,y表示一条交通线。(1<=x,y<=n) 数据保证其交通系统构成一棵树。
Output
一行一个数，表示答案乘2^(n-1)后对1,000,000,007取模后的值。
Input示例
3 1 2 1 3
Output示例
8
这道题期望值是(1+C(1,n-1)*2+C(2,n-1)*3+...+C(n-1,n-1)*n)/2^(n-1)
然后输出答案时把分母去了。就是求和式的表达式了
打表+找规律
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; long long ans=0; int C(int x,int y) { int tot=1; for(int i=1;i<=x;i++) tot*=i; for(int i=1;i<=y;i++) tot/=i; for(int i=1;i<=x-y;i++) tot/=i; return tot; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { ans+=i*C(n-1,i-1); } cout<<ans<<endl; }
然后
2:3
3:8
4:20
5:48
6:112
7:256
8:576
9:1280
乍一眼看不出规律
仔细分解一下
2:3*1
4:5*4
6:7*16
8:9*64
3:2*4
5:3*16
7:4*64
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; #define pp 1000000007 long long ans=0; int n; long long Pow(int p,int Time) { long long tot=1,tmp=p; while(Time) { if(Time%2==1) { tot=tot*tmp%pp; } tmp=tmp*tmp%pp; Time/=2; } return tot; } int main() { scanf("%d",&n); if(n%2==1) { ans=(n+1)/2; ans=ans*Pow(4,n/2)%pp; }else { ans=n+1; ans=ans*Pow(4,n/2-1)%pp; } cout<<ans<<endl; }
基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题
收藏 关注小明对三角函数充满了兴趣，有一天他突然发现一个神奇的性质。
2cos(nx)似乎可以表示成2cos(x)的一个多项式。
但是小明并不能证明它的正确性。
现在给定n，问是否可以表示成这样的多项式，如果可以，只需输出各项系数的和。（Tip:如果这个和很大，那就高精度咯:)）
否则输出No
样例解释：2*cos(3x)=(2*cosx)^3-3*(2*cosx)，系数为1和-3，他们的和为-2。
Input
一个数表示n（n<=1e15)
Output
如果能表示 输出各项系数和 不能 输出No
Input示例
3
Output示例
-2
2cos(x)=2(cos(x))
2cos(2x)=(2cosx)^2-2
归纳证明前k项可以用f(k)系数表达
则f(k+1)=2cos((k+1)x）的系数
cos((k+1)x)=cos(kx)cos(x)-sin(kx)sin(x)
cos((k-1)x)=cos(kx)cos(x)+sin(kx)sin(x)
所以cos((k+1)x)=2cos(kx)cos(x)-cos((k-1)x)
f(k+1)=f(k)*k-f(k-1)
递推+找循环节
#include<cstdio>using namespace std; typedef long long ll; int a[6] = {1, -1, -2, -1, 1, 2}; int main() { ll x; scanf("%lld", &x); printf("%d ", a[(x-1) % 6]); return 0; }