luogu P4981 父子

题目背景

上演在各大学男生寝室的日常 ::

A :A: “我没带纸，快来厕所救我！”

B :B: “叫爸爸。”

A :A: “爸爸！”

........................................................................................

A :A: “我没钱了，能借我点吗。”

B :B: “叫爸爸。”

A :A: “爸爸！”

一个月后、

B :B: “能把钱还给我吗。”

A :A: “叫爸爸。”

B :B: “爸爸！”

题目描述

对于全国各大大学的男生寝室，总是有各种混乱的父子关系。

那么假设现在我们一个男生寝室有不同的 \(n\) 个人，每个人都至多有一个“爸爸”，可以有多个“儿子”，且有且只有一个人没有“爸爸”(毕竟是室长，还是要给点面子，当然了，室长人人当嘛)。

那么现在问题来了，对于一个有 \(n\) 个人的寝室，最多可能存在多少种父子关系，当然每个人之间都必须要有直接或间接的父子关系。

输入格式

第一行一个正整数 \(t\)，表示有组数据。

接下来 \(t\) 行，每行一个整数 \(n\)，表示有 \(n\) 个人。

输出格式

共 \(t\) 行，每行一个整数，求关系个数。

由于答案可能较大，则我们需要输出答案对 \(1e9+9\) 取模的值。

Cayley定理：过n个有标志顶点的无根树的数目等于n^(n-2)

本题要求有根，那就在原来基础上乘个n

快速幂求解

#include<cstdio>

#include<iostream>

using namespace std;

const int N=3115,mod=1e9+9;

#define int long long

#define LL long long

int ksm(LL n, LL m){

    LL ret=1;

    while(m){

        if(m&1)ret=(ret*n)%mod;

        n=n*n%mod; m>>=1;

    }

    return ret;

}

signed main(){

	int t,n;

	cin>>t;

	while(t--){

		scanf("%lld",&n);

		printf("%lld\n",ksm(n,n-1));

	}

	return 0;

}

巴特西

luogu P4981 父子

题目背景

题目描述

输入格式

输出格式

最新文章

热门文章