慕容琳的后花园
慕容琳的后花园
hgoi#20190821

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]
\dots \dots
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]
\dots \dots
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+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=1ll*sum*a%mod;
        a=1ll*a*a%mod,b/=2;
    }
    return sum;
}
int n,m,ans,a[N],f[N][N][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)
    {
        f[0][0][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++)
        {
            (f[i+1][0][0]+=f[i][j][k])%=mod;//都不选 
            if(i<p)(f[i+1][j+1][0]+=f[i][j][k])%=mod;//右选左不选 
            if(i>=g)(f[i+1][0][k?k+1:0]+=f[i][j][k])%=mod;//左选右不选 
            if(i<p&&i>=g)(f[i+1][j+1][max(j+2,k+1)]+=f[i][j][k])%=mod;//左右都选 
        }
        for(int j=0;j<=p;j++)for(int k=0;k<=q;k++)
            (ans+=f[s][j][k])%=mod;
        printf("%d\n",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("%d\n",1ll*a[x]*a[y]%mod);
    }
    return 0;
}
赞赏
https://secure.gravatar.com/avatar/8cbc0c58deea66b18e9a96cd4bdd6eea?s=256&d=monsterid&r=g

慕容琳

文章作者

发表评论

textsms
account_circle
email

慕容琳的后花园

hgoi#20190821
T2-十七公斤重的文明 有一个集合S,初始时为空,每一次操作,你可以选择1到n中的任意一个不在S中的元素i,并将其加入S,此时如果i-2也在S中,则将i-2从S中删除,如果i+k也在S中,则将i+k…
扫描二维码继续阅读
2019-08-21
功能