题解

1.Coin

大意：一个数列，两个人随机从两端取走数。求先手期望取走多少数。
60 分：考场上俺就是这么打的。如果用 f[i][j] 表示数列 [i…j] 先手期望取走的数。

f[i][j]=

(f[i+2][j]+w[i]

+f[i][j-2]+w[j]

+f[i+1][j-1]+w[i]

+f[i+1][j-1]+w[j])/4

O(n^2*T);
100 分: 考虑到对于出现的一定长度的数列，每个位置上的数被取到的概率是不变的。所以如果 f[i][j] 表示出现了长度为 i 的数列，第 j 个数被取到的概率。则：

f[i][j]=

(1-f[i-1][j]+

1-f[i-1][j-1])/2

(其中前者表示取走最后一个数，后者表示取走前一个数。)
这样就可以 O(n^2+n*T);

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

2.Triangle

大意：求一个图中三元环的个数及不图中三元环的个数。
30 分：枚举每个点暴力判边。
72 分：前 30 分用 30 分做法，后 42 分只输出原图三元环个数，用后文的 O(M) 算法。
100 分：令图中有的边为黑边，没有边为白边。则要求的是全为白边和全为黑边的三元环的个数。令 B 表示全黑三角形，W 为全白三角形，A 表示彩色三角形。则

B+W+A=N(N-1)(N-2)/6

其中 A 可以用 O(N) 求出：设 black[i] 表示与 i 点相连的点数，white[i] 表示与 i 点不相邻的点数，则 A=(Σ(black[i]*white[i]))/2 (i∈V).
由于白边数量较多，所以考虑求出 B 再推出 W。
如果枚举每个点 i, 设 book[j]=1((i,j)∈E)，再枚举每个点 j((i,j)∈E)，枚举每个点 w((j,w)∈E)，如果 book[w]==1，则 B 自加 1。由于这样求出的每个三角形被枚举了 6 次 (A(3,3)=3!)，所以

W=N(N-1)(N-2)/6 – (Σ(black[i]*white[i]))/2 – (Σi,j,k∈V 且 (i,j),(i,k),(j,k)∈E1)

这样均摊复杂度为 O(M).
至此，B,W 已经求出。

#include <bits/stdc++.h>
#define MX 100001
#define MD 4323333
using namespace std;
template<typename T>
void in(T &x){
    x = 0;char ch = getchar();
    while(ch >'9' || ch <'0') ch = getchar();
    while(ch<='9' && ch >='0') x = x*10+ch-'0',ch = getchar();
}

long long pbl[MX],pwt[MX],n,m;
long long fst[MX*2],nxt[MX*2],lnum=-1,u[MX*2],v[MX*2];
long long tot,have;

int book[MX];

inline void addeg(int nu,int nv)
{
    lnum++;
    u[lnum]=nu;
    v[lnum]=nv;
    nxt[lnum]=fst[nu];
    fst[nu]=lnum;
}

void work()
{
    long long yuan=0;
    for(register int i=1;i<=n;i++)
    {
        for(register int w=fst[i];w!=-1;w=nxt[w])book[v[w]]=i;
        for(register int w=fst[i];w!=-1;w=nxt[w])
            if(v[w]>i)
                for(register int p=fst[v[w]];p!=-1;p=nxt[p])
                    if(book[v[p]]==i&&v[p]>v[w])yuan++;
    }
    printf("%I64d %I64d\n",yuan,tot-have-yuan);
}

int main()
{
    memset(fst,0xff,sizeof(fst));
    freopen("triangle.in","r",stdin),freopen("triangle.out","w",stdout);
    in(n);in(m);
    for(long long i=1,a,b;i<=m;i++)
    {
        in(a);in(b);
        addeg(a,b),addeg(b,a);
        pbl[a]++,pbl[b]++;
    }
    for(int i=1;i<=n;i++)pwt[i]=n-1-pbl[i];
    tot=n*(n-1)*(n-2)/6;
    for(int i=1;i<=n;i++)have+=pbl[i]*pwt[i];
    have/=2;
    work();
    return 0;
}

3.Aqnum
大意：求 1 到 upto 中有几个数满足：每个质因数小于等于 maxprime 且每种质因数个数为奇数。
30 分：暴力搜索，用 f(x,k) 当前的数为 x, 在处理第 k 个质数，则：继续搜索 f(x,k+1), f(xp[k],k+1), f(xp[k]*p[k]2a,k+1). 复杂度约为∏(upto/p[k])

60 分：如果当前的 xp[k]<=upto 且 xp[k]2>upto, 则找到最后一个满足上述条件的 k2, ans+=k2-k+2; 大约可以剪枝 2k 以上的状态数。

#include <bits/stdc++.h>

#define MX 1000001

using namespace std;

long long prm[80000];
long long tab[MX];
long long mp,upto,pnum;

typedef long long ll;

void makep(ll top)
{
    ll now=2;
    pnum++;
    prm[pnum]=2;
    for(;;)
    {
        for(ll i=1;i*now<=top;i++)
        {
            tab[i*now]=1;
        }
        for(ll i=now;i<=top;i++)
        {
            if(tab[i]==0)
            {
                now=i;
                prm[++pnum]=i;
                break;
            }
            if(i==top)return ;
        }
    }
}

ll sch(ll l,ll k)
{
    ll r=pnum,mid;
    while(mid=(l+r+1)>>1,l!=r)if(k*prm[mid]<=upto)l=mid;else r=mid-1;
    return l;
}

ll ans;

void get(ll x,ll now)
{
    if(now>pnum||x*prm[now]>upto){ans++;return;}
    if(x*prm[now]*prm[now]>upto){ans+=sch(now,x)-now+2;return;}
    get(x,now+1);
    x*=prm[now];
    get(x,now+1);
    while(x*prm[now]*prm[now]<=upto)
    {
        x*=prm[now]*prm[now];
        get(x,now+1);
    }
}

int main()
{
    freopen("aqnum.in","r",stdin),freopen("aqnum.out","w",stdout);
    scanf("%I64d%I64d",&upto,&mp);
    makep(mp);
    get(1,1);
    cout<<ans<<endl;
    return 0;
}