데이터 베이스 MySQL 튜토리얼 Topcoder srm 653 div.2 500

Topcoder srm 653 div.2 500

Jun 07, 2016 pm 03:44 PM
500

题意: 两个人玩石头剪刀布,你知道对方每次要出什么,有n(1~2000)局, 每局如果你赢了得1分,否则不得分,问你拿到某个分 score (0~2000)的方案数有多少。 0:石头, 1:布, 2:剪刀. 思路: 一开始想到的是组合数学的方法.每一局得分的情况只有一个,但是不得分的

题意:

两个人玩石头剪刀布,你知道对方每次要出什么,有n(1~2000)局, 每局如果你赢了得1分,否则不得分,问你拿到某个分值score(0~2000)的方案数有多少。0:石头, 1:布, 2:剪刀.

思路:

一开始想到的是组合数学的方法.每一局得分的情况只有一个,但是不得分的情况有两个,所以是任选score局*2...

但是要mod(1e9+7), 除数用mod, 要用逆元..

AC.

    #line 7 "RockPaperScissorsMagicEasy.cpp"
    #include <cstdlib>
    #include <cctype>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    #include <string>
    #include <iostream>
    #include <sstream>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <fstream>
    #include <numeric>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stdexcept>
    #include <functional>
    #include <utility>
    #include <ctime>

    using namespace std;

    #define PB push_back
    #define MP make_pair

    #define REP(i,n) for(i=0;i=(l);--i)

    typedef vector<int> VI;
    typedef vector<string> VS;
    typedef vector<double> VD;
    typedef int LL;
    typedef pair<int> PII;
    typedef long long ll;

    class RockPaperScissorsMagicEasy
    {
            public:
            ll fact[2005];
            const int mod = 1e9+7;
            RockPaperScissorsMagicEasy()
            {
                fact[0]=1;
                for(int i=1;i e2+e3) return 0;
                return a1*mod_inverse(a2*a3%p,p)%p;
            }
            ll extgcd(ll a,ll b,ll &x,ll &y)
            {
                ll d=a;
                if(b)
                {
                    d=extgcd(b,a%b,y,x);
                    y-=(a/b)*x;
                }
                else
                {
                    x=1;y=0;
                }
                return d;
            }
            ll mod_inverse(ll a,ll m)
            {
                ll  x,y;
                extgcd(a,m,x,y);
                return (m+x%m)%m;
            }
            ll mod_pow(ll a,ll n)
            {
                ll ans=1,b=a;
                while(n)
                {
                    if(n&1) ans=ans*b%mod;
                    n>>=1;
                    b=b*b%mod;
                }
                return ans;
            }

            int count(vector <int> card, int score)
            {
                int t = card.size();
                //printf("%d\n", t);
                if(score > t) return 0;
                if(score == t) return 1;
                if(score == 0) {
                    return t*2;
                }
                int ans=modc(t,score,mod)*mod_pow(2,t-score)%mod;
                return ans;
            }</int></int></double></string></int></ctime></utility></functional></stdexcept></list></bitset></iomanip></numeric></fstream></stack></queue></set></map></sstream></iostream></string></vector></algorithm></cmath></cstdio></cstring></cctype></cstdlib>
로그인 후 복사


第二种方法是DP.

dp[i][j]: 表示第i局中有j局得分的方案数. dp[i][j] = (dp[i-1][j] + dp[i-1][j-1]) % mod

AC.

  #line 7 "RockPaperScissorsMagicEasy.cpp"
    #include <cstdlib>
    #include <cctype>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    #include <string>
    #include <iostream>
    #include <sstream>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <fstream>
    #include <numeric>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stdexcept>
    #include <functional>
    #include <utility>
    #include <ctime>

    using namespace std;

    #define PB push_back
    #define MP make_pair

    #define REP(i,n) for(i=0;i=(l);--i)

    typedef vector<int> VI;
    typedef vector<string> VS;
    typedef vector<double> VD;
    typedef long long ll;
    typedef pair<int> PII;

    class RockPaperScissorsMagicEasy
    {
            public:
            ll dp[2005][2005];
            ll cal(ll a, ll n, ll mod)
            {
                ll s = 1;
                while(n > 0) {
                    if(n&1) s = s*a%mod;
                    a = a*a%mod;
                    n >>= 1;
                }
                return s;
            }
            int count(vector <int> card, int score)
            {
                int len = card.size();
                ll mod = 1e9+7;
                if(len <br>
<br>



</int></int></double></string></int></ctime></utility></functional></stdexcept></list></bitset></iomanip></numeric></fstream></stack></queue></set></map></sstream></iostream></string></vector></algorithm></cmath></cstdio></cstring></cctype></cstdlib>
로그인 후 복사
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

Video Face Swap

Video Face Swap

완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

500내부 서버 오류는 무엇을 의미하나요? 500내부 서버 오류는 무엇을 의미하나요? Feb 21, 2023 pm 03:39 PM

500 내부 서버 오류는 HTTP 500 내부 서버 오류를 의미합니다. 이는 서버가 예상치 못한 상황에 직면하여 요청을 이행할 수 없지만 오류 발생 시 특정 오류나 오류의 근본 원인을 설명할 수 없음을 의미합니다. 방문한 웹사이트에 오류가 표시됩니다.

영국인들은 £2,500 상당의 희귀한 50p 동전을 집에서 확인하라고 촉구했습니다. 영국인들은 £2,500 상당의 희귀한 50p 동전을 집에서 확인하라고 촉구했습니다. Oct 28, 2024 pm 04:20 PM

한 전문가에 따르면 2011년 작품은 2012년 런던 올림픽을 기념하기 위해 제작된 것이라고 합니다.

이더리움(ETH) 가격은 2,320달러 이상으로 회복되었지만 속도를 높이기 위해 고군분투하고 있습니다. 이더리움(ETH) 가격은 2,320달러 이상으로 회복되었지만 속도를 높이기 위해 고군분투하고 있습니다. Sep 10, 2024 pm 03:20 PM

이더리움 가격은 2,250달러 수준을 넘어 회복세를 시작했습니다. ETH는 2,280달러 저항 구역을 통과하여 플러스 구역으로 진입할 수 있었지만 비트코인에 비해 모멘텀은 약했습니다.

비트코인(BTC) 가격 분석: BTC는 $60,000를 목표로 상당한 상승 움직임을 시작합니다. 비트코인(BTC) 가격 분석: BTC는 $60,000를 목표로 상당한 상승 움직임을 시작합니다. Sep 12, 2024 pm 06:35 PM

비트코인은 $57,500 저항선을 넘어 상당한 상승세를 시작했으며 이제 잠재적으로 $60,000 선에 도달할 가능성이 있는 조짐을 보여주고 있습니다.

BetMGM Michigan 보너스 코드 MLIVEMGM: $1,500의 첫 번째 베팅 제안 받기 BetMGM Michigan 보너스 코드 MLIVEMGM: $1,500의 첫 번째 베팅 제안 받기 Nov 18, 2024 am 03:36 AM

신규 플레이어는 BetMGM 환영 보너스를 청구할 수 있으며 프로모션 코드 MLIVEMGM을 사용하여 보너스 베팅으로 최대 $1,500를 돌려받을 수 있습니다.

영국인들은 희귀 버전이 £2.5k의 엄청난 가치가 있을 수 있으므로 50p 동전을 확인하도록 촉구했습니다. 영국인들은 희귀 버전이 £2.5k의 엄청난 가치가 있을 수 있으므로 50p 동전을 확인하도록 촉구했습니다. Oct 28, 2024 pm 04:24 PM

2012년 런던 올림픽을 기념하여 주조된 2011년 동전은 "수영" 디자인으로 알려져 있으며 수영선수의 이미지를 담고 있습니다.

Rexas Finance(RXS): 솔라나(SOL) 및 이더리움(ETH)의 잠재적 경쟁자 Rexas Finance(RXS): 솔라나(SOL) 및 이더리움(ETH)의 잠재적 경쟁자 Nov 04, 2024 pm 06:44 PM

끝없는 블록체인 기술 경쟁에서 솔라나(SOL)와 이더리움(ETH) 두 가지가 눈에 띄고 투자자의 관심을 끌었습니다.

솔라나 가격은 $4,500에 도달할 수 있습니다 솔라나 가격은 $4,500에 도달할 수 있습니다 Oct 22, 2024 am 06:42 AM

SOL은 주간 차트에서 컵 앤 핸들 패턴을 형성했는데, 이는 솔라나 가격이 2,600% 급등하여 4,500달러까지 상승할 수 있음을 보여줍니다.

See all articles