2024ccpc网络赛

https://codeforces.com/gym/105336

L:

签到，队友写的

K:

签到，发现每次就是取二

B:

瞎猜过了,结论题

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mkp make_pair
#define int long long
const int maxn=2e5+10;
const int mod=998244353;
int a[maxn];
int A[maxn]; 
set<int>st;
map<int,int>mp;
signed main(){
	ios::sync_with_stdio(false);
	// 解除cin和cout的默认绑定，来降低IO的负担使效率提升
	cin.tie(NULL); cout.tie(NULL);
	A[0]=1;for(int i=1;i<=1001;i++)A[i]=A[i-1]*i%mod;
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];st.insert(a[i]);mp[a[i]]++;
	}
	if(n==1){
		cout<<0<<' '<<1<<"\n";
		return 0;
	}
	sort(a+1,a+n+1);
	
	int ans=0;
	for(int i=1;i<=n;i++){
		int mx=a[i],mn=a[i];
		for(int j=i+1;j<=n;j++){
			mx=max(a[j],mx);
			mn=min(a[j],mn);
			ans=(ans+mx-mn);
		}
	}
	cout<<ans<<" ";
	int x=1;
	if(st.size()>1)x=2;
	for(int i:st){
		x=(x*A[mp[i]]%mod);
	}
	cout<<x<<"\n";
} 

D:

正解是矩阵，但是区间dp完全就够了

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mkp make_pair
#define int long long
const int maxn=2e5+10;
const int mod=998244353;
int	f[105][105][105];
int kmp[105];
signed main(){
	ios::sync_with_stdio(false);
	// 解除cin和cout的默认绑定，来降低IO的负担使效率提升
	cin.tie(NULL); cout.tie(NULL);
	string s,t;cin>>s>>t;
	s='1'+s;t='1'+t;
	int lens=s.size()-1,lent=t.size()-1;
	for(int i=0;i<=lens;i++){
		for(int l=1;l<=lent+1;l++){
			for(int r=0;r<l;r++){
				f[i][l][r]=1;
			}
		}
	}
	for(int i=1;i<=lens;i++){
		for(int l=1;l<=lent;l++){
			for(int r=l;r<=lent;r++){
				for(int k=l-1;k<=r;k++){
					f[i][l][r]=(f[i][l][r]+f[i-1][l][k]*f[i-1][k+1][r]%mod)%mod;
				}
				for(int k=l-1;k<r;k++){
					if(s[i]==t[k+1]){
						f[i][l][r]=(f[i][l][r]+f[i-1][l][k]*f[i-1][k+2][r]%mod)%mod;
					}
				}
			}
		}
	}
	cout<<f[lens][1][lent]<<"\n";
} 

J: