2016 沈阳网络赛

    这场感觉挺难的….没出几题…

1003

    数学推公式。我们可以先假设有一个人已经入座了，然后考虑剩下m-1个人，可以看到剩下的人只有\(n-mk-1\)个位置可以坐，所以这个组合数就是 \[ C_{n-mk-1}^{m-1} \]

    因为可以旋转，所以第一个人有n个位置可以坐，在这n个位置中有m个是会和其他的人坐重的，所以最后的式子就是 \[ \frac{n·C_{n-mk-1}^{m-1}}{m} \]

    很美妙的式子~

1004

    数论题，可以看到重点是求\( g(n) \)。

    这里我的方法是构造2个函数，其中 \[ \mu(x)=f^2(x) \] \[ h(x)=f(n)f(n-1) \]

    这里用题目中的递推式代换下，然后用\( \mu(n)-\mu(n-1) \)就行了，可以得到 \[ g(x)=5g(x-1)+5g(x-2)-g(x-3) \]

    于是可以矩阵快速幂，有了这个之后大概推出在\(10^8\)之前的项，然后其他的项用欧拉降幂去算就行了。

    这题数论感觉不算很难。

1007

    这个题的题解我已经贴了，我的做法是直接从高位向低位搜，不过好像写复杂了，挺多人100行多一点就解决了…

1009

    典型的区间DP，用f[i][j]表示i到j的最优解，需要判断某一段是否会被取完，如果取完的话f[i][j]直接取i到j的和，这个可以和前缀和一起预处理，处理之后直接DP就行了。

1010

    这个题直接炸了….听不少人都说这个题直接暴力打表打出来的（什么直接打表3小时….）听上去很可怕，反正这题考试的时候我是挂了，感觉是个什么神奇的筛法。最后考后竟然是道模板题…

    这里贴个地址：Meisell-Lehmer计算π(x)—in Wiki

    这个简直碉堡了…感觉自己从没学过数论…网上还有大牛的代码20多行解决….

    这里贴一下：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll f[340000],g[340000],n;
void init(){
    ll i,j,m;
    for(m=1;m*m<=n;++m)f[m]=n/m-1;
    for(i=1;i<=m;++i)g[i]=i-1;
    for(i=2;i<=m;++i){
        if(g[i]==g[i-1])continue;
        for(j=1;j<=min(m-1,n/i/i);++j){
            if(i*j<m)f[j]-=f[i*j]-g[i-1];
            else f[j]-=g[n/i/j]-g[i-1];
        }
        for(j=m;j>=i*i;--j)g[j]-=g[j/i]-g[i-1];
    }
}
int main(){
    while(scanf("%I64d",&n)!=EOF){
        init();
        cout<<f[1]<<endl;
    }
    return 0;
}

    很强势。