AKSZ - 笔记
2024-07-05 09:55:41
发布于:广东
逆元:使得x * inv(x) % mod = 1 的数
当mod为质数时可以通过费马小定理和快速幂求:
如果a与p互质
则a^(p-1) % p = 1
它可以解决带除法的取模问题
DP 的优化
多重背包二进制分解:O(mlog(si))
模板:
int n, m;
int v[205];
int w[205];
int s[205];
vector<pair<int, int>> goods;
int dp[1005][505];
cin >> n >> m;
for (int i=1; i<=n; i++){
cin >> v[i] >> w[i] >> s[i];
int k=1;
while (s[i]){
int t=max(s[i], k);
goods.push_back({t*v[i], t*w[i]});
s[i] -= t;
k *= 2;
}
}
for (int i=1; i<=goods.size(); i++){
for (int j=1; j<=m; j++){
dp[i][j] = max(dp[i-1][j], dp[i-1][j-goods[i].second]+goods[i].first);
}
}
cout << dp[goods.size()][m] << end
单调队列优化:O(mn)
模板:
cin >> n >> m;
for (int i=1; i<=n; i++) cin >> v[i] >> w[i] >> s[i];
for (int i=1; i<=n; i++){
for (int j=0; j<v[i]; j++){
for (int k=j; k<=m; k+=v[i]){
while (!q.empty() && q.front()<k-v[i]*s[i]) q.pop_front();
dp[i][k] = dp[i-1][k];
if (!q.empty()) dp[i][k] = max(dp[i][k], dp[i-1][q.front()] + (k-q.front())/v[i] * w[i]);
while (!q.empty() && dp[i-1][q.back()]+(k-q.back())/v[i]*w[i] <= dp[i-1][k]) q.pop_back();
q.push_back(k);
}
}
}
cout << dp[n][m] << endl;
区间DP的四边形不等式优化
对于状态转移方程为f[i][j] = min(f[i][k] + f[k+1][j]) + w[i][j]的区间dp
且w[i][j]满足四边形不等式和区间单调性:
对于a<=b<=c<=d,
w[a][c]+w[b][d] < w[a][d]+w[b][c]
w[a][d] >= w[b][c]
则有:opt[i][j-1] <= opt[i][j] <= opt[i+1][j]
状态压缩dp的优化
子集枚举 SOSDP 2^n 模板
int n;
int dp[15][5000];
int a[5000];
for (int j=0; j<(1<<n); j++) dp[0][j] = a[j];
for (int i=1; i<=n; i++){
for (int j=0; j<(1<<n); j++){
if (j&(1<<i)){
dp[i][j] = dp[i-1][j] + dp[i-1][j^(1<<i)];
} else dp[i][j] = dp[i-1][j];
}
}
括号序列模板
#include <iostream>
using namespace std;
const int mod=1e9+7;
int n, k;
char s[505];
int prefs[505];
int rmax[505];
long long tmprefs[505];
long long f[505][505];
long long g[505][505];
bool chk(char a, char b){
return ((a=='(' || a=='?') && (b==')' || b=='?'));
}
bool isS(int l, int r){
if (prefs[r] - prefs[l-1] == r-l+1){
if (r-l+1<=k) return true;
} return false;
}
int main(){
cin >> n >> k;
for (int i=1; i<=n; i++) {
cin >> s[i];
prefs[i] = prefs[i-1];
if (s[i] == '*' || s[i] == '?'){
prefs[i]++;
}
}
int lst=-1;
for (int i=n; i>=1; i--){
if (s[i] == '*' || s[i] == '?') {
lst=max(min(lst, i+k-1), i);
rmax[i] = lst;
} else {
lst=-1;
rmax[i] = i-1;
}
}
for (int len=2; len<=n; len++){
for (int l=1; l+len-1<=n; l++){
int r=l+len-1;
if (chk(s[l], s[r])){
if (r-l == 1) f[l][r] = 1; // ()
else if (isS(l+1, r-1)) f[l][r]++; // (S)
f[l][r] += f[l+1][r-1] + g[l+1][r-1]; // (A)
f[l][r] %= mod;
for (int al=l+2; al<=r-1; al++){ // (SA)
if (!isS(l+1, al-1)) break;
f[l][r] += f[al][r-1] + g[al][r-1];
f[l][r] %= mod;
} for (int ar=r-2; ar>=l+1; ar--){ // (AS)
if (!isS(ar+1, r-1)) break;
f[l][r] += f[l+1][ar] + g[l+1][ar];
f[l][r] %= mod;
}
tmprefs[l+1] = 0;
for (int i=l+2; i<=r; i++){
tmprefs[i] = tmprefs[i-1] + f[i][r] + g[i][r];
tmprefs[i] %= mod;
}
for (int ar=l; ar<=r-1; ar++){
g[l][r] += f[l][ar]*g[ar+1][r]%mod + f[l][ar]*f[ar+1][r]%mod; // AB
g[l][r] %= mod;
// bl : ar+2 -> rmax[ar+1]+1
g[l][r] += f[l][ar]*(tmprefs[min(rmax[ar+1]+1, r)] - tmprefs[ar+1])%mod;
g[l][r] += mod; g[l][r] %= mod;
// ASB
}
}
}
}
cout << (f[1][n] + g[1][n])%mod;
}
数位DP记忆化搜索模板
typedef long long ll;
int cnt, k;
int digits[15];
ll dp[15][15][5][5];
void init(ll x){
cnt=0;
while (x){
digits[++cnt] = x%10;
x /= 10;
}
}
ll dfs(int len, int sum, int up, int zero){
if (len==0) return sum;
ll *it = &dp[len][sum][up][zero];
if (*it == -1){
*it = 0;
for (int i=0; i<=9; i++){
if (up && i>digits[len]) break;
*it += dfs(len-1,
sum+(i==k && (k!=0 || !zero)),
up&&(i==digits[len]),
zero&&(!i));
}
} return *it;
}
这里空空如也
有帮助,赞一个