UNIQUE VISION Programming Contest 2025 Autumn (AtCoder Beginner Contest 425)

E - Count Sequences 2

不能线性求逆元，模数不一定是素数
用C（n,m) = C(n-1,m-1)+C(n-1,m)预处理组合数

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define pii pair<int,int>
#define ll long long
#define pb push_back
#define ft first
#define se second
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f

// #define int long long

int p;
int c[300010];
int C[5010][5010];

void solve(){
    int n; cin >> n; int s = 0;
	for(int i = 1; i <= n; i ++){
		cin >> c[i]; s += c[i];
	} 


	int cur = s; int ans = 1;
	for(int i = 1; i <= n; i ++){
	ans = 1ll*ans * C[cur][c[i]] % p;
	cur -= c[i];
	}
	cout << ans << '\n';

}

signed main(){
    std::ios::sync_with_stdio(false);
	int T = 1; cin >> T >> p;
	C[0][0] = 1;
	for(int i = 1; i <= 5000; i ++){
		for(int j = 0; j <= i; j ++){
			if(j == 0 || j == i) {
				C[i][j] = 1;
				continue;
			}
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1])%p;
		}
	}
    
    while(T--){
        solve();
    }
}

F - Inserting Process

n20左右状压
最后加进去的一位是什么，只有相邻相同位置会算重复

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define pii pair<int,int>
#define ll long long
#define pb push_back
#define ft first
#define se second
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f

// #define int long long

const int p = 998244353;
int f[(1<<22) + 10];
void solve(){
    int n; cin >> n;
    string s; cin >> s;

    f[0] = 1;
    for(int i = 1; i < (1ll << n); i ++) {
        char lst = ' ';
        for(int j = 0; j < n; j ++){
            if(i >> j & 1){
                 if(lst == s[j]) continue;
            lst = s[j];
            f[i] = (f[i] + f[i ^ (1ll << j)]) % p;
            }
        }
    }
    cout << f[(1ll << n) - 1] << '\n';
    
}

signed main(){
    std::ios::sync_with_stdio(false);
    int T = 1; //cin >> T;
    while(T--){
        solve();
    }
}