首页 > 其他分享 >AtCoder Regular Contest 160 D Mahjong

AtCoder Regular Contest 160 D Mahjong

时间:2023-05-16 11:44:18浏览次数:53  
标签:AtCoder typedef res ll long Regular 160 mod

洛谷传送门

AtCoder 传送门

搞笑题,我不会做,我更搞笑。

考虑逆序操作,即初始有一个全 \(0\) 序列,每次单点加 \(k\) 或者长为 \(k\) 区间加 \(1\)。考虑把一个操作集合唯一对应到一个最终序列,不难发现只要限制每个区间加 \(1\) 的次数 \(< k\) 即可。因为如果正序操作,加上了限制,每个点被每个区间加的次数能算出来。

于是题目变成了统计序列 \(b_{1 \sim 2n - k + 1}\) 个数,要求:

  • \(\sum\limits_{i=1}^{2n - k + 1} b_i = \frac{m}{k}\)
  • \(\forall i \in [1, n - k + 1], b_i < k\)

这是一个有上界的插板法,容斥,钦定 \(i\) 个元素不合法,其余任意,那我们得到:

\[ans = \sum\limits_{i=0}^{n-k+1} (-1)^i \binom{n-k+1}{i} \binom{\frac{m}{k}-ik+2n-k}{2n-k} \]

暴力计算组合数,时间复杂度 \(O(n^2 \log mod)\)。

code
// Problem: D - Mahjong
// Contest: AtCoder - AtCoder Regular Contest 160
// URL: https://atcoder.jp/contests/arc160/tasks/arc160_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;

const ll mod = 998244353;

inline ll qpow(ll b, ll p) {
	ll res = 1;
	while (p) {
		if (p & 1) {
			res = res * b % mod;
		}
		b = b * b % mod;
		p >>= 1;
	}
	return res;
}

ll n, m, K;

inline ll C(ll n, ll m) {
	if (n < m || n < 0 || m < 0) {
		return 0;
	}
	ll res = 1;
	for (ll i = n; i >= n - m + 1; --i) {
		res = res * (i % mod) % mod;
	}
	for (int i = 1; i <= m; ++i) {
		res = res * qpow(i, mod - 2) % mod;
	}
	return res;
}

void solve() {
	scanf("%lld%lld%lld", &n, &m, &K);
	if (m % K) {
		puts("0");
		return;
	}
	m /= K;
	ll ans = 0;
	for (int i = 0; i <= n - K + 1; ++i) {
		ans = (ans + ((i & 1) ? mod - 1 : 1) * C(n - K + 1, i) % mod * C(m - i * K + n * 2 - K, n * 2 - K) % mod) % mod;
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

标签:AtCoder,typedef,res,ll,long,Regular,160,mod
From: https://www.cnblogs.com/zltzlt-blog/p/17404473.html

相关文章

  • AtCoder Beginner Contest 301 F Anti-DDoS
    洛谷传送门AtCoder传送门考虑分类计数,讨论“没有DD”、“有DD无o”、“有DDo无S”三种情况。没有DD,枚举有几种大写字母出现过;剩下两种情况,考虑设\(f_{i,0/1}\)分别表示两种情况的方案数。\(f_{i,0}\)可以从\(f_{i-1,0}\)填大写字母转移,也可以枚举第一个出现两......
  • Atcoder Regular Contest 101
    F-RobotsandExits\(n\)个人,\(m\)个出口在一条数轴上,坐标是正整数。你每次可以让所有人向左或向右一步,人在某个出口上后就离开。求多少种操作的方案使得人全部走光。两个方案相同当且仅当存在至少一个人在两次操作序列进行完成后从不同的出口消失。对\(10^9+7\)取模。\(1......
  • AtCoder Beginner Contest 223 G Vertex Deletion
    洛谷传送门AtCoder传送门设\(f_{u,0/1}\)为\(u\)的子树,\(u\)是否在匹配内的最大匹配数。注意到对于一个匹配,在它深度较浅的点上才会被计入答案。转移大概是\(f_{u,0}\)取\(\sum\limits_{v\inson_u}\max(f_{v,0},f_{v,1})\),\(f_{u,1}\)要从儿子中选一个\(f_{v,0......
  • ARC160
    A逐位确定即可,不难计算方案数。时间复杂度\(\mathcal{O}(n^2)\)或\(\mathcal{O}(n)\)。B一眼但是很恶心的题。直接整除分块做做即可。时间复杂度\(\mathcal{O}(T\sqrtn)\)。C这场比赛最简单的题。按照值从小往大考虑。设\(f_{i,j}\)表示考虑到\(i\),\(<i\)的数......
  • leetcode 1604. 警告一小时内使用相同员工卡大于等于三次的人
    力扣公司的员工都使用员工卡来开办公室的门。每当一个员工使用一次他的员工卡,安保系统会记录下员工的名字和使用时间。如果一个员工在一小时时间内使用员工卡的次数大于等于三次,这个系统会自动发布一个警告 。给你字符串数组 keyName 和 keyTime,其中 [keyName[i],keyTime[i......
  • AtCoder Beginner Contest 301
    title:AtCoderBeginnerContest301categories:算法题解description:咕咕咕tags:-Atcoder-贪心-BFS-DPcover:/img/chino/vec/chino17.jpgkatex:truedate:2023-05-1322:47:31A-OverallWinner(abc301a)题目大意给定一个字符串表示高桥和青木......
  • AtCoder Regular Contest 129 C Multiple of 7
    洛谷传送门AtCoder传送门首先\(\text{7777...777}\)(\(x\)个\(7\))对能被\(7\)整除子串数量的贡献是\(\frac{x(x+1)}{2}\)。把\(n\)分解成若干\(x_i\)使得\(\sum\limits_{i=1}^m\frac{x_i(x_i+1)}{2}=n\),表示每段\(x_i\)个\(7\)。怎么把它们组合在一起呢?一个......
  • AtCoder Beginner Contest 163 F path pass i
    洛谷传送门AtCoder传送门感觉我的做法比较奇葩(容斥,总路径数减去只走点权为\(k\)的路径。设点权为\(k\)的点数为\(c_k\),点权不为\(k\)的点构成的每个连通块大小为\(s_i\),那么\(ans_k=\frac{n(n-1)}{2}-\sum\frac{s_i(s_i-1)}{2}+c_k\)。考虑快速计算\(\su......
  • AtCoder Beginner Contest 207 F Tree Patrolling
    洛谷传送门AtCoder传送门简单树形dp。设\(f_{u,i,p=0/1,q=0/1}\)为\(u\)的子树中被覆盖点数为\(i\),\(u\)有没有被覆盖,\(u\)有没有被选。转移树形背包合并即可,需要分类讨论。要注意如果\(u\)没被覆盖,\(v\)选了,或者\(u\)选了,\(v\)没被覆盖,被覆盖点数要\(+1\)。......
  • AtCoder Beginner Contest 177 F I hate Shortest Path Problem
    洛谷传送门AtCoder传送门设\(f_{i,j}\)为从第\(1\)行到\((i+1,j)\)的最短路。因为我们并不关心最后到达的是哪一个格子,于是强制\(f_{i,j}\)为必须从\((i,j)\)往下走一格到\((i+1,j)\)的最短路。有转移:\[f_{i,r+1}\getsf_{i-1,j}+r+2-j,j\in[l......