题意: 两个人玩石头剪刀布，你知道对方每次要出什么，有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<(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<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef int LL;
typedef pair<int,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<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 <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;
}第二种方法是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<(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<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long ll;
typedef pair<int,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 < 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;
}
