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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair 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
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;ifor(int j=0;jfor(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;x1];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;
}

ツイートする

■ 天プロ2013本選 17:14

撃沈

A:

bitDPやる

B:

面白かった。

考察するとリフルシャッフルの回数さえ同じならば、数の並びかたは同じ(いくつかずらしただけ)であり、

またk枚のカットをするとk*2^(カット後のリフルシャッフルの数)分ずれることがわかる。

これより、100点解法ではリフルシャッフルの回数を決めうちし、mod 2*n+1でk個分ずらすために必要な数を計算してdijkstraすると解ける。200点解法はDPが必要になる(?)はずで、TLEすることが明らかなオーダーになり絶望

C:

知らない

D:

数え上げが得意なほうだとかいうのは幻想でした

E:

見てない

40+100+0+0+0 = 140

別に(puke)(handshake)なセットではないけどどうしようもなかった...

ツイートする