题:https://codeforces.com/contest/1027/problem/E
题意:给定n*n的方格,可以染黑白,要求相邻俩行”完全“不同或完全相同,对于列也是一样。然后限制不能拥有k面积具有相同颜色的格子
分析:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int M=1e3+3; const int mod= 998244353; ll dp[M][M];///前i个存在最多连续j个相同的格子颜色 void init(){ dp[1][1]=1ll; dp[0][1]=1ll; for(int i=2;i<=500;i++){ dp[i][i]=dp[i-1][i-1]*2ll%mod;///因为[i][i]就相当于没限制 ,所以直接每个位置俩个选择 dp[0][i]=1ll; } for(int i=1;i<=500;i++){ for(int j=1;j<=i;j++){ dp[j][i]=dp[j][j];///不受限制的部分 } ///当前的j位置,可以选择与前一个位置相同,也可以选择与后一个相同 ///若选择不相同,那么就在这个位置的贡献加上前一个位置的dp值 ///若选择相同,那么就把这个位置和前一个位置看出一整体,然后重复上述动作; for(int j=i+1;j<=500;j++) dp[j][i]=(2ll*dp[j-1][i]%mod-dp[j-i-1][i]+mod)%mod; } } int main(){ init(); int n,k; cin>>n>>k; ll ans=0; for(int i=1;i<=n;i++){ ll temp=dp[n][i]-dp[n][i-1]; temp=temp*(dp[n][min((k-1)/i,n)])%mod; ans=(ans+temp)%mod; } ans*=2; cout<<ans%mod<<endl; return 0; }