Orzz(j)yf、kb都太强啦比我不知道高到哪里去了 Orz。。。

T1 币 (coin)

每次询问跑一次 $O(n^2)$得 60 分。
所以此题需要预处理。
设 $f[i][j]$表示在 $n=i$的情况下，第 $j$个位置的权重（一个小于 1 的实数，也就是设 $j$这个位置的数为 1 时，最后先手对这个位置的期望）。
我们不难得到递推式：
$f[i][j]=1.0-(f[i-1][j]+f[i-1][j-1])/2$

所以 $O(n^2)$预处理，$O(n)$询问。

代码：

#include <bits/stdc++.h>
using namespace std;
double f[1005][1005],ans;
int t,n;
int main()
{
    freopen("coin.in","r",stdin),freopen("coin.out","w",stdout);
    for(int i=1;i<=1000;i++)
        for(int j=1;j<=i;j++)
            f[i][j]=1.0-(f[i-1][j]+f[i-1][j-1])/2;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n),ans=0;
        for(int i=1,a;i<=n;i++)scanf("%d",&a),ans+=a*f[n][i];
        printf("%.3lf\n",ans);
    }
    return 0;
}

T2 △(triangle)

其实这题解法真的很暴力。。。
如果要算出原图符合条件的三元组个数，就暴力算。
枚举一个点 $i$，再枚举与它有边链接的点 $j$，再枚举与 $j$有边链接的点 $k$，再判断 $k$与 $i$是否有边链接，如果有则 ans++。
但在这里我们需要保证：$i<j<k$，不然会重复计算，这个在读入边的时候就可以处理掉。

怎么解补图中符合条件的三元组个数呢？
看评分标准，其实是个提示。我们如果求出原图、补图的符合条件的三元组个数之和不就行了嘛。。。

显然如果整个图任意两个点之间都有一条边，那么三元组个数之和为 $C(n,3)=n×(n-1)×(n-2)/6$
所以我们要找出不能组成符合条件的三元组的个数。

这就很简单了。对于点 $i$, 它的出度为 $ocnt[i]$，那么与它不相邻的点的个数为 $n-1-a[i]$（-1 是因为与它相邻的还包括它自己）。
所以组成的不符合的三元组个数就是：$ocnt[i]*(n-1-ocnt[i])/2$
所以总共不符合条件的三元组个数为：

所以就AC了
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
static const LL maxs=100100;
LL n,m,tot,ans,ocnt[maxs+5],to[maxs+5],nxt[maxs+5],head[maxs+5],size;
queue<LL> que;
bool book[maxs+5];
void push(LL u,LL v){to[size]=v,nxt[size]=head[u],head[u]=size,size++;}
int main()
{
    freopen("triangle.in","r",stdin),freopen("triangle.out","w",stdout);
    scanf("%lld%lld",&n,&m),memset(head,-1,sizeof(head));
    for(LL i=1,u,v;i<=m;i++)
    {
        scanf("%lld%lld",&u,&v);
        if(u>v)swap(u,v);
        push(u,v),ocnt[u]++,ocnt[v]++;
    }
    for(LL i=1;i<=n;i++)
    {
        tot+=ocnt[i]*(n-1-ocnt[i]);
        for(LL j=head[i];j!=-1;j=nxt[j])que.push(to[j]),book[to[j]]=1;
        while(!que.empty())
        {
            LL f=que.front();que.pop();
            for(LL j=head[f];j!=-1;j=nxt[j])ans+=book[to[j]];
        }
        for(LL j=head[i];j!=-1;j=nxt[j])book[to[j]]=0;
    }
    tot=n*(n-1)*(n-2)/6-tot/2;
    printf("%lld %lld\n",ans,tot-ans);
    return 0;
}

T3 数 (aqnum)

题意很难理解吧。
其实可以转化为：
当一个数字 $i$质因数分解以后，每种因数的个数为奇数的时候，$i$为农数。
解法：搜索+优化
首先素数筛，筛出区间 [2,maxprime] 中的素数。
然后设 $dfs(i,j)$表示当前确定了 $i$为一个农数，当前搜索到了第 $j$个质数（因为我们只会找 $j$后面的质数）。
设 $p[i]$为第 $i$个质数。
因为 i 是个农数，所以 $i×p[j]$也是农数（因为 $p[j]$在之前没有被搜索过），$i×p[j]^3$也是，$i×p[j]$的 $(2×k+1)$次方都是。
所以我们就可以暴力搜索了。
然后我们需要优化。
1. 当 $i×p[j]$大于 upto，ans++，然后减掉。
2. 当 $j$大于 [1,maxprime] 中的质数个数时，ans++，然后减掉。
3. 当 $i×2×p[j]$大于 upto，但 $i×p[j]$小于等于 upto，直接二分找出满足条件的最大的 $j$设为 k，然后 $ans+=k-j+2$，然后减掉。

于是就能AC了。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,m,ans,p[1000005],psize;
bool book[1000005];
LL serch(LL k,LL l)
{
    LL r=psize-1,mid;
    while(mid=(l+r+1)>>1,l!=r)if(k*p[mid]<=n)l=mid;else r=mid-1;
    return l;
}
void dfs(LL k,LL x)
{
    if(x>=psize|k*p[x]>n){ans++;return;}
    if(k*p[x]*p[x]>n){ans+=serch(k,x)-x+2;return;}
    dfs(k,x+1),k*=p[x],dfs(k,x+1);
    while(k*=p[x]*p[x],k<=n)dfs(k,x+1);
}
int main()
{
    freopen("aqnum.in","r",stdin),freopen("aqnum.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    for(LL i=2;i<=m;i++)
        if(!book[i]){p[psize++]=i;for(LL j=(LL)i*i;j<=m;j+=i)book[j]=1;}
    dfs(1,0),printf("%lld\n",ans);
    return 0;
}