[AT2000] [agc002_f] Leftmost Ball
2024-08-30 09:07:23
题目链接
AtCoder:https://agc002.contest.atcoder.jp/tasks/agc002_f
洛谷:https://www.luogu.org/problemnew/show/AT2000
Solution
对于一个任意的颜色序列,它合法当且仅当任意一个前缀序列都要满足白色数量大于等于颜色种类数(不包括白色)。
设\(f[i][j]\)表示当前填了\(i\)个白球,\(j\)种其他颜色的球的方案数,显然当\(i<j\)时\(f[i][j]=0\)。
考虑转移,我们考虑每次都填最前面那个没填过的位置:
- 填白球不会有任何影响,直接转移就好了。
- 否则我们可以从剩下\(n-(j-1)\)种颜色种任选一种,一个填在第一个能填的位置,剩下的\(k-2\)个填在剩下\(n*k-i-(j-1)(k-1)-1\)个位置里。
转移式子就是:
\[f[i][j]=f[i-1][j]+f[i][j-1]\cdot (n-j+1)\cdot \binom{nk-i-(j-1)(k-1)-1}{k-2}
\]
\]
暴力转移就好了,初值\(f[0][0]=1\),时间复杂度\(O(n^2)\)。
#include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define ll long long
const int maxn = 2e3+10;
const int maxm = maxn*maxn;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
int add(int x,int y) {return x+y>mod?x+y-mod:x+y;}
int del(int x,int y) {return x-y<0?x-y+mod:x-y;}
int mul(int x,int y) {return 1ll*x*y-1ll*x*y/mod*mod;}
int n,k,f[maxn][maxn],fac[maxm],ifac[maxm],inv[maxm];
void prepare() {
inv[0]=inv[1]=fac[0]=ifac[0]=f[0][0]=1;
for(int i=2;i<maxm;i++) inv[i]=mul(mod-mod/i,inv[mod%i]);
for(int i=1;i<maxm;i++) fac[i]=mul(fac[i-1],i);
for(int i=1;i<maxm;i++) ifac[i]=mul(ifac[i-1],inv[i]);
}
int c(int nn,int mm) {return mul(fac[nn],mul(ifac[mm],ifac[nn-mm]));}
int main() {
read(n),read(k);prepare();if(k==1) puts("1"),exit(0);
for(int i=1;i<=n;i++)
for(int j=0;j<=i;j++)
f[i][j]=add(f[i-1][j],mul(f[i][j-1],mul(n-j+1,c(n*k-i-(k-1)*(j-1)-1,k-2))));
write(f[n][n]);
return 0;
}
最新文章
- Matlab与Windows桌面提醒
- 交叉验证(Cross Validation)原理小结
- 支持+-*/()int 型数据的计算机c++实现
- GitHub学习心得之 安装配置与多帐号管理
- C#复习(学生信息输入)
- R读取数据的错误
- 基于WDF的PCI/PCIe接口卡Windows驱动程序(1)-WDF概述及开发环境搭建
- IOS NSUserDefaults 讲解 用法
- Catalog Service - 解析微软微服务架构eShopOnContainers(三)
- 【剑指Offer学习】【面试题21:包括min 函数的栈】
- SQL INNER JOIN 关键字
- js jquery 遍历 for,while,each,map,grep
- Extmail 批量添加邮箱用户
- SSL 链接安全协议的enum
- Hive 系列(一)安装部署
- C# List集合基础操作
- Difference between HashMap and Hashtable | HashMap Vs Hashtable
- 程序员的福音,AI可以自动修复bug了!
- 数据结构-队列(3)-使用Java内置队列
- python的动态性和_slot_