Codeforces 1262F Wrong Answer on test 233(组合数)
2024-10-07 07:26:31
E1:设dp[i][j],表示在第i个位置的当前新状态超过原状态j分的方案数是dp[i][j],那么对于这种情况直接进行转移即可,如果a[i]==b[i]显然k种选择都可以,不影响j,如果不一样,这个位置填了a[i]那么状态从dp[i-1][j+1]转移过来,如果填了b[i]就是dp[i-1][j-1]转移,当然也可以两个都不填,那么剩下一共是k-2种选择,j不变,最后答案将所有超过分数为正数的加起来即可,因此总体复杂度O(nk)。
E2:我们可以从E1的递推式子中发现,新状态超过原状态的方案和原状态超过新状态的方案这两者是等价的问题,那么我们可以进行简单使用总方案数减去分数相同的方案数最后除二就是答案,那么我们可以枚举新状态一共多原状态j分,原状态一共多新状态j分,因为这两者在最后是打平的,这两者在只有在a[i]!=b[i]的时候才会发生超对方一分的情况,那么我们记num为一共有多少个a[i]!=b[i]的情况,然后我们枚举共超过对方i分,那么我们需要从num中挑i次是选择的a,再从剩下的num-i次中选择b,那么还剩下nun-2*i的部分是a[i]!=b[i],但是又不能影响超过的分数,那么只能选既不是a[i]也不是b[i]共k-2中选择,那么乘上(k-2)(num-2*i),最后n-num的部分是a[i]==b[i],对于这部分不论取什么对于两者的贡献是一样的,那么一共有k种选择,所以最后再乘上k(n-num)即可。
O(nk)
// ——By DD_BOND #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MOD=; ll dp[][];
int a[],b[]; int main(void)
{
ios::sync_with_stdio(false); cin.tie(); cout.tie();
ll n,k; cin>>n>>k;
for(int i=;i<=n;i++) cin>>a[i];
for(int i=;i<=n;i++) b[i]=a[i%n+];
dp[][n+]=;
for(int i=;i<=n;i++){
for(int j=;j<=*n+;j++){
if(a[i]==b[i]) dp[i][j]=dp[i-][j]*k%MOD;
else dp[i][j]=((dp[i-][j-]+dp[i-][j+])%MOD+dp[i-][j]*(k-)%MOD)%MOD;
}
}
ll ans=;
for(int i=n+;i<=*n+;i++) ans=(ans+dp[n][i])%MOD;
cout<<ans<<endl;
return ;
}
O(nlogk)
// ——By DD_BOND #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MOD=;
const int MAXN=1e6+; ll qpow(ll a,ll n){ll sum=;while(n){if(n&)sum=sum*a%MOD;a=a*a%MOD;n>>=;}return sum;} int a[MAXN],b[MAXN];
int fac[MAXN],rfac[MAXN],inv[MAXN]; int C(int n,int m){
if(n-m<m) m=n-m;
if(m==) return ;
return 1ll*fac[n]*rfac[m]%MOD*rfac[n-m]%MOD;
} int main(void)
{
ios::sync_with_stdio(false); cin.tie(); cout.tie();
fac[]=rfac[]=inv[]=;
for(int i=;i<MAXN;i++) inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
for(int i=;i<MAXN;i++) fac[i]=1ll*fac[i-]*i%MOD,rfac[i]=1ll*rfac[i-]*inv[i]%MOD;
int n,k,num=,ans=; cin>>n>>k;
for(int i=;i<=n;i++) cin>>a[i];
if(k==) return cout<<<<endl,;
for(int i=;i<=n;i++)
if(a[i]!=a[i%n+])
num++;
for(int i=;*i<=num;i++) ans=(ans+1ll*C(num,i)*C(num-i,i)%MOD*qpow(k-,num-*i)%MOD*qpow(k,n-num)%MOD)%MOD;
cout<<(qpow(k,n)-ans+MOD)%MOD*inv[]%MOD<<endl;
return ;
}
最新文章
- 记录我这一年的技术之路(nodejs纯干货)
- ListView和Adapter数据适配器的简单介绍
- HTML5——摒弃插件和前端框架的异步文件上传
- HTML DOM学习之三
- Unity5版本的AssetBundle打包方案之打包Scene场景
- Unity开发游戏 flapybird 无广告老马版分享
- iOS学习笔记---oc语言第八天
- 利用NTFS权限与虚拟目录,在IIS 6.0的默认FTP站点中做用户隔离。
- Xcode调试工具Instruments指南
- C#基础性问题
- Cassandra1.2文档学习(4)——分区器
- AJAX中文乱码PHP完美解决(IE和Firefox兼容)
- 酷炫的方块状散点3D
- stl_container容器和std_algorithm算法相同的函数
- java Log4j日志配置详解大全
- 无限分级Repeater递归实现:读取一次数据库,使用LINQ2SQL技术,支持排序&;amp;显示隐藏
- spy-debugger 安装以及使用
- 【vue】在移动端使用better-scroll 实现滚动效果
- PSi-Population Stability Index (PSI)
- 简单的document操作