小红的树构造

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 488K, 提交时间: 2023-07-31 16:16:39

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int mod=1e9+7;
int n,m,k;
int q(int x,int y){
	int sum=1;
	while(y){
		if(y%2==1){
			sum*=x;
		}
		sum%=mod;
		x*=x;
		x%=mod;
		y/=2;
	}
	return sum;
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>k;
	k=max(k,n-k);
	cout<<q(4,n-k)*q(3,k-1)%mod*q(4,(k-1)*(k-2)/2)%mod*q(6,(n-k)*(n-k-1)/2)%mod*q(6,(n-k)*(k-1))%mod<<endl;;
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 420K, 提交时间: 2023-07-30 22:00:52

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
const ll m = 1000000007;

ll mi(ll x,ll y){
	ll sum=1;
	for(; y ; y >>=1 , x=x*x%m){
		if(y&1)sum=sum*x%m;
	}
	return sum;
} 

void solve(){
	ll n,k;
	cin >> n >> k;
	k=max(k,n-k);
	cout << mi(4,n-k)*mi(3,k-1)%m*mi(4,(k-1)*(k-2)/2)%m*mi(6,(n - k)*(n-k-1)/2)%m*mi(6,(n-k)*(k-1))%m;
	return ;
}

int main(){
	ll t=1;//cin >> t;
	while(t--){
		solve();
	}
	return 0;
}

pypy3 解法, 执行用时: 70ms, 内存消耗: 21188K, 提交时间: 2023-07-31 16:39:54

from sys import stdin

mod = int(1e9)+7

def qmi(a,b,p):
    res = 1
    while b:
        if b&1==1:
            res = res*a%p
        b>>=1
        a = a*a%p
    return res 

n,k = map(int,stdin.readline().split())

a = k
b = n-k

if a<b:
    a,b = b,a
    
ans = qmi(3,a-1,mod)*qmi(4,(a-1)*(a-2)//2,mod)%mod*qmi(6,(a-1)*b,mod)%mod*qmi(4,b,mod)%mod*qmi(6,b*(b-1)//2,mod)%mod

print(ans)

Python3 解法, 执行用时: 42ms, 内存消耗: 4624K, 提交时间: 2023-08-01 17:00:20

n,k=map(int,input().split())
a,b=sorted([k,n-k])
p=int(1e9)+7
c=b-1
print(pow(3,c,p)*pow(2,a+a+(c-1)*c,p)%p*pow(6,a*c+a*(a-1)//2,p)%p)

详情