2022-9-8总结

Ribbons on Tree

树形 DP，定义 $g_i$ 表示 $i$ 个点两两配对的方案数（奇数为 $0$），否则方案数就是小于 $i$ 的奇数的积，比较好算。

然后容斥一下就可以 DP 了。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long ll;
const int N = 5005;
const int P = 1e9+7;

namespace graph {
    struct edge {
        int to, next;
    }e[N*2];
    int head[N], ecnt;
    void insert(int u, int v)
    {
        e[++ecnt] = {v, head[u]}; head[u] = ecnt;
        e[++ecnt] = {u, head[v]}; head[v] = ecnt;
    }
}
using namespace graph; 

int n;
int siz[N];
ll f[N][N];
ll g[N], tmp[N];

void prework(int n);
void dfs(int x, int fa);

int main()
{
    cin >> n; prework(n);
    for(int i = 1, a, b; i < n; i++)
    {
        cin >> a >> b;
        insert(a, b);
    }
    
    dfs(1, 0);
    
    printf("%d\n", P-f[1][0]);
    return 0;
}

void prework(int n)
{
    g[0] = 1;
    for(int i = 2; i <= n; i += 2)
        g[i] = g[i-2]*(i-1)%P;
}
void dfs(int x, int fa)
{
    siz[x] = 1;
    f[x][1] = 1;
    for(int i = head[x]; i; i = e[i].next)
    {
        int y = e[i].to;
        if(y == fa) continue;
        dfs(y, x);
        memset(tmp, 0, sizeof(tmp));
        for(int j = 1; j <= siz[x]; j++)
            for(int k = 0; k <= siz[y]; k++)
                (tmp[j+k] += f[x][j]*f[y][k]%P) %= P;
        siz[x] += siz[y];
        memcpy(f[x], tmp, sizeof(tmp));
    }
    for(int i = 2; i <= siz[x]; i += 2)
    {
        f[x][0] -= f[x][i]*g[i]%P;
        f[x][0] = (f[x][0]%P+P)%P;
    }
}

Papple Sort

如果要构成回文串，那么每个字符都是对称的，所以我们从前往后扫一遍，遇到一个字符就选一个与它对称的，这时候可以贪心一手，选一个最远的相同字符与当前字符匹配。

我们就这样给每个位置标个号，问题就变成了：给一个排列，交换相邻两项将其排序。

很明显求个逆序对就可以了。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <vector>
using namespace std;

typedef long long ll;
const int N = 200005;

int n;
ll ans;
int a[N];
char s[N];
bool vis[N];
list<int> id[128];

namespace bit {
    int a[N];
    #define lowbit(x) (x&-x)
    void add(int x)
    {
        for(; x <= n; x += lowbit(x))
            a[x] += 1;
    }
    int query(int x)
    {
        int ans = 0;
        for(; x >= 1; x -= lowbit(x))
            ans += a[x];
        return ans;
    }
}

int main()
{
    scanf("%s", s+1);
    n = strlen(s+1);
    for(int i = 1; i <= n; i++)
        id[s[i]].push_back(i);
    
    int tot = 0;
    for(int i = 0; i < 128; i++)
        tot += id[i].size()%2;
    
    if(n%2 == 0 and tot > 0) { cout << "-1"; goto end; }
    if(n%2 == 1 and tot > 1) { cout << "-1"; goto end; }
    
    for(int i = 1, pos = 0; i <= n; i++)
    {
        if(vis[i]) continue;
        if(!id[s[i]].size()) continue;
        if(id[s[i]].size() == 1)
            a[i] = (n+1)/2;
        else
        {
            pos++;
            int j = *--id[s[i]].end();
            id[s[i]].pop_front();
            id[s[i]].pop_back();
            a[i] = pos, a[j] = n-pos+1;
            vis[i] = vis[j] = true;
        }
    }
    
    
    for(int i = n; i >= 1; i--)
    {
        ans += bit::query(a[i]-1);
        bit::add(a[i]);
    }

    cout << ans << endl;    
    
    end: return 0;
}

交换

观察合法串的构成条件，其实就是个括号匹配问题。

处理括号匹配问题可以用栈解决，而我们需要知道交换两个字符后是否能将让两个栈里的元素一一匹配上。

需要统计方案数，所以我们可以考虑分治解决，如果当前分治的区间为$[l,r]$，设 $l \le i \le mid, mid < j \le r$，我们需要维护 $[1,i], [i+1,mid], [mid+1,j-1], [j,n]$ 四个栈。

