QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#56911#4814. Exciting TravelKING_UT#WA 148ms979176kbC++202.2kb2022-10-21 21:19:522022-10-21 21:19:54

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-21 21:19:54]
  • 评测
  • 测评结果:WA
  • 用时:148ms
  • 内存:979176kb
  • [2022-10-21 21:19:52]
  • 提交

answer

#include <bits/stdc++.h>
#define SIZE 300005
#define MX 200
#define MX2 2200
using namespace std;

using ll=long long;

using uint=unsigned;
const uint mod=998244353;
struct mint{
	uint v;
	mint(ll vv=0){s(vv%mod+mod);}
	mint& s(uint vv){
		v=vv<mod?vv:vv-mod;
		return *this;
	}
	mint operator -()const{return mint()-*this;}
	mint& operator+=(const mint&r){return s(v+r.v);}
	mint& operator-=(const mint&r){return s(v+mod-r.v);} 
	mint& operator*=(const mint&r){v=(unsigned ll)v*r.v%mod;return *this;}
	mint& operator/=(const mint&r){return *this*=r.inv();}
	
	mint operator+(const mint&r)const{return mint(*this)+=r;}
	mint operator-(const mint&r)const{return mint(*this)-=r;}
	mint operator*(const mint&r)const{return mint(*this)*=r;}
	mint operator/(const mint&r)const{return mint(*this)/=r;}
	
	mint pow(ll n)const{
		if(n<0)return inv().pow(-n);
		mint res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	mint inv()const{return pow(mod-2);}
	
	bool operator<(mint r)const{return v<r.v;}
};
mint dp1[2][SIZE][MX],dp2[2][SIZE][MX];
mint dp[MX2][MX2],bef[MX2][MX2];

int main(){
	int n,c;
	scanf("%d%d",&n,&c);
	int k=min(n,150);
	int pos=0;
	mint ret=0;
	for(int L=1;L<=k;L++){
		int mx=min(n,L*(L+1)/2);
		pos=1-pos;
		if(pos==1){
			dp1[pos][1][1]=1;
		} else{
			for(int s=1;s<=mx;s++){
				for(int i=1;i<=min(s,L);i++){
					dp1[pos][s][i]=dp1[pos^1][s-i][i+1]*c;
					if(i>1&&(L==2||i>2)) dp1[pos][s][i]+=dp1[pos^1][s-i][i-1];
					dp2[pos][s][i]=dp2[pos^1][s-i][i+1];
					if(i>1) dp2[pos][s][i]+=dp2[pos^1][s-i][i-1]*c;
				}
			}
		}
		for(int s=1;s<=mx;s++){
			for(int i=1;i<=min(s,L);i++){
				dp2[pos][s][1]+=dp1[pos][s][i];
			}
			for(int i=1;i<=min(s,L);i++){
				if((n-s)%L==0){
					ret+=dp2[pos][s][i];
				}
			}
		}
	}
	int mx=n/k+k;
	for(int s=k;s<=n;s++){
		int id=s%(mx+1);
		for(int i=1;i<=mx;i++){
			dp[id][i]=dp[(s-i+mx+1)%(mx+1)][i+1];
			if(i>1) dp[id][i]+=dp[(s-i+mx+1)%(mx+1)][i-1]*c;
			bef[id][i]=dp2[pos][s][i];
			bef[id][i]+=bef[(id-k+mx+1)%(mx+1)][i-1];
			if(s>=i){
				dp[id][i]+=bef[(s-i+mx+1)%(mx+1)][i+1];
				if(i>1) dp[id][i]+=bef[(s-i+mx+1)%(mx+1)][i-1]*c;
			}
			if(s==n) ret+=dp[n][i];
		}
	}
	printf("%u\n",ret.v);
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 148ms
memory: 979176kb

input:

5 3
1 2
1 3
2 4
2 5
3 1 4 5
4 1 2 4 3
4 2 4 5 1

output:

5

result:

wrong answer 1st numbers differ - expected: '1', found: '5'