kmjp's blog

競技プログラミング参加記です

yukicoder : No.444 旨味の相乗効果

yukicoder

この行列がすんなり出てこなかった。
http://yukicoder.me/problems/no/444

問題

N種類の旨み成分があり、それぞれの旨みはA[i]である。
これらから重複を許して計C個の旨みを抜き出す。
2種類以上の旨みを抜き出したとき、C個の旨みの積を全体の旨みとなる。

C個の旨みの抜き出し方における全体の旨みの総和を求めよ。

解法

1種類の旨みだけでC個選ぶ場合の全体の旨みは容易に求められるので、「2種類以上～～」の条件は無視してC個の旨みの積の総和だけを考えて、最後に1種類だけ選んだケースを引けば良い。

以下の状態を考える。（書き方は違うが値はEditorialと同じ)
f(c,n) := 先頭n種類の成分から全体でc個の旨みを選ぶ場合の旨みの積の総和(ただしc==0の時は1とする。)
求めたいものはf(C,N)である。

c個目にi番を選ぶには、(c-1)個目を選ぶ際i番以下を選んでいなければいけないので、以下の式が成り立つ。
\displaystyle f(c,i) = A_1*f(c-1,1) + A_2*f(c-1,2) + ... + A_i*f(c-1,i) = \sum_{x=1}^i A_x*f(c-1,x)

以下のようにf(c,n)と、漸化式の係数をベクトル・行列の形に並べると、f(c,n)を行列累乗の形で計算できるようになる。
\displaystyle x_c = \begin{pmatrix} f(c,1) & f(c,2) & \cdots & f(c,N) \end{pmatrix}^T
\displaystyle B = \begin{pmatrix} A_1 & 0 & \cdots & 0 \\ A_2 & A_2 & \ddots & 0 \\ \vdots & \cdots & \ddots & 0 \\ A_n & A_n & \cdots & A_n \\ \end{pmatrix}
\displaystyle x_0 = \begin{pmatrix} 1 & 1 & \cdots & 1 \end{pmatrix}^T
\displaystyle x_c = B x_{c-1}

なお、1種類の旨みだけで構成されるケースはA[i]のC乗を別途計算する必要はなく、B^Cの対角成分にA[i]^Cが並ぶのでこれを引けば良い。

int N;
ll C;
ll mo=1000000007;

const int MAT=80;
ll G[MAT][MAT],G2[MAT][MAT];
void powmat(ll p,int n,ll a[MAT][MAT],ll r[MAT][MAT]) {
	int i,x,y,z;
	ll a2[MAT][MAT];
	FOR(x,n) FOR(y,n) a2[x][y]=a[x][y];
	FOR(x,n) FOR(y,n) r[x][y]=(x==y);
	while(p) {
		ll h[MAT][MAT];
		if(p%2) {
			FOR(x,n) FOR(y,n) h[x][y]=0;
			FOR(x,n) FOR(z,n) FOR(y,n) h[x][y] += (r[x][z]*a2[z][y]) % mo;
			FOR(x,n) FOR(y,n) r[x][y]=h[x][y]%mo;
		}
		FOR(x,n) FOR(y,n) h[x][y]=0;
		FOR(x,n) FOR(z,n) FOR(y,n) h[x][y] += (a2[x][z]*a2[z][y]) % mo;
		FOR(x,n) FOR(y,n) a2[x][y]=h[x][y]%mo;
		p>>=1;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>C;
	FOR(i,N) {
		cin>>r;
		FOR(x,i+1) G[i][x]=r;
	}
	
	powmat(C,N,G,G2);
	ll ret=0;
	FOR(x,N) ret+=mo+G2[x][0]-G2[x][x];
	cout<<ret%mo<<endl;
	
	
}

まとめ

勉強になりました。