P3937 Changing_牛客博客

对于出题人大大的证法表示太高深。

这里用高考范围内的知识给出更为简洁，严谨的证明。

为了方便起见，一下 $A{i,j}$ 中的 $j$ 按 $mod n$ 理解。

首先，我们要证的命题是 $:$

若对于任意的正整数 $t$ 及任意的自然数 $k$ ，

有 $A_{t,k}=A_{t-1,k}+A_{t-1,k+1}$ ，

则对任意的自然数 $t,k$ ，

$A_{t,k}=\sum_{i=0}^{t}C_t^iA_{0,k+i}$ .

现对 $t$ 用数学归纳法证明命题。

$1.$ 当 $t=0$ 时，显然 $A_{0,k}=\sum_{i=0}^{0}C_0^iA_{0,k+i}$ .

$2.$ 假设 $t=m$ 时命题成立，即对任意的自然数 $k$ ,

有 $A_{m,k}=\sum_{i=0}^{m}C_m^iA_{0,k+i}$ .

则当 $t=m+1$ 时，对任意的自然数 $k$ ,

有 $A_{m+1,k}=A_{m,k}+A_{m,k+1}$

$=\sum_{i=0}^{m}C_m^iA_{0,k+i}+\sum_{i=0}^{m}C_m^iA_{0,k+1+i}$

$=\sum_{i=0}^{m}C_m^iA_{0,k+i}+\sum_{i=1}^{m+1}C_m^{i-***_{0,k+i}$

$=C_m^0A_{0,k+0}+\sum_{i=1}^{m}C_m^iA_{0,k+i}+\sum_{i=1}^{m}C_m^{i-***_{0,k+i}+C_m^{m}A_{0,k+m+1}$

$=C_{m+1}^0A_{0,k+0}+\sum_{i=1}^{m}(C_m^i+C_m^{i-***_{0,k+i}+C_{m+1}^{m+***_{0,k+m+1}$

$=C_{m+1}^0A_{0,k+0}+\sum_{i=1}^{m}C_{m+1}^iA_{0,k+i}+C_{m+1}^{m+***_{0,k+m+1}$

$=\sum_{i=0}^{m+1}C_{m+1}^iA_{0,k+i}$
故命题对 $t=m+1$ 也成立。

综上命题得证。

#include<iostream>
#include<cstdio>
void read(int &s);
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
const int maxn=3000030;

int gt(int nn){
    int s=0;
    for(int i=2;i<=nn;i*=2)s+=nn/i;
    return s;
}
int n,t,k,Ans,a[maxn];
int main(){
    read(n);read(t);read(k);
    rep(i,1,n)read(a[i]);
    Ans=0;
    rep(i,0,t){
        int C;
        C=(gt(t)-gt(i)-gt(t-i))?0:1;
        Ans=(Ans+C*a[(k+i-1)%n+1])%2;
    }
    cout<<Ans;
    return 0;
}
void read(int &s){
    int k=1;s=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')k=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    s*=k;
}