题目一

简单模拟题

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define ebk emplace_back 
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
void solve()
{
	int n;
	cin>>n;
	vector<int> a(n+2);
	for(int i=0;i<=n;++i) cin>>a[i];
	for(int i=2;i<=n;++i)
	{
		cout<<(ll)a[i]*i*(i-1)<<' ';
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T=1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
}

题目二

滑动窗口扫描一遍即可

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define ebk emplace_back 
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;++i)
	{
	string s;
	cin>>s;
	int len=s.size();
	int maxn=0;
	int l=0,r=0;
	while(r<len)
	{
		if(s[r]=='1') r++;
		else 
		{
			r++;
			l=r;
		}
		maxn=max(r-l,maxn);
	}
	//cout<<maxn<<'\n';
	cout<<(maxn>=n?"Yes":"No")<<'\n';
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T=1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
}

题目三

首先特判筛掉不可能归0的情况，然后类似卡特兰数的方法图解，即用点（0，x）点走到(k，0）的方案数减去走到（k，-2）的方案数，组合数计算即可

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define ebk emplace_back 
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
const int p=998244353;
int quick_pow(ll a,int b) 
{
    ll ans=1;
    for(;b;b>>=1)
    {
     if(b&1) ans=ans*a%p;
     a=a*a%p;
    }
    return ans;
}
int inv(int x) 
{
    return quick_pow(x,p-2);
}
ll f(int a,int b)
{
	ll res=1;
	if(b==0) return 1;
	for(int i=a;i>=a-b+1;--i) res=res*i%p;
	for(int i=b;i;--i) res=res*inv(i)%p;

	return res;
}
void solve()
{
	int x,k;
	
	cin>>x>>k;
	//假设有t次自减小
	if(x>k||((x+k)&1)) cout<<'0'<<'\n';
	else 
	{
		int t=(x+k)>>1;

		cout<<(f(k,t)-f(k,t+1)+p)%p<<'\n';
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T=1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
}

题目四

先特判，然后利用生成函数推导出\(x^n\)的系数，因为多次求组合，故进行了一次预处理

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
const int p=998244353;
typedef long long ll;
ll fact[N],infact[N];
ll f(int a,int b)
{
	return fact[a]*infact[b]%p*infact[a-b]%p;
}
int quick_pow(ll a,int b) 
{
    ll ans=1;
    for(;b;b>>=1)
    {
     if(b&1) ans=ans*a%p;
     a=a*a%p;
    }
    return ans;
}
int inv(int x) 
{
    return quick_pow(x,p-2);
}
int main()
{
    int n,k,t;
    cin>>n>>k>>t;
    if((long long)k*t<n) {cout<<'0'<<'\n';return 0;}
    
    fact[0]=1,infact[0]=1;
    
    for(int i=1;i<N;++i)
    {
        fact[i]=fact[i-1]*i%p;
        infact[i]=infact[i-1]*inv(i)%p;
    }
    ll ans=0;   
    for(int i=0;i<=min(k,n/(t+1));++i)
    {
    	if(i&1)
    	ans+=(-f(k,i)*f(k+n-(t+1)*i-1,n-(t+1)*i)%p),ans%=p;
    	else 
    	ans+=f(k,i)*f(k+n-(t+1)*i-1,n-(t+1)*i)%p,ans%=p;
    }
    printf("%lld\n",(ans+p)%p);
    return 0;
}