2014-02-14

■ SRM 597 Div1 Hard 02:49

自力で解いたD1Hardはたぶん2問目です。

ちょっと考えると、「0をx個 1をy個 2をz個、同じ文字が隣り合わないように並べる方法は何通りか」

を考えればよいことが分かる。

これはdp[i]=(同じ数字が連続している部分を"ブロック"とした時x個ブロックがあるような0と1の並べ方)とすると、

dp[i]* i+1 C (z-(x+y-i))の総和で求められる。dpテーブルの計算もやるだけ。

よってやるだけなんだけど正しく実装するのは闇(組み合わせの闇といわれるもの)

//Oh...(Booklet)
#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;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define mod 1000000007LL
typedef long long ll;
ll v[2000005];
ll dp[2000005];
class LittleElephantAndBoard
{
	public:
	long long modpow(long long x,long long n)
	{
		long long res=1LL;
		while(n>0)
		{
			if(n&1LL) res=(res*x)%mod;
			x=(x*x)%mod;
			n>>=1LL;
		}
		return res;
	}
	int getNumber(int M, int R, int G, int B)
	{
		v[0]=1LL;
		for(int i=1;i<=2000000;i++)
		{
			v[i]=(v[i-1]*1LL*i)%mod;
		}
		int a=M-R,b=M-G,c=M-B;
		if(a==0) swap(a,c);
		if(b==0) swap(b,c);
		//0,0,M.So there mustn't be valid solution.
		if(!a || !b) return 0;
		for(int i=2;i<=a+b;i++)
		{
			int A=(i+1)/2;
			int B=i/2;
			ll res,res2;
			if(agoto nxt;
			//a comes first
			//a-1 C A-1 * b-1 C B-1
			res=(v[a-A]*v[A-1])%mod;
			res=(v[a-1]*modpow(res,mod-2))%mod;
			res2=(v[b-B]*v[B-1])%mod;
			res2=(v[b-1]*modpow(res2,mod-2))%mod;
			dp[i]+=((res*res2)%mod);
			dp[i]%=mod;
			nxt:;
			if(agoto nxt2;
			//b comes first
			//b-1 C A-1 * a-1 C B-1
			res=(v[b-A]*v[A-1])%mod;
			res=(v[b-1]*modpow(res,mod-2))%mod;
			res2=(v[a-B]*v[B-1])%mod;
			res2=(v[a-1]*modpow(res2,mod-2))%mod;
			dp[i]+=((res*res2)%mod);
			dp[i]%=mod;
			nxt2:;
			//if(dp[i]>=mod) cout << dp[i] << endl;
		}
		ll ret=0;
		for(int i=2;i<=a+b;i++)
		{
			int rem=c-(a+b-i);
			if(rem<0) continue;
			if(rem>i+1) continue;
			//i+1 C rem
			ll res=(v[rem]*v[i+1-rem])%mod;
			res=(v[i+1]*modpow(res,mod-2))%mod;
			ret+=((dp[i]*res)%mod);
			ret%=mod;
		}
		ret*=2LL; if(ret>=mod) ret-=mod;
		return ret;
	}
};

あとTLEが地味にやばかったけどそれは逆元をO(N)でもとめとけば何とかなると思います

ツイートする