Codeforces ECR #114 : F. Occurrences

なるほど。
https://codeforces.com/contest/1574/problem/F

問題

N個の数列A[i]が与えられる。

1～Kの範囲の整数値を取るM要素の数列Bのうち、下記条件を満たすのは何通りか。

• Bの連続部分列として各A[i]が現れる回数は、Bの連続部分列として各A[i]の連続部分列が現れる回数より小さくない

解法

B中でA[i][j]が現れる場合、次はA[i][j+1]が来なければならない。
そうでないと、B中のA[i][j]の登場頻度がA[i]全体を超えてしまう。

上記条件を、B中で取りうる値を頂点、次にどの値が来なければならないかの条件を辺で表現した、有向グラフとして表現しよう。
この時、B中に含めることができるのはグラフ中のパスのうち、「始点は入次数0、終点は出次数0で、途中枝分かれのないものを選び、パス上の頂点を順に並べたもの」をいくつか並べたものとなる。
まずグラフを強連結成分して、上記条件を満たすパスの長さと個数を列挙しよう。

あとはそのようなパスを、総長Mになるまで並べるだけで、これは単純なDPである。

int N,M,K;
int invalid_num[303030];
int in[303030];
set<int> E[302020];

class SCC {
public:
	static const int MV = 305000;
	vector<vector<int> > SC; int NV,GR[MV];
private:
	vector<int> E[MV], RE[MV], NUM; int vis[MV];
public:
	void init(int NV) { this->NV=NV; for(int i=0;i<NV;i++) { E[i].clear(); RE[i].clear();}}
	void add_edge(int x,int y) { E[x].push_back(y); RE[y].push_back(x); }
	void dfs(int cu) { vis[cu]=1; for(int i=0;i<E[cu].size();i++) if(!vis[E[cu][i]]) dfs(E[cu][i]); NUM.push_back(cu); }
	void revdfs(int cu, int ind) { int i; vis[cu]=1; GR[cu]=ind; SC[ind].push_back(cu);
		FOR(i,RE[cu].size()) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);}
	void scc() {
		int c=0,i; SC.clear(); SC.resize(NV); NUM.clear();
		assert(NV);
		FOR(i,NV) vis[i]=0; FOR(i,NV) if(!vis[i]) dfs(i); FOR(i,NV) vis[i]=0;
		for(int i=NUM.size()-1;i>=0;i--) if(!vis[NUM[i]]){
			SC[c].clear(); revdfs(NUM[i],c); sort(SC[c].begin(),SC[c].end()); c++;
		}
		SC.resize(c);
	}
};
SCC scc;

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<303030> uf;
ll dp[303030];
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d%d",&N,&M,&K);
	scc.init(K);
	FOR(i,N) {
		scanf("%d",&x);
		int pre=-1;
		FOR(j,x) {
			scanf("%d",&y);
			y--;
			if(pre!=-1) {
				if(E[pre].count(y)==0) {
					E[pre].insert(y);
					in[y]++;
					scc.add_edge(pre,y);
				}
				uf(pre,y);
			}
			pre=y;
		}
	}
	scc.scc();
	FOR(i,K) {
		if(E[i].size()>1||in[i]>1) invalid_num[uf[i]]=1;
		FORR(e,E[i]) if(e==i) invalid_num[uf[i]]=1;
	}
	FORR(sc,scc.SC) {
		if(sc.size()>1) invalid_num[uf[sc[0]]]=1;
	}
	
	map<int,int> cand;
	FOR(i,K) if(invalid_num[uf[i]]==0&&in[i]==0) {
		int len=1;
		x=i;
		while(E[x].size()) {
			len++;
			x=*E[x].begin();
		}
		cand[len]++;
	}
	
	dp[0]=1;
	for(i=1;i<=M;i++) {
		FORR2(a,b,cand) if(a<=i) (dp[i]+=dp[i-a]*b)%=mo;
	}
	cout<<dp[M]<<endl;
	
	
}

まとめ

やることはともかく、問題設定がややこしいな。