欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  数据库

Topcoder srm 653 div.2 500

程序员文章站 2022-06-06 08:18:48
...

题意: 两个人玩石头剪刀布，你知道对方每次要出什么，有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 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 

    using namespace std;

    #define PB push_back
    #define MP make_pair

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

    typedef vector VI;
    typedef vector VS;
    typedef vector VD;
    typedef int LL;
    typedef pair 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  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;
            }


第二种方法是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 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 

    using namespace std;

    #define PB push_back
    #define MP make_pair

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

    typedef vector VI;
    typedef vector VS;
    typedef vector VD;
    typedef long long ll;
    typedef pair 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  card, int score)
            {
                int len = card.size();
                ll mod = 1e9+7;
                if(len
相关标签： Topcoder srm 653 div.2 500 题意

上一篇： PostgreSQL空值null参与运算的处理方法

下一篇： 【求助】php sleep()导致所有网页都没响应了

推荐阅读