然后我们需要合并两个栈看是否能消掉，所以我们需要求出两个栈的最长公共前缀，这个可以 hash + 二分解决。

然后就是计算当 $i$ 和 $j$ 被修改后的 hash 值。

然后找对于每一个 $i$，有多少相等的 $j$ 的 hash 值，用一个 map 即可解决。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <unordered_map>
using namespace std;

typedef long long ll;
const int N = 100005;
namespace Hash {    
    const int P = 1e9+7;
    const int base = 1331;
    ll pw[N];
    void prework(int n);
}
using namespace Hash;

struct Stack {
	int st[N], t;
	ll hash1[N]; 
	ll hash2[N];
    Stack() { st[t=0] = -1; }
    void clear() { t = 0; }
	void insert(int x)
	{
		if(st[t] == x)
            t--;
		else
		{
			st[++t] = x;
            hash1[t] = (hash1[t-1]*base%P + x)%P;
            hash2[t] = (hash2[t-1] + pw[t-1]*x%P)%P;
        }
	}
    void del(int x)
    {
        insert(x);
    }
};

int n;
ll len;
char s[N];
Stack pre, suf, tmp;
unordered_map<ll,int> t;
ll f1[N][3], f2[N][3];

void solve(int l, int r);
void get_left(int l, int r);
void get_right(int l, int r);
int binary_search(Stack &a, Stack &b);

int main()
{
    scanf("%s", s+1);
    n = strlen(s+1);
    for(int i = 1; i <= n; i++)
        s[i] -= 'a';
    
    Hash::prework(n);
    
    solve(1, n);
    
    printf("%lld", len);
}


void solve(int l, int r)
{
    if(l == r) return;
    int mid = (l+r)>>1;
    get_left(l, mid);
    get_right(mid+1, r);

    for(int a = 0; a < 3; a++)
    {
        for(int b = 0; b < 3; b++)
        {
            if(a == b) continue;
            t.clear();
            for(int i = l; i <= mid; i++)
                if(s[i] == a) ++t[f1[i][b]];
            for(int i = mid+1; i <= r; i++)
                if(s[i] == b) len += t[f2[i][a]];
        }
    }

    solve(mid+1, r);
    for(int i = mid; i >= l; i--) pre.del(s[i]);
    for(int i = r; i > mid; i--) suf.insert(s[i]);
    solve(l, mid);
    for(int i = mid+1; i <= r; i++) suf.del(s[i]);
}


void get_left(int l, int r)
{
    tmp.clear();
    for(int i = r; i >= l; i--)
        tmp.insert(s[i]);
    for(int i = l; i <= r; i++)
    {
        tmp.del(s[i]);
        for(int a = 0; a < 3; a++)
        {
            if(a == s[i]) continue;
            pre.insert(a);
            int x = binary_search(pre, tmp);
            f1[i][a] = (pre.hash1[pre.t-x]*pw[tmp.t-x]%P + tmp.hash2[tmp.t-x])%P;
            pre.del(a);
        }
        pre.insert(s[i]);
    }
}
void get_right(int l, int r)
{
    tmp.clear();
    for(int i = r; i >= l; i--)
        suf.insert(s[i]);
    for(int i = l; i <= r; i++)
    {
        suf.del(s[i]);
        for(int a = 0; a < 3; a++)
        {
            if(a == s[i]) continue;
            tmp.insert(a);
            int x = binary_search(tmp, suf);
            f2[i][a] = (tmp.hash2[tmp.t-x] + suf.hash1[suf.t-x]*pw[tmp.t-x]%P)%P;
            tmp.del(a);
        }
        tmp.insert(s[i]);
    }
}
int binary_search(Stack &pre, Stack &suf)
{
    int l = 0, r = min(pre.t, suf.t);
    while(l < r)
    {
        int mid = (l+r+1)>>1;
        ll hash1 = (pre.hash1[pre.t] - pre.hash1[pre.t-mid]*pw[mid]%P+P)%P;
        ll hash2 = (suf.hash1[suf.t] - suf.hash1[suf.t-mid]*pw[mid]%P+P)%P;
        if(hash1 == hash2)
            l = mid;
        else
            r = mid-1;
    }
    return l;
}

namespace Hash {
    void prework(int n)
    {
        pw[0] = 1;
        for(int i = 1; i <= n; i++)
            pw[i] = (ll)pw[i-1]*base%P;
    }
}