2019.01.05【NOIP提高組】模拟 B組

遲到的解題報告

• JZOJ 3057 電影票
• • 題目大意
  • 分析
  • 代碼
• JZOJ 3058 火炬手
• • 題目
  • 分析
• JZOJ 3059 雕塑
• • 題目
  • 分析
  • 代碼

JZOJ 3057 電影票

題目大意

由n個a和m個b組成的序列，它的任意字首 a的個數大于b的個數，這樣的序列有多少個？

分析

首先它的答案是 c ( n + m , n ) − c ( n + m , n + 1 ) c(n+m,n)-c(n+m,n+1) c(n+m,n)−c(n+m,n+1)。

第一個很容易了解，n+m個選出n個當a

那第二個怎麼解釋，那應該是減掉不合法的，考慮一個由n個a和m個b組成的不合法序列，肯定存在一個n=m-1的狀态，這時隻要轉換a和b，使其變為m=n-1的狀态，就可以使序列合法，那麼目前序列是由n+1個a和m-1 個b組成，是以說就是 c ( n + m , n + 1 ) c(n+m,n+1) c(n+m,n+1)

但是這樣普通的高精乘除很慢，那麼就要盡量優化，那麼就是 n + 1 − m m c ( n + m , n + 1 ) = ( n + 1 − m ) ( n + m ) ! ( n + 1 ) ! m ! \frac{n+1-m}{m}c(n+m,n+1)=\frac{(n+1-m)(n+m)!}{(n+1)!m!} mn+1−m​c(n+m,n+1)=(n+1)!m!(n+1−m)(n+m)!​，可以提前對它們質因數分解，算出指數應該是多少，再用高精乘單精實作

代碼

#include <cstdio>
#define rr register
using namespace std;
typedef unsigned long long ull;
const int N=10000; const ull mod=(ull)1e12; bool flag;
int n,m,prime[N>>3],v[N+1],snt[N>>3],cnt,len; ull a[261];
inline void fj(int x,bool plmi){
	for (rr int i=1;i<=cnt&&x>1;++i)
	if (x%prime[i]==0)
	do{
		if (plmi) ++snt[i];
			else --snt[i];
		x/=prime[i];
	}while (x%prime[i]==0);
}
inline ull ksm(ull x,ull y){
	rr ull ans=1;
	while (y){
		if (y&1) ans*=x;
		x*=x; y>>=1;
	}
	return ans;
}
inline void mul(ull x){
	rr ull g=0;
	for (rr int i=1;i<=len;++i)
		g+=a[i]*x,a[i]=g%mod,g/=mod;
	while (g) a[++len]=g%mod,g/=mod;
}
inline void print(ull x){
	rr char buf[15]; rr int lenn=0;
	while (x) buf[++lenn]=x%10+48,x/=10;
	if (flag) for (rr int i=lenn+1;i<=12;++i) putchar(48);
	for (rr int i=lenn;i;--i) putchar(buf[i]); flag=1;
}
signed main(){
    for (rr int i=2;i<=N;++i){
		if (!v[i]) prime[++cnt]=i,v[i]=i;
		for (rr int j=1;j<=cnt;++j){
			if (prime[j]>N/i||prime[j]>v[i]) break;
			v[i*prime[j]]=prime[j];
		}
	}
	scanf("%d%d",&n,&m); a[++len]=1;
    if (n>m) fj(n+1-m,1);
	for (rr int i=n+2;i<=n+m;++i) fj(i,1);
	for (rr int i=2;i<=m;++i) fj(i,0);
	for (rr int i=1;i<=cnt;++i)
	if (snt[i]) mul(ksm(prime[i],snt[i]));
	for (rr int i=len;i;--i) print(a[i]);
	return 0;
}
           

JZOJ 3058 火炬手

題目

洛谷 1988 火炬 洛谷 2841 A*B Problem

分析

bfs 01串+餘數優化（相同餘數不會更優）

JZOJ 3059 雕塑

題目

将n座雕塑，準備安置在校園内，整個校園可以抽象成一個nn的大網格，每個11網格最多隻能安置一座雕塑，但是某些1*1的網格上恰好是一個食堂或湖泊，這些網格是不能安置雕塑的，每個雕塑的造型相同，這樣同一種安置方案中交換排列都算一種。任意雕塑在同一行或同一列是不合法的方案。

分析

由于不可以放的地方比較少，是以說可以用容斥原理 ∑ i = 1 m ( − 1 ) i × ( n − i ) ! × d f s ( 1 ∼ i 的 可 能 性 ) \sum_{i=1}^m(-1)^i\times (n-i)!\times dfs(1\sim i的可能性) i=1∑m​(−1)i×(n−i)!×dfs(1∼i的可能性)

代碼

#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
typedef unsigned long long ull;
ull fac[21]; int x[11],y[11],n,m; bool r[21],c[21]; 
inline signed iut(){
	rr int ans=0,f=1; rr char c=getchar();
	while (!isdigit(c)) f=(c==45)?-f:f,c=getchar();
	while (isdigit(c)) ans=ans*10+(c-48),c=getchar();
    return ans*f;
}
inline void dfs(int t,int dep,int &cnt){
	if (!dep) ++cnt;
	else for (rr int i=t+1;i<=m;++i)
	if (!r[x[i]]&&!c[y[i]]){
		r[x[i]]=c[y[i]]=1;
		dfs(i,dep-1,cnt);
		r[x[i]]=c[y[i]]=0;
	}
}
signed main(){
	n=iut(); m=iut(); rr ull ans=1; fac[0]=fac[1]=1;
	for (rr int i=1;i<=m;++i) x[i]=iut(),y[i]=iut();
	for (rr int i=2;i<=n;++i) fac[i]=(ans*=i);
	for (rr int i=1;i<=m;++i){
		rr int cnt=0; dfs(0,i,cnt);
		if (i&1) ans-=cnt*fac[n-i];
		    else ans+=cnt*fac[n-i];
	}
	printf("%llu",ans);
	return 0;
}