1.花
（flower.cpp/c/pas）
【问题描述】
商店里出售n种不同品种的花。为了装饰桌面，你打算买m支花回家。你觉得放两支一样的花很难看，因此每种品种的花最多买1支。求总共有几种不同的买花的方案？答案可能很大，输出答案mod p的值。
【输入格式】
一行3个整数n，m，p，意义如题所述。
【输出格式】
一个整数，表示买花的方案数。
【输入输出样例1】
|
flower.in |
flower.out |
|
4 2 |
1 |
见选手目录下的flower / flower1.in与flower /
flower1.out
【输入输出样例1说明】
用数字1,2,3,4来表示花的种类的话，4种花里买各不相同的2支的方案有(1,2)、(1,3)、(1,4)、(2,3)、(2,4)、(3,4)，共6种方案，模5后余数是1。
【输入输出样例2】
见选手目录下的flower / flower2.in与flower /
flower2.out
【数据范围】
对于30%的数据，n,m≤10
对于50%的数据，n,m≤1000
对于80%的数据，1≤m≤n≤50,000
对于100%的数据，1≤m≤n≤1,000,000，p≤1,000,000,000
暴力
/*
求组合数取膜
因为有÷ 显然直接摸是搞不定的
开始用扩展欧几里得写了逆元
后来发现不互质的时候无解
这样求不出逆元....
然后想用欧拉定理 情况差不多
而且吧 边乘边%会导致答案错误
在这里发现了问题的关键....
好吧我是蒟蒻写到这才发现..
举个栗子 比如 C(8,7)
(8*7*6*5*4*3*2)/(1*2*3*4*5*6*7)%7
本来7 7可以约掉 但是%一下就成0了...
换思路 直接暴力质因数分解吧
先筛下素数 然后分解的时候加个特盘什么的
能卡过去 最后两个点都0.8s
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1000010
#define ll long long
using namespace std;
int n,m,p,a[maxn],x,y,ans=,prime[maxn],num,P[maxn];
bool f[maxn];
void gcd(ll a,ll b){
if(b==){x=;y=;return;}
gcd(b,a%b);ll tmp=x;x=y;y=tmp-a/b*y;
}
void Get(){
for(int i=;i<=;i++){
if(f[i]==)prime[++num]=i,P[i]=num;
for(int j=;j<=num;j++){
if(i*prime[j]>)break;
f[i*prime[j]]=;
if(i%prime[j]==)break;
}
}
}
ll qm(ll a,ll b,ll c){
ll r=;
while(b){
if(b&)r*=a,r%=c;
b>>=;a*=a;a%=c;
}
return r;
}
void Insert1(ll x){
for(int i=;i<=num;i++){
if(x%prime[i]==){
ll cnt=;
while(x%prime[i]==)x/=prime[i],cnt++;
a[i]+=cnt;
}
if(x==)break;
if(f[x]==){
a[P[x]]++;break;
}
}
}
void Insert2(ll x){
for(int i=;i<=num;i++){
if(x%prime[i]==){
int cnt=;
while(x%prime[i]==)x/=prime[i],cnt++;
a[i]-=cnt;
}
if(x==)break;
if(f[x]==){
a[P[x]]--;break;
}
}
}
int main()
{
freopen("flower.in","r",stdin);
freopen("flower.out","w",stdout);
cin>>n>>m>>p;Get();
for(int i=;i<=n;i++)Insert1(i);
for(int i=;i<=m;i++)Insert2(i);
for(int i=;i<=n-m;i++)Insert2(i);
for(int i=;i<=num;i++){
if(a[i]>)ans=ans*qm(prime[i],a[i],p)%p;
if(a[i]<){
gcd(qm(prime[i],-a[i],p),p);
ans=ans*x%p;
}
} cout<<ans<<endl;
return ;
}
XXX（数学公式）
/*
然后身边学过数竞的孩子说求阶乘里有几个素数有别的方法
n!里p的个数=n/p+n/p*p+n/p*p*p.....知道p==n
知道这个就快了嘛 嗖嗖的.....
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1000010
#define ll long long
using namespace std;
ll n,m,p,a[maxn],x,y,ans=,prime[maxn],num,P[maxn];
bool f[maxn];
void Get(){
for(int i=;i<=;i++){
if(f[i]==)prime[++num]=i,P[i]=num;
for(int j=;j<=num;j++){
if(i*prime[j]>)break;
f[i*prime[j]]=;
if(i%prime[j]==)break;
}
}
}
ll qm(ll a,ll b,ll c){
ll r=;
while(b){
if(b&)r*=a,r%=c;
b>>=;a*=a;a%=c;
}
return r;
}
int main()
{
freopen("flower.in","r",stdin);
freopen("flower.out","w",stdout);
cin>>n>>m>>p;Get();
for(int i=;i<=num;i++){
ll P=prime[i];
while(P<=n){
a[i]+=n/P;
P*=prime[i];
}
}
for(int i=;i<=num;i++){
ll P=prime[i];
while(P<=m){
a[i]-=m/P;
P*=prime[i];
}
}
for(int i=;i<=num;i++){
ll P=prime[i];
while(P<=n-m){
a[i]-=(n-m)/P;
P*=prime[i];
}
}
for(int i=;i<=num;i++)
ans=ans*qm(prime[i],a[i],p)%p;
cout<<ans<<endl;
return ;
}
2.圆桌游戏
（game.cpp/c/pas）
【问题描述】
有一种圆桌游戏是这样进行的：n个人围着圆桌坐成一圈，按顺时针顺序依次标号为1号至n号。对1<i<n的i来说，i号的左边是i+1号，右边是i-1号。1号的右边是n号，n号的左边是1号。每一轮游戏时，主持人指定一个还坐在桌边的人（假设是i号），让他向坐在他左边的人（假设是j号）发起挑战，如果挑战成功，那么j离开圆桌，如果挑战失败，那么i离开圆桌。当圆桌边只剩下一个人时，这个人就是最终的胜利者。
事实上，胜利者的归属是与主持人的选择息息相关的。现在，你来担任圆桌游戏的主持人，并且你已经事先知道了对于任意两个人i号和j号，如果i向j发起挑战，结果是成功还是失败。现在你想知道，如果你可以随意指定每轮发起挑战的人，哪些人可以成为最终的胜利者？
【输入】
第一行包含一个整数n，表示参加游戏的人数；
接下来n行，每行包含n个数，每个数都是0或1中的一个，若第i行第j个数是1，表示i向j发起挑战的结果是成功，否则表示挑战结果是失败。第i行第i列的值一定为0。
【输出】
一行，包含若干个数，表示可能成为最终胜利者的玩家的标号。标号按从小到大的顺序输出，相邻两个数间用1个空格隔开。
【输入输出样例1】
|
game.in |
game.out |
|
3 0 1 0 0 0 1 0 1 0 |
1 3 |
见选手目录下的game / game1.in与game /
game1.out
【输入输出样例1说明】
先指定2号向3号发起挑战，3号离开；再指定1号向2号发起挑战，2号离开。此时1号是最终胜利者。
先指定1号向2号发起挑战，2号离开；再指定1号向3号发起挑战，1号离开。此时3号是最终胜利者。
无论如何安排挑战顺序，2号都无法成为最终胜利者。
【输入输出样例2】
见选手目录下的game / game2.in与game /
game2.out
【数据规模与约定】
对于30%的数据，n≤7
对于100%的数据，n≤100
暴力
/*暴力30*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 110
using namespace std;
int n,g[maxn][maxn],f[maxn];
bool Can[maxn];
void Dfs(int now){
if(now==n){
for(int i=;i<=n;i++)
if(f[i]==)Can[i]=;
}
for(int i=;i<=n;i++)
if(f[i]==){
int x=i+;
if(x==n+)x=;
while(f[x]==){
x++;
if(x==n+)x=;
}
if(g[i][x]==){
f[x]=;Dfs(now+);f[x]=;
}
else{
f[i]=;Dfs(now+);f[i]=;
}
}
}
int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&g[i][j]);
Dfs();
for(int i=;i<=n;i++)
if(Can[i]==)printf("%d ",i);
return ;
}
正解dp
/*
正解dp吧 很巧妙地思路
关键是转化成比较好操作的题目
先把环拆成链 定义状态f[i][j]
表示i到j能不能都死掉
最后答案就是f[i][i+n]==1的
初始化 f[i][i+1]=1
然后区间dp 小区间到大区间
并且判断谁杀了谁
*/
#include<cstdio>
#define maxn 210
using namespace std;
int n,g[maxn][maxn],f[maxn][maxn],c[maxn];
int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&g[i][j]);
for(int i=;i<=n;i++)
c[i]=c[i+n]=i;
for(int i=;i<=n*;i++)
f[i][i+]=;
for(int i=*n;i>=;i--)
for(int j=i+;j<=n*;j++)
for(int k=i;k<=j;k++)
if(f[i][k]&&f[k][j]&&(g[c[i]][c[k]]||!g[c[k]][c[j]])){
f[i][j]=;break;
}
for(int i=;i<=n;i++)
if(f[i][i+n])printf("%d ",i);
return ;
}
3.兔子
（rabbit.cpp/c/pas）
【问题描述】
在一片草原上有N个兔子窝，每个窝里住着一只兔子，有M条路径连接这些窝。更特殊地是，至多只有一个兔子窝有3条或更多的路径与它相连，其它的兔子窝只有1条或2条路径与其相连。换句话讲，这些兔子窝之前的路径构成一张N个点、M条边的无向连通图，而度数大于2的点至多有1个。
兔子们决定把其中K个兔子窝扩建成临时避难所。当危险来临时，每只兔子均会同时前往距离它最近的避难所躲避，路程中花费的时间在数值上等于经过的路径条数。为了在最短的时间内让所有兔子脱离危险，请你安排一种建造避难所的方式，使最后一只到达避难所的兔子所花费的时间尽量少。
【输入】
第一行有3个整数N，M，K，分别表示兔子窝的个数、路径数、计划建造的避难所数。
接下来M行每行三个整数x,y，表示第x个兔子窝和第y个兔子窝之间有一条路径相连。任意两个兔子窝之间至多只有1条路径。
【输出】
一个整数，表示最后一只到达避难所的兔子花费的最短时间。
【输入输出样例1】
|
rabbit.in |
rabbit.out |
|
5 5 2 1 2 2 3 1 4 1 5 4 5 |
1 |
见选手目录下的rabbit / rabbit1.in与rabbit /
rabbit1.out
【输入输出样例1说明】
在第2个和第5个兔子窝建造避难所，这样其它兔子窝的兔子最多只需要经过1条路径就可以到达某个避难所。
【输入输出样例2】
见选手目录下的rabbit / rabbit2.in与rabbit /
rabbit2.out
【数据规模与约定】
对于30%的数据，N≤15，K≤4；
对于60%的数据，N≤100；
对于100%的数据，1≤K≤N≤1,000，1≤M≤1,500
暴力
/*暴力30*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1010
using namespace std;
int n,m,k,f[maxn][maxn],c[maxn],ans=0x7fffffff;
bool vis[maxn];
void Solve(){
int r=;
for(int i=;i<=n;i++){
int mx=0x3f3f3f3f;
for(int j=;j<=c[];j++)
mx=min(mx,f[i][c[j]]);
r=max(r,mx);
}
ans=min(ans,r);
}
void Dfs(int now){
if(now==k+){
Solve();
return;
}
for(int i=;i<=n;i++)
if(vis[i]==){
vis[i]=;c[++c[]]=i;
Dfs(now+);
c[]--;vis[i]=;
}
}
void Floyed(){
for(int k=;k<=n;k++)
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
int main()
{
freopen("rabbit.in","r",stdin);
freopen("rabbit.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
int u,v;
memset(f,/,sizeof(f));
for(int i=;i<=m;i++){
scanf("%d%d",&u,&v);
f[u][v]=f[v][u]=;
}
for(int i=;i<=n;i++)f[i][i]=;
Floyed();Dfs();
printf("%d\n",ans);
return ;
}
正解二分
/*
正解二分（好吧很容易想到）
只不过Judge的时候不好想
而且怎么用上那个度>=3的点不超过1个呢
不妨把这个点看成中心的点
上下的出去的要么是链 要么是连回来的环
嗯这就好办了
先预处理所有连出去的的长度以及是不是环
然后二分答案 算出最少搞几个窝
judge的时候注意 中心不一定选
所以我们枚举第一个选的在哪条路上
在枚举位置 这么这条路来说
如果是链 除去头上的枚举的s 以及最后的t
中间p[i].len-s-t要覆盖 而且每个区间长度是 2*t+1
再加上开始选的那个
如果是环 上面的情况在-(t-s)这是连回来的 靠近中心的那部分点
他们可以从中心到达最开始枚举的那个窝
剩下的那些类似的处理 长度是+s 而不是-s了
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1510
using namespace std;
int n,m,k,num,head[maxn],r[maxn],cnt,root,f[maxn],ans;
struct node{
int len,cir;
}p[maxn];
struct edge{
int v,pre;
}e[maxn*];
void Add(int from,int to){
num++;e[num].v=to;
e[num].pre=head[from];
head[from]=num;
}
void Dfs(int now,int from){
p[cnt].len++;
for(int i=head[now];i;i=e[i].pre){
int v=e[i].v;
if(v==from)continue;
if(f[v]==){
f[v]=;Dfs(v,now);
}
else if(v==root)p[cnt].cir=;
}
}
int Cal(int len,int t){
if(len<=)return ;
return (len-)/(*t+)+;
}
bool Judge(int t){
int mx=0x3f3f3f3f;
for(int i=;i<=cnt;i++){
for(int s=;s<=t&&s<=p[i].len;s++){
int tot=;
if(p[i].cir==)tot=Cal(p[i].len-s-t,t);
else tot=Cal(p[i].len-s-t-(t-s),t);
tot++;
for(int j=;j<=cnt;j++){
if(i==j)continue;
if(p[j].cir==)tot+=Cal(p[j].len+s-t,t);
else tot+=Cal(p[j].len+s-t-(t-s),t);
}
mx=min(mx,tot);
}
}
return mx<=k;
}
int main()
{
freopen("rabbit.in","r",stdin);
freopen("rabbit.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
int u,v;root=;
for(int i=;i<=m;i++){
scanf("%d%d",&u,&v);
Add(u,v);Add(v,u);
r[u]++;r[v]++;
if(r[u]>=)root=u;
if(r[v]>=)root=v;
}
f[root]=;
for(int i=head[root];i;i=e[i].pre){
int v=e[i].v;
if(f[v]==){
f[v]=;cnt++;
Dfs(v,root);
}
}
int l=,r=0x3f3f3f3f;
while(l<=r){
int mid=(l+r)/;
if(Judge(mid)){
r=mid-;ans=mid;
}
else l=mid+;
}
printf("%d\n",ans);
return ;
}
/*
5 5 1
1 2
2 4
2 3
3 5
4 5
*/