2024.11.26 鮮花

傳話游戲題解

七里香

窗外的麻雀
在電線桿上多嘴
你說這一句
很有夏天的感覺
手中的鉛筆
在紙上來來回回
我用幾行字形容你是我的誰
秋刀魚 的滋味
貓跟你都想了解
初戀的香味就這樣被我們尋回
那溫暖 的陽光
像剛摘的鮮艷草莓
你說你舍不得吃掉這一種感覺
雨下整夜
我的愛溢出就像雨水
院子落葉
跟我的思念厚厚一疊
幾句是非
也無法將我的熱情冷卻
你出現(xiàn)在我詩的每一頁
雨下整夜
我的愛溢出就像雨水
窗臺蝴蝶
像詩里紛飛的美麗章節(jié)
我接著寫
把永遠(yuǎn)愛你寫進(jìn)詩的結(jié)尾
你是我唯一想要的了解
雨下整夜
我的愛溢出就像雨水
院子落葉
跟我的思念厚厚一疊
幾句是非
也無法將我的熱情冷卻
你出現(xiàn)在我詩的每一頁
那飽滿 的稻穗
幸福了這個季節(jié)
而你的臉頰像田里熟透的番茄
你突然 對我說
七里香的名字很美
我此刻卻只想親吻你倔強(qiáng)的嘴
雨下整夜
我的愛溢出就像雨水
院子落葉
跟我的思念厚厚一疊
幾句是非
也無法將我的熱情冷卻
你出現(xiàn)在我詩的每一頁
整夜 我的愛溢出就像雨水
窗臺蝴蝶
像詩里紛飛的美麗章節(jié)
我接著寫
把永遠(yuǎn)愛你寫進(jìn)詩的結(jié)尾
你是我唯一想要的了解

不是都聽了一輩子了，能不能換一首

屬于是思維極高的題，下輩子也想不到。

沒有歧義時將 \((S_1)_i\) 簡記為 \(s_i\)

首先考慮什么時候會重復(fù)，顯然是當(dāng)刪除兩個不同位置后結(jié)果一樣。

設(shè)第 \(i\) 個點(diǎn)被刪除的上一個時刻是 \(t_i\)，也就是說在 \(S_{t_i+1}\) 時將 \(s_i\) 刪掉。

我們將貢獻(xiàn)同統(tǒng)一欽定放到后面，也就是說 \(1,2,2,1\to 1,2,1\) 我們認(rèn)為是刪除后面的 \(2\)，而認(rèn)為刪除前面的不合法。

考慮形式化描述不合法的情況：\(s_i=s_j\land i<j\land t_i<t_j\) 并且不存在一個 \(k\) 滿足 \(i<k<j\land t_k > t_i\land s_k\not=s_i\)。

容易發(fā)現(xiàn)這是序列不重的必要條件，感覺上也是充分的，考慮證明其充分性。

對于每個 \(S_t\) 單獨(dú)考慮，將 \(t_i>t\) 設(shè)為 \(1\)，\(t_i<t\) 設(shè)為 \(0\)，考慮 dp 生成子序列的過程，容易發(fā)現(xiàn)一個子序列和一個 \(01\) 串一一對應(yīng)。

考慮統(tǒng)計，發(fā)現(xiàn)這個限制依然不太好做，發(fā)現(xiàn)難點(diǎn)在于枚舉 \(i, j, k\)，考慮對所有 \(j\) 一起做，發(fā)現(xiàn)這個限制事實(shí)上等價于對于 \(i\) 的一個最小的 \(j\) 滿足 \(i<j\land t_i<t_j\)，若 \(s_i=s_j\) 則不合法。

這個可以在笛卡爾樹上做區(qū)間 dp。

具體的，設(shè) \(dp_{l,r,p,v}\) 表示 \([l,r]\) 這段區(qū)間，其中填的 \(t\) 的最大值是 \(t_p=v\)，轉(zhuǎn)移是顯然的，用前綴和優(yōu)化可以做到 \(nm^5\)。

