【CF1027E】Inverse Coloring(DP)
2024-08-28 01:55:26
题意:给出一个n*n的矩阵,要求在每个位置涂上黑/白色,
要求满足:任意相邻的两行,其颜色要么完全相同,要么完全相反
任意相邻的两列,其颜色也要么相同要么完全相反
且这个矩形中,不存在任意一个大小大于等于k的同色矩形
求方案数模998244353
n<=5e2,1<=k<=n^2
思路:From https://blog.csdn.net/qq_34454069/article/details/81835687
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef vector<int> VI;
#define fi first
#define se second
#define MP make_pair
#define N 510
#define M 51
#define MOD 998244353
#define eps 1e-8
#define pi acos(-1)
#define oo 1e9 int dp[N][N],f[N]; void add(int &x,int y)
{
x=(ll)x+y;
if(x>=MOD) x-=MOD;
} int main()
{
int n,K;
scanf("%d%d",&n,&K);
for(int i=;i<=n;i++)
{
dp[][i]=;
for(int j=;j<=n;j++)
for(int k=;k<=min(i,j);k++) add(dp[j][i],dp[j-k][i]);
}
for(int i=;i<=n;i++) f[i]=(dp[n][i]-dp[n][i-]+MOD)%MOD;
int ans=;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(i*j<K) add(ans,(ll)f[i]*f[j]%MOD);
ans=ans*%MOD;
printf("%d\n",ans);
return ;
}
最新文章
- JAVA发展史
- 【海洋女神原创】How to: Installshield做安装包时如何添加文件
- sqlite query用法
- Linux用户名显示-bash-4.1$快速排查
- 1. while循环(当循环) 2. do{}while()循环 3. switch cose(多选一) 例子:当选循环下求百鸡百钱 用 switch cose人机剪刀石头布
- java jdbc 封装。。
- JavaEE是什么?
- <;s:form action=";login";...与<;s:form action = ";login.action";.的区别
- 学习PHP时的一些总结(二)
- spoj 2319 BIGSEQ - Sequence
- Windows 注册表操作
- [stack]Evaluate Reverse Polish Notation
- 图片上传webuploader
- poj 1564 Sum It Up | zoj 1711 | hdu 1548 (dfs + 剪枝 or 判重)
- Python中的各种装饰器详解
- kafka集群搭建(windows环境下)
- MySQL/MariaDB触发器
- SpringCloud-分布式链路跟踪配置详解
- java集合(1)
- 飞旋treap