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 longint 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 longconst 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();}
}