yukicoder : No.2356 Back Door Tour in Four Seasons

これは割とすんなりだった。
https://yukicoder.me/problems/no/2356

問題

N個の街があり、i番の街は

• 春夏秋冬のいずれかであり、入力で与えられる。
• それぞれA[i]個の扉があり、それぞれ入ると他の街(N-1)個のいずれかにつながる。

各扉の行先を定めたとする。
任意の街から、扉をたどり計4つの街をたどったとする。
その際、夏・秋・冬・春の順でたどるようにしたい。
その時、各行先のパターンに応じ、条件を満たす訪問順の総和は何通りか。

解法

先に訪問順を定めたとき、それを満たす扉の行先が何通りあるかを考える。
今街i→jに移動したい場合、A[i]個の扉の少なくとも1つがjに通じてないといけないので、(N-1)^A[i]-(N-2)^A[i]通りということになる。

経路上にない街は、最後春の街の扉はどこに通じていてもよい。
同じ季節である各街に至る経路×扉の組み合わせは同一なことを鑑みて、季節ごとにDPで数え上げて行こう。

int N;
vector<int> V[4];
const ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll pat=1;
	int num=0;
	FOR(i,N) {
		cin>>s>>x;
		if(s=="U") V[0].push_back(x);
		if(s=="F") V[1].push_back(x);
		if(s=="W") V[2].push_back(x);
		if(s=="P") {
			pat=pat*modpow(N-1,x)%mo;
			num++;
		}
	}
	pat=pat*num%mo;
	FOR(i,3) {
		ll sum=0;
		FORR(v,V[i]) sum+=v;
		ll npat=0;
		FORR(v,V[i]) {
			ll a=modpow(N-1,sum-v);
			ll b=modpow(N-1,v)+mo-modpow(N-2,v);
			(npat+=a*b)%=mo;
		}
		pat=pat*npat%mo;
	}
	cout<<pat<<endl;
}

まとめ

普段春でプレイしますね。