Light OJ 1318 Strange Game 组合数+快速幂+分解因子

2024-06-15 11:32

本文主要是介绍Light OJ 1318 Strange Game 组合数+快速幂+分解因子,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

长度为l的用k种字符组成的字符串有k^l中 其中m个字符要不相同 那就是k^l*C(l, m)*(k-1)^m 有重复 要除以2 但是你mod n了 不能直接除 n不一定是素数 所以不能乘以逆元

所以我都mod 2倍的n 最后的结果再除以2 特判l = 1 和 m = 0的情况

#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
int vis[100010];
int prime[100010], c;void sieve(int n)
{int m = sqrt(n+0.5);memset(vis, 0, sizeof(vis));vis[0] = vis[1] = 1;for(int i = 2; i <= m; i++)if(!vis[i])for(int j = i*i; j <= n; j += i)vis[j] = 1;
}int get_primes(int n)
{sieve(n);int c = 0;for(int i = 2; i <= n; i++)if(!vis[i])prime[c++] = i;return c;
}
LL pow(LL a, LL b, LL n)
{LL ans = 1;while(b){if(b&1){ans *= a;ans %= n;}b >>= 1;a *= a;a %= n;}return ans;
}
LL work(LL x, LL y)
{LL ans = 0;while(x){ans += x/y;x /= y;}return ans;
}
LL cm(LL n, LL m, LL p)
{LL ans = 1;for(int i = 0; prime[i] <= n && i < c; i++){LL x = work(n, prime[i]);LL y = work(n-m, prime[i]);LL z = work(m, prime[i]);x -= y+z;ans *= pow(prime[i], x, p);ans %= p;}return ans;
}
LL cal(LL n, LL k, LL l, LL m)
{LL ans = 1;ans = ans * pow(k, l, n) % n;ans = ans * pow(k-1, m, n) % n;ans = ans * cm(l, m, n) % n;return ans;
}
int main()
{c = get_primes(100000);int T;int cas = 1;scanf("%d", &T);while(T--){LL n, k, l, m;scanf("%lld %lld %lld %lld", &n, &k, &l, &m);if(m == 0){printf("Case %d: %lld\n", cas++, pow(k, l, n)+1);}else if(k == 1)printf("Case %d: 1\n", cas++);elseprintf("Case %d: %lld\n", cas++, cal(2*n, k, l, m)/2+1);}return 0;
}


这篇关于Light OJ 1318 Strange Game 组合数+快速幂+分解因子的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1063333

相关文章

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

hdu4869(逆元+求组合数)

//输入n,m,n表示翻牌的次数,m表示牌的数目,求经过n次操作后共有几种状态#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#includ

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值: Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中: 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令: An=(a+b√)n A_n = (a +

v0.dev快速开发

探索v0.dev:次世代开发者之利器 今之技艺日新月异,开发者之工具亦随之进步不辍。v0.dev者,新兴之开发者利器也,迅速引起众多开发者之瞩目。本文将引汝探究v0.dev之基本功能与优势,助汝速速上手,提升开发之效率。 何谓v0.dev? v0.dev者,现代化之开发者工具也,旨在简化并加速软件开发之过程。其集多种功能于一体,助开发者高效编写、测试及部署代码。无论汝为前端开发者、后端开发者

线性因子模型 - 独立分量分析(ICA)篇

序言 线性因子模型是数据分析与机器学习中的一类重要模型,它们通过引入潜变量( latent variables \text{latent variables} latent variables)来更好地表征数据。其中,独立分量分析( ICA \text{ICA} ICA)作为线性因子模型的一种,以其独特的视角和广泛的应用领域而备受关注。 ICA \text{ICA} ICA旨在将观察到的复杂信号

fzu 2275 Game KMP

Problem 2275 Game Time Limit: 1000 mSec    Memory Limit : 262144 KB  Problem Description Alice and Bob is playing a game. Each of them has a number. Alice’s number is A, and Bob’s number i

利用Django框架快速构建Web应用:从零到上线

随着互联网的发展,Web应用的需求日益增长,而Django作为一个高级的Python Web框架,以其强大的功能和灵活的架构,成为了众多开发者的选择。本文将指导你如何从零开始使用Django框架构建一个简单的Web应用,并将其部署到线上,让世界看到你的作品。 Django简介 Django是由Adrian Holovaty和Simon Willison于2005年开发的一个开源框架,旨在简

CentOs7上Mysql快速迁移脚本

因公司业务需要,对原来在/usr/local/mysql/data目录下的数据迁移到/data/local/mysql/mysqlData。 原因是系统盘太小,只有20G,几下就快满了。 参考过几篇文章,基于大神们的思路,我封装成了.sh脚本。 步骤如下: 1) 先修改好/etc/my.cnf,        ##[mysqld]       ##datadir=/data/loc

SAM2POINT:以zero-shot且快速的方式将任何 3D 视频分割为视频

摘要 我们介绍 SAM2POINT,这是一种采用 Segment Anything Model 2 (SAM 2) 进行零样本和快速 3D 分割的初步探索。 SAM2POINT 将任何 3D 数据解释为一系列多向视频,并利用 SAM 2 进行 3D 空间分割,无需进一步训练或 2D-3D 投影。 我们的框架支持各种提示类型,包括 3D 点、框和掩模,并且可以泛化到不同的场景,例如 3D 对象、室

UE5 半透明阴影 快速解决方案

Step 1: 打开该选项 Step 2: 将半透明材质给到模型后,设置光照的Shadow Resolution Scale,越大,阴影的效果越好