【题解】牛客寒假集训营6 BEF

别的题没什么好说的，H正解的线段树我不会，用暴力卡过去了（数据不强）
主要说下BEF三题吧：

B

正解的思路是把 $(x^2+x+1)^n$ 转化为 $(x^2-2x+1)^n=(x-1)^{2n}$
我没想到这个方法，而是用打表找规律来做的：
图片说明
可以发现，当n=4、13、40。。。的时候，全部都是1。而 $4=1+3,13=1+3+9,40=1+3+9+27...$
所以首先根据 $n$ 所在那一块进行分类，然后再根据更细的分类进行讨论。这里就不写细节了，毕竟推了快2小时。。
给大家介绍一下我找规律和debug的技巧。首先一定要写一个对拍函数，以及一个check函数，这样可以快速得出自己算出来的对不对。然后是不要一口气全写完，可以写一部分对拍一次，查看这一部分写的对不对，这样debug起来不容易出错。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[1000][1000],b[1000][1000];
ll kk;
ll f(ll n,ll m){
   // cout<<n<<" "<<m<<endl;
    if(m>2*n)return 0;
    if(n<=kk)return a[n][m];
    ll p=1,sum=0;
    while(sum<n)sum+=p,p*=3;

    p/=3;
    ll l=sum-p,r=sum,mid=l+r+1>>1;
    ll dis=n-l;
    if(n==l&&n==r)return 1;
 //   cout<<n<<" "<<m<<" "<<dis<<endl;
    if(n>=mid&&n<=r)return f(n-p,m%p);
    else{
    //    cout<<p<<endl;

        if(m<=p-1&&m>=dis*2)return 0;
        if(m>n)return f(n,2*n-m);
        if(m>=dis)return (3-f(n,2*dis-1-m))%3;
        ll mid2=l+p/3;
      //  cout<<mid2<<endl;
        if(n>mid2)return f(n-p/3*2,m%(p/3));
       // if(n==mid2)return 1;
        ll mid3=l+(p/3-(sum-p-p/3));
       // cout<<mid2<<endl;
        if(n>mid3)return f(n-p/3,m);
        else{


     //   cout<<n<<" "<<m<<" "<<2*dis<<endl;
            if(m>=2*dis)return 0;

            return f(n-p/3,m);
        }
    }
}
int main(){
    ll n,i,j,m,_=1;
  //  cin>>_;
    a[0][0]=1;
    a[1][0]=a[1][1]=a[1][2]=1;
    for(i=2;i<300;i++){
        for(j=0;j<500;j++){
            a[i][j]+=a[i-1][j];
            a[i][j+1]+=a[i-1][j];
            a[i][j+2]+=a[i-1][j];
        }
        for(j=0;j<500;j++)a[i][j]%=3;
    }
  //  cout<<f(22,9)<<endl;
  kk=13;
    for(i=0;i<40;i++){
    //    cout<<i<<": ";
        for(j=0;j<2*i+2;j++){
      //      b[i][j]=f(i,j);
   //         cout<<f(i,j)<<" ";
        }
  //      cout<<endl;
    }
    kk=40;
    for(i=0;i<40;i++){
        for(j=0;j<2*i+2;j++){
   //         if(b[i][j]!=f(i,j)){cout<<i<<" "<<j<<" "<<-1;return 0;}
        }
    }
    int t;
    cin>>t;
    while(t--){

        cin>>n>>m;
        cout<<f(n,m)<<endl;
    }


}

E

