AtCoder Beginner Contest 280

A - Pawn on a Grid

Problem Statement

题意：给你\(N\)行\(M\)列的网格，问你有多少个#

Solution

思路：直接记录个数就行。

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int cnt = 0;
	int n,m;
	cin>>n>>m;
	for(int i =1;i<=n;i++)
		for(int j = 1;j<=m;j++)
		{
			char x;
			cin>>x,cnt += (x=='#');
		}
	cout<<cnt<<endl;
	return 0;
}

B - Inverse Prefix Sum

Problem Statement

题意:给你一个前缀和数组让你求原数组

Solution

思路：差分

#include<bits/stdc++.h>
using namespace std;
const int N = 10;
long long a[N],b[N],n;
int main()
{
	int n;
	cin>>n;
	for(int i = 1;i<=n;i++)
		cin>>a[i];
	for(int i = 1;i<=n;i++)
		b[i] = a[i]-a[i-1];
	for(int i = 1;i<=n;i++)
		cout<<b[i]<<" ";
	cout<<endl;
	return 0;
}

C - Extra Character

Problem Statement

题意:给你两个字符串\(S\)和\(T\),问你在\(S\)哪个位置插一个字母和\(T\)一样

Solution

思路：for一遍看那个位置不一样，如果前\(len_s\)个都一样，那就插在最后

#include<bits/stdc++.h>
using namespace std;

int main()
{
	string s,t;
	cin>>s>>t;
	int m = t.size();
	s = "?"+s,t = "?"+t;
	bool ok = true;
	int pos = -1;
	for(int i = 1;i<=m;i++)
	{
		if(s[i]!=t[i])
		{
			ok = false;
			pos = i;
			break;
		}
	}
	if(ok)cout<<m<<endl;
	else cout<<pos<<endl;
	return 0;
}

D - Factorial and Multiple

Problem Statement

题意：给你一个大于等于2的整数\(K\),让你找到最大的正整数\(N\)满足\(k|N!\)

Solution

思路：

由唯一分解定理可知，一个数\(n\)可以写成素数幂的乘积。

比如\(n = p_1^{e_1}p_2^{e_2}...p_k^{e_k}\)

因为\(N!\)能被\(K\)整除，说明每一项\(p_i\)的素数幂次至少有\(e_i\)个

比如：\(280 = 2^3\times 5^1 \times 7^1\)

也就是说要能整除\(280\),至少有\(3\)个\(2\)，\(1\)个\(5\)和\(1\)个\(7\)

那么我们对每个素因子\(p_i\)判断，满足至少含\(e_i\)个的\(p_i\)的阶乘是几。

比如还是以\(280\)为例：

对于第一个素因子 \(p = 2\)，我们分解质因数之后知道它至少要\(3\)个,\(cnt = 3\)

int p = 2,tmp = 0;
while(cnt>0)
{
    tmp += p;
    ll x = tmp;
    while(x%p==0)x/=p,cnt--;
}

什么意思呢？

一开始\(tmp = 2\)，那我们看\(2!\)有几个\(2\),我们发现有一个，那现在\(cnt\)变为\(2\),我们还需要\(2\)个\(2\)，那我们继续加，\(tmp += 2\)，那我们发现\(4!\)有\(2\)个\(2\)，那满足了，那对于\(p = 2\)而言，答案至少是\(4!\)。

答案为什么直接就是对\(tmp\)取\(max\)呢？

因为在我们算\(4!\)之前先算了\(2!\)对吧，而\(4 = 4\times3\times2\times1\), \(2 = 2\times 1\)

很显然\(4\)的阶乘包含\(2\)的阶乘，同理大的阶乘含素数个数包含了小的，也就是说，我们算\(4!\)的贡献的时候，只需要算出\(4\)本身的贡献加上前面的\(2\)的贡献即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	ll k;
	cin>>k;
	ll cnt = 0;
	ll ans = 0;
	for(int i = 2;i<=k/i;i++)
	{
		cnt = 0;
		if(k%i==0)
			while(k%i==0)cnt++,k/=i;
		ll tmp = 0;
		while(cnt>0)
		{
			tmp += i;
			ll x = tmp;
			while(x%i==0)
			{
				x/=i;
				cnt--;
			}
		}
		ans = max(ans,tmp);
	}
	cout<<max(ans,k)<<endl;
	return 0;
}

E - Critical Hit

Problem Statement

题意：一个怪兽有\(N\)点耐力值。

一次攻击有\(\dfrac{P}{100}\)的概率使得怪兽的耐力值\(-2\),有\(1-\dfrac{P}{100}\)的概率\(-1\)

求使得怪兽耐力值减小到\(0\)以下的期望次数。用逆元，模数是\(998244353\)

Solution

思路：一个正常的概率\(dp\)

定义\(dp[i]\)为耐力值为\(i\)时候的期望次数，那显然\(dp[0] = 0,dp[1] = 1\)

因为除以\(100\)，我们可以先对\(100\)求个逆元\(inv\)

状态转移：\(dp[i] = dp[i-2]*P*inv+dp[i-1]*(100-p)*inv+1\)

记得取模不要炸了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
 const int mod = 998244353;
struct modular_arithmetic {
   
    int add(ll a, ll b) {
        return (a % mod + b % mod) % mod;
    }
    int mul(ll a, ll b) {
        return ((a % mod) * (b % mod)) % mod;
    }
    int pow(ll x, ll n) {
        if (n == 0) return 1;
        int res = pow(x, n / 2);
        res = mul(res, res);
        if (n % 2) res = mul(x, res);
        return res;
    }
    int inv(ll x) {
        return pow(x, mod - 2);
    }
    int div(ll a, ll b) {
        return mul(a, inv(b));
    }
};
modular_arithmetic Mod;
ll n,p;
ll dp[N];
int main()
{
    cin>>n>>p;
    ll inv = Mod.inv(100);
    dp[0] = 0 ,dp[1] = 1;
    for(int i = 2;i<=n;i++)
        dp[i] = (dp[i-2]*p%mod*inv%mod + dp[i-1]*(100-p+mod)%mod*inv%mod+1)%mod;
    cout<<dp[n]<<endl;
    return 0;
}