search
HomeDatabaseMysql TutorialTopcoder srm 653 div.2 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>
Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
500internal server error什么意思500internal server error什么意思Feb 21, 2023 pm 03:39 PM

500internal server error的意思是HTTP 500内部服务器错误,表示服务器遇到意外情况,导致其无法履行请求,但它无法说明具体错误或发生错误的根本原因;当发生错误时,访问的网站会显示发生错误。

Ethereum (ETH) Price Recovers Above $2,320, But Struggles to Gain PaceEthereum (ETH) Price Recovers Above $2,320, But Struggles to Gain PaceSep 10, 2024 pm 03:20 PM

Ethereum price started a recovery wave above the $2,250 level. ETH was able to clear the $2,280 resistance zone to move into a positive zone, but momentum was weak compared to Bitcoin.

Bitcoin (BTC) Price Analysis: BTC Initiates Significant Upward Movement, Targets $60,000 MarkBitcoin (BTC) Price Analysis: BTC Initiates Significant Upward Movement, Targets $60,000 MarkSep 12, 2024 pm 06:35 PM

Bitcoin has initiated a significant upward movement, surpassing the $57,500 resistance level and now showing promising signs of potentially reaching the $60,000 mark.

Brits urged to check at home for rare 50p coin that could be worth £2,500Brits urged to check at home for rare 50p coin that could be worth £2,500Oct 28, 2024 pm 04:20 PM

According to one expert, the 2011 piece was minted to celebrate the London Olympics in 2012

BetMGM Michigan Bonus Code MLIVEMGM: Get a $1,500 First Bet OfferBetMGM Michigan Bonus Code MLIVEMGM: Get a $1,500 First Bet OfferNov 18, 2024 am 03:36 AM

New players can claim the BetMGM welcome bonus and get up to $1,500 paid back in bonus bets by using promo code MLIVEMGM.

The Solana Price Can Reach $4,500The Solana Price Can Reach $4,500Oct 22, 2024 am 06:42 AM

SOL has formed a cup-and-handle pattern on its weekly chart, which shows that the Solana price can surge by 2,600% and rise to $4,500.

Rexas Finance (RXS): A Potential Competitor to Solana (SOL) and Ethereum (ETH)Rexas Finance (RXS): A Potential Competitor to Solana (SOL) and Ethereum (ETH)Nov 04, 2024 pm 06:44 PM

In this never-ending race of blockchain technology, two have managed to stand out and catch investors' attention - Solana (SOL) and Ethereum (ETH).

Brits urged to check their 50p coins as rare version could be worth a huge £2.5kBrits urged to check their 50p coins as rare version could be worth a huge £2.5kOct 28, 2024 pm 04:24 PM

The 2011 coin, minted in celebration of the London Olympics in 2012, is known as the "aquatics" design and features an image of a swimmer

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
1 months agoBy尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

WebStorm Mac version

WebStorm Mac version

Useful JavaScript development tools

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

DVWA

DVWA

Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment