Topcoder 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>