【题解】 CF1027E Inverse Coloring-蒲公英云

【题解】 CF1027E Inverse Coloring

快来打我* 2022-01-12 03:21 206阅读 0赞

\(Description:\)

You are given a square board, consisting of n n n rows and n n n columns. Each tile in it should be colored either white or black.

Let’s call some coloring beautiful if each pair of adjacent rows are either the same or different in every position. The same condition should be held for the columns as well.

Let’s call some coloring suitable if it is beautiful and there is no rectangle of the single color, consisting of at least k k k tiles.

Your task is to count the number of suitable colorings of the board of the given size.

Since the answer can be very large, print it modulo 998244353 998244353 998244353 .

(果然还是太懒了)

\(Sample\) \(Input\):

1 1

\(Sample\) \(Output\):

0

\(Solution\)

首先考虑怎么求把一段i涂成一种颜色的方案数：

设\(f[i][j]\)表示连续段长度\(<=i\),前j个的方案数

\(f[i][j]=\sum_{l=1}^{i}f[i][j-l]\)

然后这样预处理出第一列的情况数，在考虑后面每一列

连续长度为（K-1）/当前连续长度。

然后对横着做一遍连续长度小于连续长度的DP

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int n,K,now,sum,ans;
const int N=2000,p=998244353;
int f[N+5],s[N+5];
signed main(){
    if(fopen("fairy.in","r")){
        freopen("fairy.in","r",stdin);
        freopen("fairy.out","w",stdout);
    }
    scanf("%lld%lld",&n,&K);
    K--;
    for(int i=1;i<=min(K,n);++i){
        f[0]=1;sum=0;
        for(int j=1;j<=i;++j){
            f[j]=(f[j-1]*2)%p;
            sum=(sum+f[j])%p;
        }
        for(int j=i+1;j<=n;++j){
            f[j]=sum;
            sum=((sum-f[j-i])%p+p)%p;
            sum=(sum+f[j])%p;
        }
        s[i]=((f[n]-now)%p+p)%p;
        now=f[n];
    }
    for(int i=1;i<=min(K,n);++i){
        int limit=min(K/i,n);
        f[1]=s[i];sum=s[i];
        for(int j=2;j<=limit;++j){
            f[j]=(f[j-1]*2)%p;
            sum=(sum+f[j])%p;
        }
        for(int j=limit+1;j<=n;++j){
            f[j]=sum;
            sum=((sum-f[j-limit])%p+p)%p;
            sum=(sum+f[j])%p;
        }
        ans=(ans+f[n])%p;
    }
    printf("%lld\n",ans);
    return 0;
}