2024.2.16 そんな凡庸を探して、探している

cnyz / 2024-02-17 / 原文

Namid[A]me 好听呢。可惜了。
今天 DP 专题感觉 laofu 选的题有点经典，导致我有一半时间在摸鱼，不过还是写了点题的。
怎么西工大附中有糖醋茄子这种神秘菜啊。

ICPC 2020 Macau B Boring Problem

其实不一定懂完了，试着说一说。
显然询问没什么用，问题本质是要求解一个 AC 自动机上游走问题。
直接高斯消元显然寄飞了，考虑优化。
考虑原本的高斯消元是什么样的，是：$f_u=\sum_{i=1}^k p_i f_{tr(u,k)}+1$。
考虑主元法，发现这样一件事：如果在原 Trie 上某个节点只有一个儿子，这个点在 AC 自动机上的其余转移全部会指向向上的节点，于是可以用父亲的方程推出儿子用主元表示的结果。
于是令根节点与儿子个数大于二的节点的儿子们作为主元，这样就只有 $O(n)$ 个主元，可以使用 BFS 推出所有元用主元表示的结果，以结束点答案为 $0$ 和「儿子个数大于二的节点」存在两种表示：「用儿子们」「从父亲推」来构造方程，于是就做到 $O(n^3)$，Code。
昨天模拟赛 T3 就这个东西加后半的普及组答辩，不写了。

IOI2005 River

令 $f_{u,j,k}$ 表示对于点 $u$ 钦定祖先 $j$ 作为最近的伐木场，子树内选了 $k$ 个伐木场，$g_{u,j,k}$ 同上，但是 $u$ 是一个伐木场，同时这个也没算进 $k$ 里面。
于是暴力 DP 复杂度就是 $O(n^2k^2)$，对了，Code。

TC12909 Seat Friends

令 $f_{i,j}$ 表示当前 $i$ 个人 $j$ 段，于是可以列出转移柿子：

\[\begin{aligned} 2jf_{i,j}&\to f_{i+1,j}\\ jf_{i,j}&\to f_{i+1,j-1}\\ jf_{i,j}&\to f_{i+1,j+1} \end{aligned} \]

最后计算答案需要上一个组合数，还得记得考虑圆是可以转圈的，$O(n^2)$，Code。

CS Academy Round #32 Sum of Powers

需要知道 $f_{i,j}$ 表 $i$ 个数凑出 $j$ 这样的 DP。
于是就会发现求 $f_{i-k,j-k*l}k^m$ 的总和就是答案了，证明很好证。

/*
Author: cnyz
世界があたしを拒んでも今 愛の唄 歌わせてくれないかな
*/
#include<bits/stdc++.h>
using namespace std;

using db=double;
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
using ull=unsigned long long;

#define fi first
#define se second
#define gc getchar
#define pb emplace_back
#define mkp make_pair
#define push emplace
#define sz(a) (int)a.size()
#define all(p) p.begin(),p.end()
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)

bool Mbe;

void chkmax(int &x,int y) {if(x<y) x=y;}
void chkmin(int &x,int y) {if(x>y) x=y;}
void chkmax(ll &x,ll y) {if(x<y) x=y;}
void chkmin(ll &x,ll y) {if(x>y) x=y;}
int read() { int x; cin>>x; return x; }

const int mod=1e9+7;
struct modint {
    int x;
    modint(int o=0) { x=(0ll+mod+o)%mod; }
    modint &operator = (int o) { return x=o,*this; }
    modint &operator += (modint o) { return x=(x+o.x)%mod,*this; }
    modint &operator -= (modint o) { return x=(mod+x-o.x)%mod,*this; }
    modint &operator *= (modint o) { return x=1ull*x*o.x%mod,*this; }
    modint &operator ^= (int b) {
        modint a=*this,c=1;
        for(;b;b>>=1) { if(b&1) c*=a; a*=a; }
        return x=c.x,*this;
    }
    modint &operator /= (modint o) { return *this*=(o^=mod-2); }
    friend modint operator + (modint a,modint b) { return a+=b; }
    friend modint operator - (modint a,modint b) { return a-=b; }
    friend modint operator * (modint a,modint b) { return a*=b; }
    friend modint operator / (modint a,modint b) { return a/=b; }
    friend modint operator ^ (modint a,int b) { return a^=b; }
    friend bool operator == (modint a,int b) { return a.x==b; }
    friend bool operator != (modint a,int b) { return a.x!=b; }
    bool operator ! () { return !x; }
    modint operator - () { return x?mod-x:0; }
    bool operator < (const modint &b) const { return x<b.x; }
};

const int N=5005;
modint f[N][N],g[N];
void solve() {
    int n=read(),K=read(),m=read();
    f[0][0]=1;
    FOR(i,0,K-1) FOR(j,0,n) {
        f[i+1][j+1]+=f[i][j];
        if(i&&j+i<=n) f[i][j+i]+=f[i][j]; 
    }
    modint o=0;
    FOR(i,1,n) FOR(j,1,K) if(i*j<=n) {
        modint pm=i; pm^=m;
        o+=f[K-j][n-i*j]*pm;
    }
    cout<<o.x<<"\n";
}

bool Med;
int main() {
    ios::sync_with_stdio(false),cin.tie(0);
    // fprintf(stderr, "%.3lf MB\n", (&Med - &Mbe) / 1048576.0);
    int T=1;
    while(T--) solve();
    // fprintf(stderr, "%d ms\n", int(1e3 * clock() / CLOCKS_PER_SEC));
}

NOIOL #1 跑步

令 $f_{i,j}$ 表上面的 DP，$g_{i,j}$ 表用 $[1,i]$ 背出 $j$ 的总方案，都是容易 $O(n^2)$ 做到的。
根号分治，对于 $<\sqrt{n}$ 的跑 $g$，对于 $>\sqrt{n}$ 的跑 $f$，复杂度都是 $O(n\sqrt{n})$ 的。
于是就平衡住了，Code。