2017.9.9 NOIP模拟赛

题解 套题

目录

• 2017.9.9 NOIP模拟赛
  • 1. 兔子序列
    • 思路
    • 代码
  • 2. 完整的海报
    • 思路
  • 3. 互质统计
    • 思路
    • 代码

1. 兔子序列

思路

• 其实很简单，其他大佬都想多了，完全不需要去发现每一次死的兔子数是该递推数列的第$i-m+2$项；
• 每次把新增加的兔子数加到一个队列里，然后每次队首就是死去的兔子数了，直接模拟。。。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    x=0;
    int pm=1; char c;
    do{c=getchar();}while(!isdigit(c) && c!='-');
    c=='-' ? pm=-1:x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <queue>
#include <algorithm>
using std::queue;
using std::min;
const int MAXN=100005,P=1e9+7;
inline int cal_ans(int n,int m){
    static int fib[MAXN];
    static queue<int> die;
    while(die.size()) die.pop();
    fib[0]=fib[1]=1;
    die.push(fib[0]);
    for(int i=2,lim=min(n,m);i<=lim;++i){
        fib[i]=(fib[i-1]+fib[i-2])%P;
        die.push(fib[i-2]);
    }
    for(int i=m+1;i<=n;++i){
        fib[i]=((fib[i-1]+fib[i-2])%P-die.front()+P)%P;
        die.pop();
        die.push(fib[i-2]);
    }
    return fib[n];
}
int main(){
    setIO("rabbit");
    int T;
    read(T);
    int n,m;
    while(T--){
        read(n),read(m);
        write(cal_ans(n,m),'\n');
    }
    return 0;
}

2. 完整的海报

思路

• 显然线段树区间合并，但是当时写完调不出来，就想到了一个不太好想但不容易写挂的方法（非旋转式Treap）；
• 其实，后来发现是我线段树节点记录的东西不妥导致的；
• 每个节点记录的海报都应该是完整的海报（修改时可能会暂时有记录不完整海报的节点，但是upd()后就不存在了）；
• 每个节点记录区间左右端所属的海报的编号以及其在该节点维护的区间的长度；
• 当然，还要记录被节点维护区间完整包含的海报数量，这样答案就是$cnt(rt)$了；
• 考虑修改，显然要打$tag$，之后upd()时注意分清楚情况，不重不漏地统计就好了；
• 具体细节看一下代码应该就能明白了。

3. 互质统计

思路

• 考虑最朴素的暴力写法，设$ans(i)$表示当$n=i$时的答

  for(int i=1;i<=n;++i){
      for(int j=1;j<i;++j)
          ans[i]+=(gcd(i-j,i+j)==1);
  }

• 很容易发现，$ans$具有前缀性质，即2从$ans(i-1)$到$ans(i)$转移时，第一层循环增加了一次，第二层循环增加了一次$1 \to i-1$的循环。所以我们考虑递推；
• 因为是统计互质的个数，所以肯定与[欧拉函数][3]有关，但是$i-j,i+j$都是变量，难以计算；
• 在说正解前，我们先看两个结论：
  
  1. 设$a>b$，则有$\gcd(a,b)=1 \iff\gcd(a,a-b)=1$，其否命题也成立。证明：
     
     • 考虑反证法，假设$\gcd(a,b)=1$且$\gcd(a,a-b)>1$；
     • 则设$a=mx,a-b=nx$，则$b=(m-n)x$；
     • 所以有$\gcd(a,b)>1$，与假设矛盾，命题成立。其否命题证明类似。
  2. $\gcd(a,b)=1$且$a \not\equiv b \pmod{2}\iff\gcd(2a,a+b)=1$，其否命题也成立。证明：
     
     • 仍然考虑反证法，假设$\gcd(a,b)=1,a \not\equiv b \pmod{2}$且$gcd(2a,a+b)>1$；
     • 因为$a \not\equiv b \pmod{2}$，所以$2a \not\equiv a+b \pmod{2}$，于是$2 \nmid\gcd(2a,a+b)$；
     • 所以$gcd(2a,a+b)\mid a$，那么设$\gcd(2a,a+b)=k$，则$k \mid b$；
     • 于是$\gcd(a,b)=k$与假设矛盾，故命题成立。其否命题证明同理。
• 因为$\gcd(i-j,i+j)$形式与以上结论相像，所以我们从$i-1 \to i$递推时分两种情况讨论：
  
  1. $i$为偶数：
     
     • 则$\forall x \in\{x \mid\gcd(x,i)=1,x\leq i \}$有$x \not\equiv i \pmod{2}$；
     • 那么根据结论2，有$\gcd(2x,x+i)=1$；
     • 又根据结论1可知，$\gcd(2x-(x+i),x+i)=\gcd(x-i,x+i)=1$；
     • 所以，此时$i$的贡献等于小于$i$且尤其互质的数的个数，即为$\varphi(i)$。
  2. $i$为奇数：
     
     • 此时，情况似乎复杂了一点，因为与$i$互质的数可能为奇数，也可能为偶数，而我们只求是偶数的个数；
     • 但是考虑对于一个奇数$i$，若一个小于$i$的奇数$x$与其互质，则$i-x$也一定与其互质，而$i-x$是偶数；
     • 那么，小于且与奇数$i$互质的数奇偶一一对应，故做贡献的数等于$\varphi(i)/2$。
• 综上，
  $ans(i)= \begin{cases} ans(i-1)+\varphi(i) &\quad 2 \mid i\\ ans(i-1)+\varphi(i)/2 &\quad 2 \nmid i \end{cases}$

代码

#include <cstdio>
const int MAXN=1e7+5;
int phi[MAXN];
long long ans[MAXN];
inline void Euler_phi(){
    static int prm[MAXN];
    static bool notP[MAXN];
    notP[1]=true,phi[1]=1;
    for(int i=2;i<MAXN;++i){
        if(!notP[i]){
            prm[++prm[0]]=i;
            phi[i]=i-1;
        }
        for(int j=1,tmp;j<=prm[0] && i*prm[j]<MAXN;++j){
            tmp=i*prm[j];
            notP[tmp]=true;
            if(i%prm[j]==0){
                phi[tmp]=prm[j]*phi[i];
                break;
            }
            else phi[tmp]=phi[i]*phi[prm[j]];
        }
    }
}
inline void pre_tab(){
    Euler_phi();
    for(int i=1;i<MAXN;++i){
        ans[i]=ans[i-1];
        ans[i]+= i&1 ? phi[i]>>1:phi[i];
    }
}
int main(){
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    pre_tab();
    int T;
    scanf("%d",&T);
    int n;
    while(T--){
        scanf("%d",&n);
        printf("%lld\n",ans[n]);
    }
    return 0;
}