ARC120F Wine Thief

Description

给定含有个元素的序列，现在要求选出含有个元素的子序列，满足相邻的元素不能同时选择。问所有可能的子序列的权值和。

。答案对取模。

Sol

神仙计数题。

考虑一个弱化版问题：序列排成一个环，即两端不能同时选。

环带来的性质在于：环是对称的，因此易于计算贡献。

设表示在长度为的环中选取个元素的方案数，为长度为的链中选取个元素的方案数。

对于，我们在这个点断环为链，考虑选或不选，得到转移。

对于，考虑经典插板模型，得到。

计算贡献时每个数都会被计算次，直接加乘即可。

再考虑加上同时选取头尾的贡献，显然同时选取头尾的贡献为，此时再统计区间的贡献即可。

时间复杂度。

Code

今日小寄巧：lambda函数无脑开 [&] 就完了否则会出现各种奇怪的RE。

#include<bits/stdc++.h>
#define int long long
using std::vector;
typedef vector<int> vi;
typedef long long ll;
const int Mod=998244353;
template<typename Tp=int>inline Tp read(){Tp x(0);int op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}

signed main(){
    int n=read(),K=read(),D=read();
    vi a(n+1),s(n+1);for(int i=1;i<=n;++i)s[i]=(s[i-1]+(a[i]=read()))%Mod;
    auto ksm=[&](int x,int y) -> int {
        int ans=1;
        for(;y;y>>=1,x=x*x%Mod)if(y&1)ans=ans*x%Mod;
        return ans;
    };
    vi fac(n+1),inv(n+1);
    fac[0]=fac[1]=1;
    for(int i=2;i<=n;++i)fac[i]=fac[i-1]*i%Mod;
    inv[n]=ksm(fac[n],Mod-2);
    for(int i=n-1;~i;--i)inv[i]=inv[i+1]*(i+1)%Mod;
    auto C=[&](int x,int y) -> int {return x>=0&&y>=0&&x>=y?fac[x]*inv[y]%Mod*inv[x-y]%Mod:0;};
    auto g=[&](int x,int y) -> int {return C(x-y+1,y);};
    auto solve=[&](auto solve,int l,int r,int x) -> int {
        if(!x||l>r)return 0;
        if(x==1)return (s[r]+Mod-s[l-1])%Mod;
        return ((g(r-l-2,x-1)*(s[r]+Mod-s[l-1])%Mod+g(r-l-3,x-2)*((a[l]+a[r])%Mod)%Mod)%Mod+solve(solve,l+2,r-2,x-2))%Mod;
    };printf("%lld\n",solve(solve,1,n,K));
    return 0;
}