列表

详情

NC241412. 占星

描述

Background


繁星闪耀，世人的命运早已注定。
-----------------------------------------------------------------------------------------------------------
「『阿斯托洛吉斯·莫娜·梅姬斯图斯』老师的文章真是太有趣了！虽然基本看不懂，但特别有意思。」——《蒸汽鸟报》的忠实读者紫薇满怀敬意地说道。

莫娜是一位奇特的占星术士——与其他的占星术士为了赏钱可以信口雌黄不同，莫娜替人占卜向来都是分文不取，但也不会对占卜的结果加以修饰。即便是会让人不悦的结果，她也会直截了当地告诉对方：「就算你加入冒险家协会，也不会出人头地的」、「你和他没机会的，不久之后他就会远走」等等，诸如此类。

她直言不讳的性格导致来找她占卜的人骤减。莫娜对此并无不满，这让她能将更多的时间用在自己的研究上。

既然是研究，那么器具、书籍自然是必不可少的，而莫娜唯一的收入来源是为《蒸汽鸟报》的《星座相谈》专栏供稿。每当稿费到账，她总是会将钱优先用在研究上，璃月的古书、须弥的星盘······每一件都价格不菲，等她回过神时，每月剩下的稿酬勉强只够她满足温饱生活的了。

「没关系，限制物欲是占星术士修行的一部分，只有简朴地生活，才能窥探到世界的真实。」莫娜一边说，一边用咳嗽声掩盖肚子因为饥饿而发出的声响。

今天的莫娜，也在为摩拉发愁。
-----------------------------------------------------------------------------------------------------------
在提瓦特大陆众生奔忙时，
莫娜忙着计算一笔名为「生活」的账。

尽管她本人一定会否认「穷」这个说法，作出如下辩解：

太过漂亮的景象
会把最简朴的真实藏起来。
太过美味的食物
会让人忘记这东西有多少营养。
简朴的生活
是为了看破世界的真实。

提瓦特大陆众生奔忙，
连神秘的占星术士也不例外······
哦，不过吟游诗人好像真的什么都不做。

Description


伟大的占星术士莫娜决定进行一次史无前例的占卜。

这次占卜需要将一个当场构造的任意 n 边形星盘沿对角线划分成若干个区域，莫娜认为划分出来的区域越多，占卜结果就越准确，于是莫娜决定连接所有的对角线以获得最精确的占卜结果。

但是天不遂人愿——众所周知摩拉是一种重要的触媒，而莫娜在占卜即将开始的时候发现自己的摩拉不够用了，于是她只能少选择 k 条连接的对角线。

计划被打乱的莫娜现在已经焦头烂额，所以她想请你帮她计算星盘最多能被划分成多少个区域。

输入描述

两个数 n, k，含义见题面。

输出描述

一个数，其值为所求答案对  取模后的值。

示例1

输入: 

6 3

输出: 

15

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 504K, 提交时间: 2022-09-10 01:04:53 

#include <bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
int read()
{
	int x;
	cin >> x;
	return x;
}
void print(__int128 x)
{
	cout << (long long)(x%mod+mod)%mod << "\n";
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	__int128 n,k;
	n=read(),k=read();
	__int128 X=0;
	if(k>=1)
	{
		X+=n-3;
		X+=(n%mod-4)*(k%mod-1);
		if(k==n) --X;
	}
	__int128 ans=n*(n-3)/2;
	ans%=mod,ans+=n*(n-1)%mod*(n-2)%mod*(n-3)%mod*41666667%mod;
	++ans;
//	print(ans);
	print(ans-X-k); 
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 2ms, 内存消耗: 480K, 提交时间: 2022-09-09 20:39:02 

#include<cstdio>
using namespace std;
const int MOD=1e9+7;
long long n,k,inv[30];
int main(){
	scanf("%lld%lld",&n,&k);n%=MOD;k%=MOD;inv[1]=1;
	for(int i=2;i<=24;++i) inv[i]=MOD-MOD/i*1ll*inv[MOD%i]%MOD;
	printf("%lld",((1+n*(n-1)/2+n*(n-1)%MOD*(n-2)%MOD*(n-3)%MOD*inv[24]-n-(k?(n-2)+(k-1)*(n-3)-(k==n):0))%MOD+MOD)%MOD);
	return 0;
}

Python3 解法, 执行用时: 43ms, 内存消耗: 4584K, 提交时间: 2022-09-13 20:58:36 

n,k=map(int,input().split())
mod=1000000007
ans=((n-1)*(n-2)*(n*n-3*n+12)//24)%mod

if k==1:
    ans=(ans-(n-2))%mod
elif k==n:
    ans=(ans-(n-2)*(n-1)+2)%mod
elif k!=0:
    ans=(ans-(n-2)-(n-3)*(k-1))%mod

print(ans)

上一题

© 2024 nowcoder.com