Noip2016 六校模拟 AHSDFZ Round 3

tonyfang posted @ 2016年11月08日 14:37 in 随笔 with tags C++ OI , 1431 阅读
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!!!

njmcdirect.com 说:
2022年8月26日 10:33

NJMCdirect – the fast, secure and convenient way to access and pay your Traffic Ticket and Municipal Complaint online. njmcdirect.com To view or pay your Traffic 2021. NJMCDirect Pay Traffic Tickets Online – www.NJMCDirect.com · What is NJMCDirect? · NJMCDirect Pay – What will you need to pay njmcdirect ticket payment 2021.NJMCdirect – the fast, secure and convenient way to access and pay your Traffic Ticket and Municipal Complaint online.

mon activité 说:
2023年7月13日 19:37

Google Mon activité pour supprimer une grande partie ou la totalité de son historique de recherche. Supprimer ou effacer votre historique et votre activité de recherche. mon activité Google supprimera uniquement les éléments entrés dans les produits Google tels que l’historique de localisation de la chronologie Google Maps, les photos, l’activité de recherche et de surveillance YouTube, etc.

Meghalaya 8th Class 说:
2023年7月19日 21:13

Students Should Download the Respective Stream wise MBOSE Board 8th Class Exam Syllabus Subjects of Hindi, English, Mathematics, Science, Social Science etc, Pdf Format Provide Check the same From our page here,Students need to Start Their Preparation by first Downloading the Stream wise MBOSE 8th Class Curriculum Syllabus 2024 Latest Edition.Meghalaya Board Class Syllabus 2024 is Designed in Meghalaya 8th Class Syllabus 2024 Accordance with the NCERT Based Guidelines and helps Students to get an Overview of the Hindi, English Medium All Subject, MBOSE keeps a Class Exam Pattern with the aim to Provide a Quality Education for All Students, On the basis of the Current Educational Demands


登录 *


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