【题解】 CF1027E Inverse Coloring

快来打我* 2022-01-12 03:21 147阅读 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;
    }

转载于:https://www.cnblogs.com/JCNL666/p/10688040.html