提出 #19001337


ソースコード 拡げる

Copy
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define FORR2(x,y,arr) for(auto& [x,y]:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
template<class T> bool chmax(T &a, const T &b) { if(a<b){a=b;return 1;}return 0;}
template<class T> bool chmin(T &a, const T &b) { if(a>b){a=b;return 1;}return 0;}
//-------------------------------------------------------

int N,K;
const ll mo=998244353;
ll dp[41][41][41][41];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll hoge(int turn,int pre,int suf,int cur) {
	//cout<<turn<<" "<<pre<<" "<<suf<<" "<<cur<<" "<<endl;
	if(dp[turn][pre][suf][cur]>=0) return dp[turn][pre][suf][cur];
	ll ret=0;

	int ball=K-(N-(1+pre+suf));
	int cand=K-turn;
	
	if(ball<=0) return 0;
	
	ll ok=ball*modpow(cand)%mo;
	ll ng=(mo+1-ok)%mo;
	
	if(ball>=cand) ok=1,ng=0;
	
	if(cur==pre) {
		ret=ok;
		if(ng) ret+=ng*hoge(turn,pre,suf,cur+1)%mo;
	}
	else if(cur==pre+1+suf) {
		ret=hoge(turn+1,pre,suf,0);
	}
	else if(cur<pre) {
		// pre or suf
		ret=ok*hoge(turn,pre-1,suf,cur);
		if(ng) ret+=ng*hoge(turn,pre,suf,cur+1)%mo;
	}
	else {
		ret=ok*hoge(turn,pre,suf-1,cur);
		if(ng) ret+=ng*hoge(turn,pre,suf,cur+1)%mo;
	}
	
	
	
	return dp[turn][pre][suf][cur]=(ret%mo+mo)%mo;
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	MINUS(dp);
	
	FOR(i,N) {
		cout<<hoge(0,i,N-(i+1),0)<<endl;
	}
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}

提出情報

提出日時
問題 D - Shopping
ユーザ kmjp
言語 C++ (GCC 9.2.1)
得点 1300
コード長 1911 Byte
結果 AC
実行時間 57 ms
メモリ 25768 KB

コンパイルエラー

./Main.cpp: In function ‘void solve()’:
./Main.cpp:66:8: warning: unused variable ‘j’ [-Wunused-variable]
   66 |  int i,j,k,l,r,x,y; string s;
      |        ^
./Main.cpp:66:10: warning: unused variable ‘k’ [-Wunused-variable]
   66 |  int i,j,k,l,r,x,y; string s;
      |          ^
./Main.cpp:66:12: warning: unused variable ‘l’ [-Wunused-variable]
   66 |  int i,j,k,l,r,x,y; string s;
      |            ^
./Main.cpp:66:14: warning: unused variable ‘r’ [-Wunused-variable]
   66 |  int i,j,k,l,r,x,y; string s;
      |              ^
./Main.cpp:66:16: warning: unused variable ‘x’ [-Wunused-variable]
   66 |  int i,j,k,l,r,x,y; string s;
      |                ^
./Main.cpp:66:18: warning: unused variable ‘y’ [-Wunused-variable]
   66 |  int i,j,k,l,r,x,y; string s;
      |                  ^
./Main.cpp: In function ‘int main(int, char**)’:
./Main.cpp:6:28: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    6 | #define FOR(x,to) for(x=0;x<(to);x++)
      |                            ^
./Main.cpp:81:38: note: in expansion of macro ‘FOR’
   81 |  FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
      |                                      ^~~

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 1300 / 1300
結果
AC × 3
AC × 28
セット名 テストケース
Sample example0.txt, example1.txt, example2.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, example0.txt, example1.txt, example2.txt
ケース名 結果 実行時間 メモリ
000.txt AC 22 ms 25572 KB
001.txt AC 19 ms 25592 KB
002.txt AC 28 ms 25540 KB
003.txt AC 31 ms 25544 KB
004.txt AC 34 ms 25656 KB
005.txt AC 45 ms 25768 KB
006.txt AC 49 ms 25572 KB
007.txt AC 53 ms 25680 KB
008.txt AC 55 ms 25684 KB
009.txt AC 57 ms 25716 KB
010.txt AC 54 ms 25692 KB
011.txt AC 56 ms 25568 KB
012.txt AC 23 ms 25584 KB
013.txt AC 19 ms 25748 KB
014.txt AC 25 ms 25732 KB
015.txt AC 22 ms 25732 KB
016.txt AC 43 ms 25608 KB
017.txt AC 27 ms 25716 KB
018.txt AC 28 ms 25596 KB
019.txt AC 20 ms 25688 KB
020.txt AC 29 ms 25672 KB
021.txt AC 49 ms 25660 KB
022.txt AC 27 ms 25712 KB
023.txt AC 42 ms 25748 KB
024.txt AC 36 ms 25672 KB
example0.txt AC 20 ms 25688 KB
example1.txt AC 23 ms 25588 KB
example2.txt AC 36 ms 25756 KB