我们先观察第一行。
第一行第一个只能选择右和下。第一行最后一个只能选择左和下。其他的可以选择左/右和下。
那么很明显，这一行带来的权值最大的贡献（不考虑和下面的）可以用dp来解决，对应每个数选择向左/向右为 $dp[i][0]$ 和 $dp[i][1]$ ，就很容易解决了。
其他的行同理，列也同理。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[1010][2],a[1010][1010];
int gao(int x,int y){
    int p=x^y;
    int i=p,cnt=0;
    while(i)cnt+=i%2,i/=2;
    return p+cnt;
}
int main(){
    ll n,i,j=0,k,z=0,sum=0,cnt=0;
    ll m;
    cin>>n>>m;
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            cin>>a[i][j];
        }
    }
    ll ans=0;
    for(i=0;i<n;i++){
        for(j=0;j<m;j++)dp[j][0]=dp[j][1]=0;
        dp[1][1]=gao(a[i][0],a[i][1]);
        for(j=2;j<m;j++){
            dp[j][0]=max(dp[j-1][0],dp[j-1][1]);
            dp[j][1]=max(dp[j-2][0],dp[j-2][1])+gao(a[i][j],a[i][j-1]);
        }
      //  cout<<max(dp[m-1][0],dp[m-1][1])<<endl;
        ans+=max(dp[m-1][0],dp[m-1][1]);
    }
    for(j=0;j<m;j++){
        for(i=0;i<n;i++)dp[i][0]=dp[i][1]=0;
        dp[1][1]=gao(a[0][j],a[1][j]);
        for(i=2;i<n;i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
            dp[i][1]=max(dp[i-2][0],dp[i-2][1])+gao(a[i][j],a[i-1][j]);
          //  cout<<i<<" "<<j<<" "<<dp[i][0]<<" "<<dp[i][1]<<endl;
        }
    //    cout<<max(dp[n-1][0],dp[n-1][1])<<endl;
        ans+=max(dp[n-1][0],dp[n-1][1]);
    }
    cout<<ans;
}

F

这道题有很多人是OEIS过的，我说一下我的推导过程。
首先要明确两个公式：

$C^m_n=C^{m-1}_{n-1}+C^m_{n-1}$
$C^0_n+C^2_n+...+C^n_n=2^{n-1}$ （这个公式可以用上一个公式推出）
然后推导的时候为了方便，可以拿具体的数为例子（本题用12进行推导）。
设 $f(x)=C^0_x+C^4_x+...+C^x_x$
那么有：

$f(12)$
$=C^0_{12}+C^4_{12}+C^8_{12}+C^{12}_{12}$
$=1+C^3_{11}+C^4_{11}+C^7_{11}+C^8_{11}+1$
$=1+C^2_{10}+2*C^3_{10}+C^4_{10}+C^6_{10}+2*C^7_{10}+C^8_{10}+1$
$=2^9+2*(C^3_{10}+C^7_{10})$
$=2^9+2*(C^2_9+C^3_9+C^6_9+C^7_9)$
$=2^9+2*(C^1_8+2*C^2_8+C^3_8+C^5_8+2*C^6_8+C^7_8)$
$=2^9+2^8+4*(C^2_8+C^6_8)$
$=2^9+2^8+4*(2^7-f(8))$
$=2^{10}+2^8-4*f(8)$
由于上述推导过程适用于任何正整数 $n$ 不仅仅是12，所以可以得出递推式：

$f(n)=2^{n-2}+2^{n-4}-4*f(n-4)$
用这个递推式继续化简：

$f(n)$

$=2^{n-2}+2^{n-4}-4*f(n-4)$ ………………①式

$=2^{n-2}+2^{n-4}-4*(2^{n-6}+2^{n-8}-4*f(n-8))$

$=2^{n-2}-2^{n-6}+16*f(n-8)$ ………………②式

$=2^{n-2}-2^{n-6}+16*(2^{n-10}+2^{n-12}-4*f(n-12))$

$=2^{n-2}+2^{n-8}-64*f(n-12)$ ………………③式

$=$ ……………………
其中，假设已知f(4)，那么可以用①式推出f(8)，②式推出f(12)。。。以此类推可以推出所有的f(n)了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
string s[1010];
ll dp[100010];
int mod=998244353;
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;


}
int main(){
    ll n,i,j,k,t,m,sum=0;
    //2^(n-2)-或+2*(n/2)+
    cin>>n;
    cout<<((power(2,n-2)+(n%8!=0?-1:1)*power(2,n/2)-(n%8!=0?-1:1)*power(2,n/2-1))%mod+mod)%mod;


}