UPC 组队训练 5215 Fence Building（欧拉示性数）

这里写图片描述
题意：给一个圆，圆上有N个点，N个点两两连成一条直线，问最多能把这个圆分成几部分。
根据欧拉示性数常数2=V（点个数）+F（面个数）-E（边条数）。
链接：对欧式性数的解释
得到公式：F=C（n 2）+C（n，4）+1；
链接：对公式的证明
由于取模运算，有对除法的取模运算，需要用到逆元
(a + b) % p = (a%p + b%p) %p （对）
(a - b) % p = (a%p - b%p) %p （对）
(a * b) % p = (a%p * b%p) %p （对）
(a / b) % p = (a%p / b%p) %p （错）
链接：取模运算总结
最后Java大数运算AC，这里要将乘法拆开分部运算，否则Java会超时。

import java.util.*;
import java.math.*;
public class Main {

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int t;
        t=in.nextInt();
        BigInteger n,a,b,sum,m,s,f,p,q,r;
        m=BigInteger.valueOf(1000000007);
        s=BigInteger.valueOf(2);
        f=BigInteger.valueOf(24);
        p=BigInteger.valueOf(1);
        r=BigInteger.valueOf(3);
        for(int i=1;i<=t;i++)
        {
            n=in.nextBigInteger();
            a=n.multiply(n.subtract(p));
            a=a.divide(s);
            b=n.multiply(n.subtract(p));
            b=b.multiply(n.subtract(s));
            b=b.multiply(n.subtract(r));
            b=b.divide(f);
            sum=a.add(b).add(p);
            BigInteger modd = sum.mod(m);
            System.out.print("Case #");
            System.out.print(i);
            System.out.print(": ");
            System.out.println(modd);
        }
    }  
}

本文链接：https://blog.csdn.net/a17865569022/article/details/81913494

智能推荐

Fence Building UVALive - 8471 2017乌鲁木齐区域赛D题

计蒜客题目一道组队赛题目，当时猜着是有什么规律，但是我们都不太擅长找规律，gg的一道题，今天补题时第一次了解到欧拉定理，这道题目就是用欧拉定理做的。欧拉公式：V-E+F=2.其中V是顶点(即所有线段的断点数加上交点数),E是边数（即n段椭圆弧加上这些线段被切成的段数），F是面数（即土地块数加上椭圆...

【字符串哈希】UPC Contest2569 - 2020年秋季组队训练赛第六场 G:Typo

问题 G: Typo 时间限制: 10 S e c 10 Sec 10Sec 内存限制: 128 M B 128 MB 128MB 题目描述 It is now far into the future and human civilization is ancient history. Archaeologists from a distant planet have recently disco...

【DFS&反向建图&记忆化搜索】UPC Contest2592 - 2020年秋季组队训练赛第十四场问题 D: Mysterious Treasure

问题 D: Mysterious Treasure 时间限制: 1 Sec 内存限制: 128 MB 题目描述 WNJXYK and DIDIDI is playing a game. DIDIDI draws a directed graph G on the paper which contains n points, m directed edges and no cycle. WNJXYK...

upc 2020春季个人训练赛第九场

问题 A: 水题大战题目描述小Q最近正在给一个比赛出题目，他认为第一题应该是老少皆宜的。于是，他出了一个题目，然后让n个人来评价这个题目。每个人会对这个题目做出评价，有难和简单两种，1表示难，0表示简单。如果所有人都认为这个题目简单，那么这个题目就是简单的，否则这个题目就是难的。输入输入第一行是一个正整数T，表示数据的组数。接下来对于每组数据，先输入一个正整数n，表示参与评价的人的数量...

（大组合数）D. Fence Building ------ ACM-ICPC 2017 Asia Urumqi

传送门： D.Fence Building Farmer John owns a farm. He first builds a circle fence. Then, he will choose n points and build some straight fences connecting them. Next, he will feed a cow in each regio...

UPC 组队训练 5215 Fence Building（欧拉示性数）

智能推荐

猜你喜欢