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>

핫 AI 도구

Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

Video Face Swap
완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

인기 기사

뜨거운 도구

메모장++7.3.1
사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전
중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경

드림위버 CS6
시각적 웹 개발 도구

SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)

500 내부 서버 오류는 HTTP 500 내부 서버 오류를 의미합니다. 이는 서버가 예상치 못한 상황에 직면하여 요청을 이행할 수 없지만 오류 발생 시 특정 오류나 오류의 근본 원인을 설명할 수 없음을 의미합니다. 방문한 웹사이트에 오류가 표시됩니다.

한 전문가에 따르면 2011년 작품은 2012년 런던 올림픽을 기념하기 위해 제작된 것이라고 합니다.

이더리움 가격은 2,250달러 수준을 넘어 회복세를 시작했습니다. ETH는 2,280달러 저항 구역을 통과하여 플러스 구역으로 진입할 수 있었지만 비트코인에 비해 모멘텀은 약했습니다.

비트코인은 $57,500 저항선을 넘어 상당한 상승세를 시작했으며 이제 잠재적으로 $60,000 선에 도달할 가능성이 있는 조짐을 보여주고 있습니다.

신규 플레이어는 BetMGM 환영 보너스를 청구할 수 있으며 프로모션 코드 MLIVEMGM을 사용하여 보너스 베팅으로 최대 $1,500를 돌려받을 수 있습니다.

2012년 런던 올림픽을 기념하여 주조된 2011년 동전은 "수영" 디자인으로 알려져 있으며 수영선수의 이미지를 담고 있습니다.

끝없는 블록체인 기술 경쟁에서 솔라나(SOL)와 이더리움(ETH) 두 가지가 눈에 띄고 투자자의 관심을 끌었습니다.

SOL은 주간 차트에서 컵 앤 핸들 패턴을 형성했는데, 이는 솔라나 가격이 2,600% 급등하여 4,500달러까지 상승할 수 있음을 보여줍니다.
