Topcodersrm653div.2500

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

查看更多关于Topcodersrm653div.2500的详细内容...