Hatena::Grouptopcoder

Hiro180の日記

 | 

2014-09-05

天プロ2013本選D 18:34

あのあと1hくらい考えてわかった。

何も考えないとN^D通りあって、

そのなかに制約を満たさないものがあるからそれを取り除く。

少なくともi種類の筋肉は制約を満たさず、それらのトレーニングでj日間を費やしているような場合の数を考えると

(i種類の筋肉を選び、そこにj日間費やすようなトレーニングの仕方) * (N-i)^(D-j)

であることがわかる。あとは包除原理により,この値をi%2==1なら引き、i%2==0なら足せばよい。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
ll dp[35][35][1000];
int n,d;
int a[35];
ll c[1005][35];
long long modpow(long long x,long long n)
{
	long long res=1;
	while(n>0)
	{
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
ll C(int a,int b)
{
	ll res = 1;
	for(int i=a;i>a-b;i++) res = (res*1LL*i)%mod;
	for(int i=1;i<=b;i++) res = (res*modpow(i,mod-2))%mod;
	return res;
}
int main()
{
	cin >> n >> d;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
	}
	dp[0][0][0] = 1;
	for(int k=0;k<1000;k++) for(int x=0;x<30;x++) c[k][x] = C(d-k,x);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			for(int k=0;k<1000;k++)
			{
				if(dp[i][j][k] == 0) continue;
				dp[i+1][j][k] = (dp[i+1][j][k] + dp[i][j][k])%mod;
				for(int x=0;x<a[i+1];x++)
				{
					dp[i+1][j+1][k+x] = (dp[i+1][j+1][k+x] + dp[i][j][k] * c[k][x])%mod;
				}
			}
		}
	}
	ll res = modpow(1LL*n,1LL*d);
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=min(d,999);j++)
		{
			if(dp[n][i][j] == 0) continue;
			if(i%2 == 1)
			{
				res = (res+mod-(dp[n][i][j]*modpow(1LL*(n-i),1LL*(d-j))%mod))%mod;
			}
			else
			{
				res = (res+(dp[n][i][j]*modpow(1LL*(n-i),1LL*(d-j))%mod))%mod;
			}
		}
	}
	cout << res << endl;
}
 |