首页 > 代码库 > NOIP2017模拟赛 senior 6.29 T1 码灵鼠(A)
NOIP2017模拟赛 senior 6.29 T1 码灵鼠(A)
NOIP2017模拟赛 senior 6.29 T1 码灵鼠(A)
Description
码零鼠是一只很喜欢mx数学的神犇,上面那个不是ta本人的样子。这天,ta在研究一个神奇的数列,这个数列是这样的:
a0 = 1
an = ai + aj (n>=1, i,j均在[0,n-1]内均匀随机)
Ta想知道对于给定的n,an的期望值是多少,你能告诉ta吗?
出于ta对整数的热爱,你只需要输出答案向下取整后的值
Input
一个整数T,表示数据组数
每组数据一行,包括一个整数n
Output
一个整数E(an),
这个码灵鼠难道就是传说中的洋芋= =(手动滑稽)
不过他的问题很高大上啊,居然问我随便一个n的期望是多少,相当有深度。
那么这个问题我们怎么解决呢?我们可以随便取之前的几个数来推理一下:
对于a0直接等于1就不说了吧。
a1= 2;
a2= 3;
a3= 4
……
an= n+1;
这样的推导能给我们一个大致的思路对吧。
那么我们是否能够证明我们的推导是正确的呢:
结论:an = n + 1
下面归纳地进行证明。
对于n = 0,n = 1,有a0 = 1,a1 = 2,满足an = n + 1。
当n > 1时:
an = E(ai + aj),fori,j∈[0,n)
an = E(ai)+ E(aj),fori,j∈[0,n)
an = 2E(ai),fori∈[0,n)
E(ai)=(∑0~n-1(ai))/ n = n(n + 1)/ 2n = (n +1)/2
∴ an = n + 1
哇,非常严密的论证!所以说,推
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define INT_MAX_ 0x7fffffff 7 #define LONG_MAX_ 0x7fffffffffffffffll 8 #define pi acos(-1) 9 #define N 1001010 #define M 1001011 using namespace std;12 13 inline long long read()14 {15 long long data=http://www.mamicode.com/0,w=1;16 char ch=0;17 while(ch!=‘-‘ && (ch<‘0‘ || ch>‘9‘)) ch=getchar();18 if(ch==‘-‘) w=-1,ch=getchar();19 while(ch>=‘0‘ && ch<=‘9‘) data=http://www.mamicode.com/data*10+ch-‘0‘,ch=getchar();20 return data*w;21 }22 23 inline void write(long long x)24 {25 if(x<0) putchar(‘-‘),x=-x;26 if(x>9) write(x/10);27 putchar(x%10+‘0‘);28 }29 30 long long T,n;31 32 int main()33 {34 freopen("A.in","r",stdin);35 freopen("A.out","w",stdout);36 37 T = read();38 while(T--)39 {40 n = read();41 write(n+1);42 putchar(‘\n‘);43 }44 45 return 0;46 }
出来就是这么简单!!
NOIP2017模拟赛 senior 6.29 T1 码灵鼠(A)