当前位置:网站首页>Educational Codeforces Round 116 (Rated for Div. 2) E. Arena
Educational Codeforces Round 116 (Rated for Div. 2) E. Arena
2022-07-05 05:31:00 【solemntee】
d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k] The maximum value is i i i The length is j j j Less than j − 1 j-1 j−1 The number of is k k k individual
After considering a round, the state changes to d p [ i − ( j − 1 ) ] [ j − k ] [ . . . ] dp[i-(j-1)][j-k][...] dp[i−(j−1)][j−k][...], Therefore, the transfer is
d p [ i ] [ j ] [ k ] = ∑ ( C j k ∗ ( j − 1 ) k ∗ d p [ i − ( j − 1 ) ] [ j − k ] [ l ] ) dp[i][j][k]=\sum(C^k_j*(j-1)^k*dp[i-(j-1)][j-k][l]) dp[i][j][k]=∑(Cjk∗(j−1)k∗dp[i−(j−1)][j−k][l])
Find out k k k It has nothing to do with the transfer and scrolls directly .
#include<bits/stdc++.h>
using namespace std;
int dp[505][505];
const int mod=998244353;
long long poww(long long a,long long b)
{
long long t=1;
if(b==0)return 1;
while(b>1)
{
if(b%2==1)t=(t*a)%mod;
a=a*a%mod;
b/=2;
}
return a*t%mod;
}
long long P1[1005],P2[1005];
void init()
{
P1[0]=1;
P2[0]=1;
for(int i=1;i<=505;i++)P1[i]=(P1[i-1]*i)%mod;
for(int i=1;i<=505;i++)P2[i]=(P2[i-1]*poww(i,mod-2))%mod;
}
int main()
{
init();
int n,x;
scanf("%d%d",&n,&x);
for(int i=1;i<=x;i++)
for(int j=1;j<=n;j++)
for(int k=0;k<j;k++)
{
if(j==1)dp[i][j]+=1;
else if(j==i&&k!=j-1)continue;
else if(j>i)continue;
else
{
dp[i][j]=(dp[i][j]+poww(j-1,k)*P1[j]%mod*P2[k]%mod*P2[j-k]%mod*dp[i-j+1][j-k])%998244353;
}
}
///
// for(int i=1;i<=x;i++)
// for(int j=1;j<=n;j++)
// for(int k=0;k<j;k++)
// {
// printf("%d %d %d %lld\n",i,j,k,dp[i][j][k]);
// }
long long ans=0;
for(int i=1;i<=x;i++)
{
ans=(ans+dp[i][n])%998244353;
}
printf("%lld",((poww(x,n)-ans)%mod+mod)%mod);
return 0;
}
边栏推荐
- Binary search basis
- 剑指 Offer 58 - II. 左旋转字符串
- Haut OJ 1218: maximum continuous sub segment sum
- kubeadm系列-01-preflight究竟有多少check
- sync.Mutex源码解读
- Kubedm series-00-overview
- Download xftp7 and xshell7 (official website)
- Sword finger offer 09 Implementing queues with two stacks
- 【ES实战】ES上的native realm安全方式使用
- Pointnet++学习
猜你喜欢
Acwing 4300. Two operations
To the distance we have been looking for -- film review of "flying house journey"
YOLOv5添加注意力機制
剑指 Offer 58 - II. 左旋转字符串
[to be continued] [UE4 notes] L1 create and configure items
Light a light with stm32
YOLOv5-Shufflenetv2
Graduation project of game mall
The present is a gift from heaven -- a film review of the journey of the soul
Fragment addition failed error lookup
随机推荐
Download xftp7 and xshell7 (official website)
TF-A中的工具介绍
[es practice] use the native realm security mode on es
YOLOv5添加注意力機制
全国中职网络安全B模块之国赛题远程代码执行渗透测试 //PHPstudy的后门漏洞分析
sync.Mutex源码解读
[merge array] 88 merge two ordered arrays
To the distance we have been looking for -- film review of "flying house journey"
[speed pointer] 142 circular linked list II
PMP candidates, please check the precautions for PMP examination in July
第六章 数据流建模—课后习题
Kubedm series-00-overview
Palindrome (csp-s-2021-palin) solution
每日一题-无重复字符的最长子串
数仓项目的集群脚本
【ES实战】ES上的native realm安全方式使用
Sword finger offer 05 Replace spaces
Haut OJ 1352: string of choice
PC寄存器
SDEI初探-透过事务看本质