考慮優(yōu)化，發(fā)現(xiàn) \(p\) 是不必要的，因?yàn)槲覀兪冀K會將 \(t_p\) 和 \(t_{r+1}\) 作比較，不妨直接在枚舉狀態(tài)時比較，這樣就不用在轉(zhuǎn)移時比較并記錄這一維了，于是用前綴和優(yōu)化可以做到 \(nm^3\)。

考慮干掉 \(n\)，我們最后要求的是前綴和 \(sm_{1,m,n}\) 其實(shí)容易發(fā)現(xiàn)對于 \(n\) 只有 \(m\) 個點(diǎn)會變化，也就是說 \(n\) 并不在關(guān)鍵的地方，可能可以聯(lián)想到 \(sm_{1,m,x}\) 是一個關(guān)于 \(x\) 的 \(m+1\) 次多項式。

證明也不難，考慮 \(sm_{1,1}\) 顯然是 \(1\) 次多項式，而轉(zhuǎn)移本質(zhì)是卷積，其會把次數(shù)相加。

所以用拉差差出來即可。

復(fù)雜度是 \(\mathcal{O}(m^4)\) 的，不卡常什么的都是扯淡，關(guān)鍵的地方在于在 dp 時用 __int128_t 存值減少上界的取模（但是不要將 dp 數(shù)組開 __int128_t）。

Code

#include<bits/stdc++.h>
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
#ifdef LOCAL
	FILE *InFile=freopen("in_out/in.in","r",stdin),*OutFile=freopen("in_out/out.out","w",stdout);
#else
	FILE *InFile=freopen("message.in","r",stdin),*OutFile=freopen("message.out","w",stdout);
#endif

const int M=207,MOD=1e9+7;
int dp[M][M][M],fac[M],ivf[M],n,m; int cs[M];

class LGG{
private: int cy[M],lmu[M],rmu[M],len;
public:
	void In(){len=m+2; for(int i=1;i<=len;++i) cy[i]=dp[1][m][i];}
	int operator()(int x){
		int y=0; memset(lmu,0,sizeof(lmu)),memset(rmu,0,sizeof(rmu));
		lmu[0]=1; for(int i=1;i<=len;++i) lmu[i]=1ll*lmu[i-1]*(x-i)%MOD;
		rmu[len+1]=1; for(int i=len;i;--i) rmu[i]=1ll*rmu[i+1]*(x-i)%MOD;
		for(int i=1;i<=len;++i) y=(y+1ll*cy[i]*lmu[i-1]%MOD*rmu[i+1]%MOD*ivf[i-1]%MOD*ivf[len-i]%MOD*(len-i&1?-1:1)+MOD)%MOD;
		return y;
    }
}Lgg;

int main(){
	ios::sync_with_stdio(0),cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>m; for(int i=1;i<=m;++i) cin>>cs[i];
	fac[0]=1; for(int i=1;i<=M-3;++i) fac[i]=1ll*fac[i-1]*i%MOD; cerr<<fac[M-3]<<endl;
	ivf[M-3]=657408467; for(int i=M-3;i;--i) ivf[i-1]=1ll*ivf[i]*i%MOD;
	for(int i=1;i<=m;++i) for(int j=0;j<=m+2;++j) dp[i][i-1][j]=dp[i+1][i][j]=1;
	for(int ln=1;ln<=m;++ln) for(int l=1;l+ln-1<=m;++l){
		int r=l+ln-1; dp[l][r][0]=0;
		for(int v=1;v<=m+2;++v){
			__int128_t t=0;
			for(int k=l;k<=r;++k) if(cs[k]!=cs[r+1]) t+=1ll*dp[l][k-1][v-1]*dp[k+1][r][v];
			dp[l][r][v]=(t+dp[l][r][v-1])%MOD;
		}
	}
	Lgg.In(); cout<<Lgg(n)<<endl;
}

posted @ 2024-11-26 21:23 xrlong 閱讀(88) 評論(2) 收藏舉報

刷新頁面返回頂部

xrlong

博客密碼是 K8 色號

2024.11.26 鮮花

傳話游戲題解

公告

Loading