Topcodersrm653div.2500

2020-11-09 来源：汇意旅游网

题意: 两个人玩石头剪刀布，你知道对方每次要出什么，有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<(n);++i)
 #define FOR(i,l,h) for(i=(l);i<=(h);++i)
 #define FORD(i,h,l) for(i=(h);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<2005;i++)
 fact[i]=i*fact[i-1]%mod;
 }
 ll modf(ll n, ll p, ll & e)
 {
 e = 0;
 if(n==0) return 1;
 ll res = modf(n/p, p, e);
 e += n/p;
 if(n/p % 2 != 0) return res*(p - fact[n%p]) % p;
 return res * fact[n%p]%p;
 }
 ll modc(ll n, ll k, ll p)
 {
 if(n < 0 || k < 0 || n < k) return 0;
 ll e1, e2, e3;
 ll a1 = modf(n, p, e1), a2 = modf(k, p, e2), a3 = modf(n-k, p, e3);
 if(e1 > 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<(n);++i)
 #define FOR(i,l,h) for(i=(l);i<=(h);++i)
 #define FORD(i,h,l) for(i=(h);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 < score) return 0;
 memset(dp, 0, sizeof(dp));
 for(int i = 1; i <= len; ++i) {
 for(int j = 0; j <= i; ++j) {
 if(i == 1 || j == i) dp[i][j] = 1;
 else dp[i][j] = (dp[i-1][j] + dp[i-1][j-1]) % mod;
 }
 }
 ll ans = dp[len][score]*cal(2, len-score, mod) % mod;
 return ans;
 }

显示全文

全部栏目

Topcodersrm653div.2500