2022-9-22总结

导出子图

题目给了一个限制： $|a_i-b_i| \le 12$ 。

这启发我们进行状压DP，具体来说可以维护选择了哪些联通块，然后进行一个 DP 的做就 OK 了。

#include <cstdio>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
 
typedef long long ll;
const int N = 55;
const int P = 998244353;
 
ll ans;
int n, m;
int g[N];
map<vector<int>, ll> f[2];
  
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y; cin >> x >> y;
        if(x < y) swap(x, y);
        g[x] |= (1<<(12-x+y));
    }
    f[0][vector<int>()] = 1;
    for(int i = 1; i <= n; i++)
    {
        f[i&1].clear();
        for(auto tmp : f[(i-1)&1])
        {
            auto now = tmp.first;
            auto val = tmp.second;
            bool flag = false;
            for(int j = 0; j < now.size(); j++)
                if(now[j] == 1) {flag = true; break;}
            if(flag and now.size() == 1) (ans += val) %= P;
            if(flag and !(g[i]&1)) continue;
            vector<int> to2;
            int np = 1<<11;
            for(int j = 0; j < now.size(); j++)
            {
                if(now[j]&g[i]) np |= (now[j]>>1);
                else to2.push_back(now[j]>>1);
            }
            to2.push_back(np);
            (f[i&1][to2] += val) %= P;
            if(flag) continue;
            auto to1 = now;
            for(int j = 0; j < to1.size(); j++)
                to1[j] >>= 1;
            (f[i&1][to1] += val) %= P;
        }
    }
    for(auto i : f[n&1])
        if(i.first.size() == 1)
            (ans += i.second) %= P;
     
    cout << ans << "\n";
}

Delete 1,4,7,…

设 $f(n)$ 为进行一次删除后第 $n$ 个位置的数，手玩一下发现 $f(n) = \lfloor \frac{3n+1}{2} \rfloor$，这个式子是可以推广到 $k$ 次删除的，套 $k$ 层 $f$ 就行了，所以我们记 $f^k(n) = f(f(\cdots f(n)))$。

我们可以很快地递推出进行 $k$ 次操作后数列中剩下的数的个数，设其为 $cnt$ ，我们只需要求出 $\sum _{i=1} ^{cnt} f^k(i)$ 就行了。

暴力求的话是 $O(nk(\frac{3}{2})^k)$ 的时间复杂度，但如果 $k$ 较小的话显然会超时。

在上面我们只找到了 $f^k$ 和 $f^{k-1}$ 之间的关系，如果能找到 $f^k(i)$ 与 $f^k(j)$ 之间的关系就可以进行一个递推的做了。

一个直觉上很对的等式: $f^k(n+2^k) = f^k(n)+3^k$ ，这个式子直接拆开一层就可以得证了。

但是这样做完时间复杂度是 $O(k*2^k)$ 的，还是不太够。

考虑进行一个类似折半搜索的东西，将 $f^k(i)$ 拆成 $f^x(f^y(i))$ ，那么 $f^k(i+2^yj) = f^x(f^y(i+2^yj)) = f^x(f^y(i)+3^yj)$。

设 $g(a,i)$ 为 $\sum\limits _{j=0} ^{2^i-1} f^x(a+3^yj)$，那么 $g(a,i) = g(a,i-1) + g(a+3^y2^{i-1}, i-1)$。

在小范围内进行一个记搜就可以通过了。

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int P = 998244353;
 
ll n ,k, x, y, ans;
ll lim, pw3[105];
unordered_map<ll,int> mem[105];
  
ll f(ll x, ll k);
ll g(ll a, ll i);
void work1();
void work2();
  
int main()
{
    cin >> n >> k;
    for(int i = 1;i <= k;i++)
        n -= (n+2)/3;
    if(k > 36) work1();
    else work2();
    cout << ans;
}
  
void work2()
{
    pw3[0] = 1;
    x = k>>1;
    y = k-x;
    lim = (1ll<<x)-1;
    for(int i = 1; i <= 29; i++)
        pw3[i] = pw3[i-1]*3 % P;
    for(int i = 1; i <= n and i <= (1ll<<y); i++)
    {
        ll a = f(i, y), lim = ((n - i)>>y) + 1;
        for(int j = 50; j >= 0; j--)
            if(lim>>j&1)
            {
                (ans += g(a,j)) %= P;
                a += pw3[y]<<j;
            }
    }
}
  
void work1()
{
    for(ll i = 1;i <= n;i++)
    ans = (ans + f(i,k)) % P;
}
 
ll g(ll a, ll i)
{
    if(a - 1 > lim) return (g(((a-1)&lim)+1, i) + ((a-1)>>x)%P * pw3[x]%P * ((1ll<<i)%P)%P) % P;
    if(i == 0) return mem[i][a] = f(a,x)%P;
    if(mem[i].count(a)) return mem[i][a];
    return mem[i][a] = (g(a,i-1) + g(a + pw3[y] * (1ll << (i-1)),i-1)) % P;
}
  
ll f(ll x, ll k)
{
    if(!k) return x;
    else return f((x*3+1)/2, k-1);
}

Priorty Queue

考虑将 $A$ 个 $1$ 和 $B$ 个 $2$ 依次排列开来，并且按 $1 \cdots n$ 标号，我们尝试去构造一组字典序最大的最终集合，那么字典序比它大的都无法构造，比它小的都一定可以构造。

字典序最大的集合构造方法就是在第 $i$ 次操作插入第 $i$ 个数就行了，遇到操作 $2$ 就找一个不在最终集合里的数垫背。

然后再进行一个 $O(n^2)$ 的 DP 求出字典序小于等于这个的集合有多少个就 OK 了。

#include <cstdio>
#include <iostream>
using namespace std;
 
const int N = 5005;
const int P = 998244353;
 
int A, B;
int st[N], top, cnt;
int f[2][N];
 
int main()
{
    cin >> A >> B;
    for(int i = 1; i <= A+B; i++)
    {
        int x; cin >> x;
        if(x == 1) st[++top] = ++cnt;
        else top--;
    }
     
    f[0][0] = 1;
    for(int i = 1; i <= top; i++)
    {
        f[i&1][0] = 0;
        for(int j = 1; j <= st[i]; j++)
            f[i&1][j] = (f[i&1][j-1]+f[(i-1)&1][j-1])%P;
    }
     
    int ans = 0;
    for(int i = 1; i <= st[top]; i++)
        (ans += f[top&1][i]) %= P;
    cout << ans << "\n";
}