Tax collectors in the Roman empire, called publicans, are not well perceived, and for good reason. However, they are necessary for the running of the empire. Your job is to estimate how much money Rome will receive in taxes. Not everyone pays, but at least one person is guaranteed to pay. The trouble is you can never really know who will and won’t pay.
Given a list of what citizens would pay if they did pay taxes,output the average of all possible sums of taxes received.
Given a list of what citizens would pay if they did pay taxes,output the average of all possible sums of taxes received.
输入
The first line of the input will be a single integer, n ≤ 1, 000. There will be n test cases that follow.
Each test case begins with a single integer p denoting the number of people in Rome, 1 ≤ p ≤ 10, 000. The next line will contain p space separated integers, 0 < vi < 10, 000,denoting the amount of taxes that each citizen would pay if they decided to pay.
Each test case begins with a single integer p denoting the number of people in Rome, 1 ≤ p ≤ 10, 000. The next line will contain p space separated integers, 0 < vi < 10, 000,denoting the amount of taxes that each citizen would pay if they decided to pay.
输出
Each test case should contain a single floating point number denoting the average taxes paid, accurate and truncated to three decimal places.
样例输入 Copy
2
5
1 2 3 4 5
5
10 11 12 13 14
样例输出 Copy
7.742 30.968
这个题就是求他的全部的子段和除以他的个数
就是 (全部字段和)/(2^n-1)
全部字段和为sum*(2^(n-1))
但是这个题是n很大，所以盲猜一波当n很大的时候1/（2^(n-1))为0
sum*(2^(n-1))/(2^n-1)==sum/(2-1/(2^(n-1))
#include<iostream> #include<algorithm> #include<set> #include<map> #include<queue> #include<cstring> using namespace std; typedef long long ll; const int maxn=1e5+100; ll a[maxn]; ll qpow(ll a,ll b){ ll ans=1; while(b){ if(b&1){ ans=(ans*a); } a=(a*a); b>>=1; } return ans; } int main(){ int t; cin>>t; while(t--){ int n; cin>>n; ll ans=0; for(int i=1;i<=n;i++){ cin>>a[i]; ans+=a[i]; } if(n>62){ printf("%.3lf ",1.0*ans/2.0); } else{ ll tmp=qpow(2,n-1); ll tmp1=tmp*2-1; double tmp2=1.0*ans*tmp/tmp1; printf("%.3lf ",tmp2); } } }
序列字段积和
链接：https://ac.nowcoder.com/acm/contest/13504/I
来源：牛客网
众所周知，一个序列拥有许多非空子序列。
所谓子序列就是在原序列中任意删除 0 个或多个元素，然后保持剩下元素的顺序不变所形成的序列。非空子序列集意味着剩下的子序列不能为空。
比如对于序列[1, 2, 3]，它的所有非空子序列为：[1, 2, 3]，[1, 2]，[1, 3]，[2, 3]，[1]，[2]，[3]。再比如序列 [1, 1]，它的非空子序列有：[1, 1]，[1] (删除了第一个 1)，[1] (删除了第二个1) 。
现在母牛哥手里有一个长度为 n 的正整数序列，他现在要为这个序列的所有非空子序列打分。对于一个序列而言，它的评分标准为序列里所有数的乘积（只有一个数的序列，分数就是这个数）。
母牛哥想要知道所有分数的和，但由于结果太大了，所以你只要告诉母牛哥结果对 1000000007 取模即可。
所谓子序列就是在原序列中任意删除 0 个或多个元素，然后保持剩下元素的顺序不变所形成的序列。非空子序列集意味着剩下的子序列不能为空。
比如对于序列[1, 2, 3]，它的所有非空子序列为：[1, 2, 3]，[1, 2]，[1, 3]，[2, 3]，[1]，[2]，[3]。再比如序列 [1, 1]，它的非空子序列有：[1, 1]，[1] (删除了第一个 1)，[1] (删除了第二个1) 。
现在母牛哥手里有一个长度为 n 的正整数序列，他现在要为这个序列的所有非空子序列打分。对于一个序列而言，它的评分标准为序列里所有数的乘积（只有一个数的序列，分数就是这个数）。
母牛哥想要知道所有分数的和，但由于结果太大了，所以你只要告诉母牛哥结果对 1000000007 取模即可。
输入描述:
第一行为 n，表示这个序列长度为 n (1 <= n <= 10^6)。
接下来的一行有 n 个数字 a1, a2, …… , an (1 <= ai <= 2 * 10^9) 表示序列的 n 个数字。
输出描述:
一个非负整数，表示结果对 1000000007 取模。
示例2
输出
复制3
这是一个结论题
#include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int maxn=5e6+100; const int mod=1e9+7; ll a[maxn]; int main(){ int n; cin>>n; ll sum=0; for(int i=1;i<=n;i++){ cin>>a[i]; sum+=a[i]; } if(n==1){ cout<<sum<<endl; return 0; } ll ans=0; for(int i=1;i<=n;i++){ ll z=sum-a[i]; ans=(ans+z*a[i])%mod; } cout<<(ans+1)%mod<<endl; }