hgoi#20190821

muronglin
muronglin 2019年08月21日
  • 在其它设备中阅读本文章

T2- 十七公斤重的文明

有一个集合 S,初始时为空,每一次操作,你可以选择 1 到 n 中的任意一个不在 S 中的元素 i,并将其加入 S,此时如果 i - 2 也在 S 中,则将 i - 2 从 S 中删除,如果 i + k 也在 S 中,则将 i + k 从 S 中删除。该操作可以进行任意多次。郝仁想知道总共有多少种不同的 S,对 998244353 取模 两个集合不同,当且仅当存在一个元素,在其中一个集合中出现,而在另一个集合中没有出现

解法

我们将 K 为奇数和偶数的情况分开讨论

偶数:

打个表,可以发现都有一个这样的规律
$f[k][k]=a[0]*a[0]$
$f[k+1][k]=a[0]*a[1]$
$f[k+2][k]=a[1]*a[1]$
$......$
$f[n][k]=a[(n-k)/2]*a[(n-k+1)/2]$
而 $f[x][x]=2^x$,所以 $a[0]=2^\frac{k}{2}$
又可以打表得出
当 $k=2$ 时,$a[i]=2*a[i-1]-a[i-3]$
当 $k=4$ 时,$a[i]=2*a[i-1]-a[i-4]$
$......$
当 $k=2*x$ 时
当 $i>0$ 时,$a[i]=2*a[i-1]-a[i-2-x]$
当 $i<0$ 时,$a[i]=max(2^{x+i},1)$
然后偶数就愉快的解决了

奇数:

我们将 1~n 的奇数和偶数分成两列排好,将 i 和 i + k 对齐 样例 $n=6,k=3$
如 $ \ \ \ 2\ 1 \ 4\ 3 \ 6\ 5 $
我们保证,每次取点只增加点,不减少点
这样就只能从一个点开始,向下或向右取,而且不会重复
那什么时候不合法呢 我们从右边开始取,取了一个 $num$ 如果取到 $num+k$ 就不合法
往下走一次是 $+2$,往左走一次是 $-k$
设 x 为向下走的次数 如果 $num+2x-k=num+k$ 就不合法 所以 $x < k$ 所以最多走过 k 条边,走过 k + 1 个点 如果走到了 k + 2 个点,一定不合法
设 $dp[i][j][k]$ 表示考虑到第 i 层, 右边的点往上走的最长距离为 j, 左边的点只拐一次的最大距离为 k 的方案数 那么转移分四种情况讨论
左右都不选: $dp[i+1][0][0]=dp[i][j][k]$
左选右不选: $dp[i+1][0][k?k+1:0]=dp[i][j][k]$
如果上一层 k 为 0,表示上一层没点或没拐过,k 不会增加 右选左不选: $dp[i+1][j+1][0]=dp[i][j][k]$
左右都选: $dp[i+1][j+1][max(k+1,j+2)]=dp[i][j][k]$
因为 k 表示最大长度,左右都选的时候,k 的长度可以从上面或者右边转移过来 最后的答案就是最后一层的合法方案总数

ac 代码

#include<bits/stdc++.h>
#define mod 998244353
#define N 310 
using namespace std;
int p(int a,int b)
{
    int sum=1;
    while(b)
    {
        if(b&1)sum=1llsuma%mod;
        a=1llaa%mod,b/=2;
    }
    return sum;
}
int n,m,ans,a[N],fN[N];
int get_a(int x)
{
    if(x>=0)return a[x];
    if(-x<m)return p(2,m+x);
    return 1;
}
int main()
{
    freopen("seventeen.in","r",stdin);
    freopen("seventeen.out","w",stdout);
    scanf("%d%d",&n,&m);
    if(m&1)
    {
        f0[0]=1;
        int s=(m>>1)+((n+1)>>1),p=(n>>1),q=m+1,g=(m>>1);
        for(int i=0;i<s;i++)for(int j=0;j<=p;j++)for(int k=0;k<=q;k++)
        {
            (fi+1[0]+=fi[k])%=mod;//都不选 
            if(i<p)(fi+1[0]+=fi[k])%=mod;//右选左不选 
            if(i>=g)(fi+1[k?k+1:0]+=fi[k])%=mod;//左选右不选 
            if(i<p&&i>=g)(fi+1[max(j+2,k+1)]+=fi[k])%=mod;//左右都选 
        }
        for(int j=0;j<=p;j++)for(int k=0;k<=q;k++)
            (ans+=fs[k])%=mod;
        printf("%dn",ans);
    }
    else
    {
        n-=m,m/=2,a[0]=p(2,m);
        int x=n/2,y=n-x;
        for(int i=1;i<=y;i++)
            a[i]=((2*a[i-1]-get_a(i-2-m))%mod+mod)%mod;
        printf("%dn",1lla[x]a[y]%mod);
    }
    return 0;
}