首页 > 其他分享 >AtCoder Beginner Contest 301 F Anti-DDoS

AtCoder Beginner Contest 301 F Anti-DDoS

时间:2023-05-16 10:46:28浏览次数:54  
标签:AtCoder typedef Beginner Contest ll 30 long maxn mod

洛谷传送门

AtCoder 传送门

考虑分类计数,讨论“没有 DD”、“有 DDo”、“有 DDoS”三种情况。

  • 没有 DD,枚举有几种大写字母出现过;
  • 剩下两种情况,考虑设 \(f_{i,0/1}\) 分别表示两种情况的方案数。\(f_{i,0}\) 可以从 \(f_{i-1,0}\) 填大写字母转移,也可以枚举第一个出现两次的字母;\(f_{i,1}\) 可以从 \(f_{i-1,0}\) 和 \(f_{i-1,1}\) 填小写字母转移。

时间复杂度 \(O(52^2n)\),精细实现可过。

code
// Problem: F - Anti-DDoS
// Contest: AtCoder - パナソニックグループプログラミングコンテスト2023(AtCoder Beginner Contest 301)
// URL: https://atcoder.jp/contests/abc301/tasks/abc301_f
// 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 int maxn = 300100;
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, fac[maxn], ifac[maxn], f[maxn][2], pw[maxn], c[maxn][30], g[maxn][30];
ll h1[30][30], h2[30][30];
bool vis[128];
char s[maxn];

inline ll C(ll n, ll m) {
	if (n < m || n < 0 || m < 0) {
		return 0;
	} else {
		return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
	}
}

void solve() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	fac[0] = 1;
	for (int i = 1; i <= n + 50; ++i) {
		fac[i] = fac[i - 1] * i % mod;
	}
	ifac[n + 50] = qpow(fac[n + 50], mod - 2);
	for (int i = n + 49; ~i; --i) {
		ifac[i] = ifac[i + 1] * (i + 1) % mod;
	}
	pw[0] = 1;
	for (int i = 1; i <= n; ++i) {
		pw[i] = pw[i - 1] * 26 % mod;
	}
	for (int i = 0; i <= n + 50; ++i) {
		for (int j = 0; j <= min(i, 26); ++j) {
			c[i][j] = C(i, j);
			g[i][j] = c[i][j] * pw[i - j] % mod;
		}
	}
	for (int i = 0; i <= 26; ++i) {
		for (int j = 0; j <= 26; ++j) {
			h1[i][j] = c[i][j] * fac[j] % mod;
			if (j) {
				h2[i][j] = c[i][j - 1] * fac[j - 1] % mod * j % mod;
			}
		}
	}
	bool flag = 0;
	int cnt = 0, d = 0, T = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < 52; ++j) {
			if (s[i] != '?') {
				if (isupper(s[i]) && s[i] != 'A' + j) {
					continue;
				} else if (islower(s[i]) && s[i] != 'a' + (j - 26)) {
					continue;
				}
			}
			if (j < 26 && !flag) {
				if (vis['A' + j]) {
					int t = 26 - d;
					for (int k = 0; k <= min(26, cnt); ++k) {
						f[i][0] = (f[i][0] + g[cnt][k] * h1[t][k]) % mod;
					}
				} else if (cnt) {
					int t = 25 - d;
					for (int k = 1; k <= min(26, cnt); ++k) {
						f[i][0] = (f[i][0] + g[cnt][k] * h2[t][k]) % mod;
					}
				}
			}
			if (j < 26) {
				f[i][0] = (f[i][0] + f[i - 1][0]) % mod;
			}
			if (j >= 26) {
				f[i][1] = (f[i][1] + f[i - 1][0] + f[i - 1][1]) % mod;
			}
		}
		if (isupper(s[i]) && vis[s[i]]) {
			flag = 1;
		}
		if (isupper(s[i])) {
			vis[s[i]] = 1;
			++d;
		}
		cnt += (s[i] == '?');
	}
	ll ans = (f[n][0] + f[n][1]) % mod;
	if (!flag) {
		int k = 26 - d;
		for (int i = 0; i <= min(k, cnt); ++i) {
			ans = (ans + C(cnt, i) * pw[cnt - i] % mod * C(k, i) % mod * fac[i] % mod) % mod;
		}
	}
	printf("%lld\n", ans);
}

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

标签:AtCoder,typedef,Beginner,Contest,ll,30,long,maxn,mod
From: https://www.cnblogs.com/zltzlt-blog/p/17404177.html

相关文章

  • 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......
  • SMU Spring 2023 Contest Round 3(2023年湘潭大学新生赛)
    ProblemA.签到啦从大到小排序,累加大于行李w时输出下标即可intans;voidsolve(){cin>>n>>m;intans=0;vector<int>a(n);for(inti=0;i<n;i++){cin>>a[i];}sort(a.begin(),a.end());reverse(a.begin......
  • SMU Spring 2023 Contest Round 1
    B.ContestPreparation#include<iostream>#include<cstdio>#include<algorithm>#include<string>#include<cstring>#include<vector>#include<queue>#include<set>#include<map>#defineinf0x3f......
  • SMU Spring 2023 Contest Round 2
    M.DifferentBilling#include<map>#include<set>#include<cmath>#include<queue>#include<cstdio>#include<vector>#include<climits>#include<cstring>#include<cstdlib>#include<......
  • 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......