Noip2016 六校模拟 AHSDFZ Round 3

tonyfang posted @ 2016年11月08日 14:37 in 随笔 with tags C++ OI , 267 阅读
1. 圆桌会议
学校要策划$q$次会议,第$i$次会议有$m_i$位同学,将被安排在一个环绕着$n_i$个座位(座位是两两不同的)的圆桌边举行,并且任意两个人之间至少空$k_i$个座位。主办方会在参会人员来临之前,将其中$m_i$个座位标注为可就坐的。现标注为可就坐的。现在请你帮忙计算出他们共有多少种合法的标注座位方案(对$10^9+7$取模)。
对于20%的数据,$q \leq 10, n \leq 20$;
对于额外30%的数据,$q \leq 1000,~n_i, m_i \leq 10^6, k_i = 0$;
对于额外20%的数据,$q \leq 1000,~n_i, m_i \leq 10^6, k_i = 1$;
对于100%的数据,$ q \leq 100, 0 < m_i < n_i \leq 106, 0 \leq k_i \leq 1000$;
【题解】推推公式就行啦
# include <stdio.h>
# include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int M = 1000010;
const int mod = 1e9+7;

/*
假设m个人已经围成了一圈,那么有m个位置需要插空椅子。
C(n-k*m-1, m-1)*n/m
*/ 

ll frac[M];

inline ll pwr(ll x, ll y) {
	ll ret = 1;
	while(y) {
		if(y&1) ret = 1ll * ret * x % mod;
		x = 1ll * x * x % mod;
		y >>= 1;
	}
	return ret;
}

inline ll C(ll n, ll k) {
	if(n<k || n<0) return 0;
	return 1ll * frac[n] * pwr(1ll * frac[k] * frac[n-k] % mod, mod-2) % mod;
}

int n, m, k;

int main() {
//	freopen("meeting.in", "r", stdin);
//	freopen("meeting.out", "w", stdout);
	
	frac[0] = 1;
	for (int i=1; i<=1000000; ++i)
		frac[i] = 1ll * frac[i-1] * i % mod;
		
	int Q; scanf("%d", &Q);
	while(Q--) {
		scanf("%d%d%d", &n, &m, &k);
		if(m == 1) {
			printf("%d\n", n);
			continue;
		}
		if(n-(k+1)*m < 0) {
			puts("0");
			continue;
		}
		ll ans = 1ll * C(n-m*k-1, m-1)*n % mod * pwr(m, mod-2) % mod;
		printf("%lld\n", ans);
	}
	return 0;
}
2.间谍
有三个间谍 007、008、009潜入了 敌境。 这个 国家共有 N座城市, 它们之 间存在着$m$条有向边 ,通过任意一条边的时间都是1。初始时三位间谍各有一个起点城市,此后他们将一直沿着有向边保持行进,由于边权均为1,任意整数时刻他们一定都在城市。每座城市有各自的无线电频$w_i$,每当三人到达城市时,必须保证两两所在城市的$w_i$差不超过一给定的值$k$,否则这种走法就是不合法的。在任意整数时刻(包括初始时刻)他们都可以选择结束任务(必须一起结束)。三个人共须执行$q$次任务,每会分别给三人配一个起点(保证起点合法), 问他们共有多少种不同的执行任务的方案 (两个方案被视作不同当且仅当至少存在一个人某整数时刻所在的城市不同),对于$998244353$取模。
对于30%的数据,$n \leq 8$;
对于60%的数据,$n \leq 20$;
对于100%的数据,$n \leq 50, M \leq \frac{n \times (n - 1)}{2}, 0 \leq K \leq 10^9, 1 \leq Q \leq 125000, 1 \leq w_i \leq 10^9, 1 \leq u_i < v_i \leq n$,保证没有重边 。
【题解】原题,见这里:http://tonyfang.is-programmer.com/posts/204777.html
 
3.宝藏查询

 

AireenYe 说:
2016年11月08日 16:02

orzTonyFang!!!


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter