技术标签: lucas与扩展lucas
公式的话官方题解已经非常详细,这里就不再写公式了,大致推导为n步有x+y步是j,k两维移动,有n-x-y步是在i轴上移动。 在x+y的两维中,有y步是在y轴上移动,x步在x轴上移动。然后算上C(n,x+y)*C(x+y,x)*t1^(x/p)*t2(y/p)。就是每个点的贡献。这题卡常卡的太恶心了。
#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef long long ll;
const LL mod = 998244353;
LL pi = 2;
LL pe = 8388608, Pa[8388610];
LL per = pe-1;
LL fac[2][30],inv[2][30],mul0,mul1,mul2,qpe[1007];
inline LL qpow(LL a, LL b, LL m)
{
LL ans = 1;
a %= m;
while(b > 0)
{
if(b&1) ans = ans*a%m;
a = a*a%m;
b >>= 1;
}
return ans;
}
inline LL fast_pow(LL a, LL b, LL m)
{
LL ans = 1;
LL mm = m-1;
a &= mm;
while(b > 0)
{
if(b&1) ans = ans*a&mm;
a = a*a&mm;
b >>= 1;
}
return ans;
}
inline LL exgcd(LL a,LL b,LL &x,LL &y) {
if(b==0) {
x=1,y=0;
return a;
}
LL d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
inline LL Inv(LL a,LL P){//求a在膜P下的逆
if(a==0)return 1;
LL x,y;
exgcd(a,P,x,y);
return (x%P+P)%P;
}
inline LL cal1(LL n) {
LL ans=0;
while(n > 0) {
ans += (n>>1);
n >>= 1;
}
return ans;
}
inline LL cal2(LL n) {
if(n == 0) return 1;
LL ans = 1;
if(n/pe) ans = qpe[n/pe];
ans = Pa[n&per];
return cal2(n>>1)*ans&per;
}
inline LL cal(LL n,LL m, LL P) {
LL cnt = cal1(n) - cal1(m) - cal1(n-m);
LL a = cal2(n), b = cal2(m), c = cal2(n-m);
LL ans = ((a*Inv(b,pe)&per)*Inv(c,pe)&per)*fast_pow(pi,cnt,pe)&per;
return ans;//范围可到达P*Pi,注意是否用快速乘
}
inline LL C(LL n, LL m, LL p, LL id)//组合数C(n, m) % p
{
if(m > n) return 0;
return fac[id][n] * inv[id][m]%p * inv[id][n - m] % p;
}
inline LL Lucas(LL n, LL m, LL p, LL id)
{
if(m == 0) return 1;
return C(n % p, m % p, p, id) * Lucas(n / p, m / p, p, id) % p;
}
inline LL solve(LL n,LL m,LL P) {
if(m>n)return 0;
LL ans = cal(n,m,P)*mul0%P;
LL p = 7;
LL t1 = Lucas(n,m,p,0)*mul1%P;
p = 17;
LL t2 = Lucas(n,m,p,1)*mul2%P;
ans = (ans + t1 + t2)%P;
return ans;
}
void init(LL P){
mul0 = (P/pe)*Inv(P/pe,pe)%P;
mul1 = (P/7)*Inv(P/7,7)%P;
mul2 = (P/17)*Inv(P/17,17)%P;
Pa[0] = Pa[1] = 1;
for(LL j = 2; j <= pe; j++){
if(j&1) Pa[j] = Pa[j-1]*j&per;
else Pa[j] = Pa[j-1];
}
qpe[0] = Pa[pe];
for(int i = 1; i <= 1000; i++)
qpe[i] = qpe[i-1]*Pa[pe]%pe;
LL p = 7;
fac[0][0] = fac[0][1] = 1;
inv[0][0] = inv[0][1] = 1;
for(LL j = 2; j <= p; j++){
fac[0][j] = fac[0][j-1]*j%p;
inv[0][j] = inv[0][j-1]*qpow(j,p-2,p)%p;
}
p = 17;
fac[1][0] = fac[1][1] = 1;
inv[1][0] = inv[1][1] = 1;
for(LL j = 2; j <= p; j++){
fac[1][j] = fac[1][j-1]*j%p;
inv[1][j] = inv[1][j-1]*qpow(j,p-2,p)%p;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int t1,t2,p,q,n,m;
init(mod-1);
while(~scanf("%d%d%d%d%d%d",&t1,&t2,&p,&q,&n,&m)){
LL ans = 1;
for(LL i = 1; i <= m; i++){
int ax,ay,av;
scanf("%d%d%d",&ax,&ay,&av);
if(ax%p != 0 || ay%q != 0){
continue;
}
LL x = ax/p , y = ay/q;
if(x+y > n) continue;
LL tmp = solve(x+y, x, mod-1)*solve(n,x+y,mod-1)%(mod-1)*qpow(t1,x,mod-1)%(mod-1)*qpow(t2,y,mod-1)%(mod-1);
ans = ans*qpow(av,tmp,mod)%mod;
}
printf("%lld\n",(ans%mod+mod)%mod);
}
return 0;
}
文章浏览阅读850次,点赞23次,收藏24次。 通过整个项目的实践,我们亲身体会了数据挖掘的那张路线图,预处理、分析之后发现问题(Knowledge),再进行新的处理,再重新分析挖掘,做评估,然后发现新的问题,再从头开始,在这几个过程的循环往复中完成了整个项目。_数据挖掘二手房价预测
文章浏览阅读3.6k次。var setSearchFlag; function showSearch(obj){ clearSearchFlag(); var w3c=(document.getElementById)? true:false;//w3c 标准 var ns6=(w3c && (navigator.appName=="Netscape"))? true: false;//Netsca_input触发弹出层
文章浏览阅读5.6k次,点赞7次,收藏63次。文章目录一、交叉验证二、K折交叉验证KFold()方法StratifiedKFold()方法一、交叉验证交叉验证的基本思想是把在某种意义下将原始数据(dataset)进行分组,一部分做为训练集(train set),另一部分做为验证集(validation set or test set),首先用训练集对分类器进行训练,再利用验证集来测试训练得到的模型(model),以此来做为评价分类器的性能指标。–来自百科二、K折交叉验证KFold()方法KFold(): KFold 将所有的样例划分为 _四折交叉验证
文章浏览阅读9k次。我们都知道刷bios的时候,在整个升级过程中都需要谨慎,不然很容易搞坏主板,就会得不偿失,那么如果使用联想电脑的用户该怎么去刷bios呢?虽然使用联想的用户很多,但是会的没几个,下面,小编就来跟大家讲讲联想电脑如何刷bios。刷bios有什么用?这是一些用户都想要知道了,其实我们的电脑想要增加新的选项,就像软件更新一样增加功能,那么该怎么去刷bios呢?很多的用户都不知道该怎么去操作呢?下面,小编..._联想主板刷bios教程
文章浏览阅读996次。Win7与Xp,直观上最大的区别便是界面上的改变了,win7拥有着华丽的玻璃界面.今天就写一下关于这方面的文章.毫无疑问,一切都是微软提供,以下一切内容参考于MSDN中http://msdn.microsoft.com/en-us/library/windows/desktop/aa969540(v=vs.85).aspx这篇文章.先给出代码.再做解释: 1 .3_获取dwm窗口
文章浏览阅读308次。以我之前主持开发的一个商业产品:p2p网贷为例进行分析。整个的概况,可以参见:www.huixinp2p.com(目的只会技术交流)界面可以直接参考前期博客:http://www.cnblogs.com/shenliang123/p/3435427.html其中涉及到的部分web安全的解决可以参考最新博客:http://www.cnblogs.com/shenliang123/p/3835..._p2p网贷系统平台设计简析
文章浏览阅读1.2k次。出现这种异常是因为没有设置 project.build.home.directory 参数,系统找不到源代码文件的位置。解决办法:1.首先下载源代码,可参考如何下载olat源代码并在eclipse中查看2.在部署的服务中找到 olat.local.properti_guidemo_main不显示
文章浏览阅读1.4k次。Rect 类定义了一个矩形结构,同样实现了 Parcelable 序列化接口。Rect 类定义了 left、top、right、bottom 四个成员变量,我们需要正确理解这 4 个成员变量的作用:left:矩形左边线条离 y 轴的距离top:矩形上面线条离 x 轴的距离right:矩形右边线条离 y 轴的距离bottom:矩形底部线条离 x 轴的距离矩形是一种非常常见的图_android根据rect坐标添加控件
文章浏览阅读2.4w次,点赞10次,收藏27次。1.出错CCS5.5.0导入工程(Import CCS Eclispse Project)时出错:Issues that may require your attention were encountered while importing the projects ,如下图:2.原因是由于文件夹名(例如f28335_Sci_Update_Flash_first)和文件夹中的工程名
文章浏览阅读8.9k次,点赞3次,收藏4次。在修复RUI桌面在4.0系统下的提示信息不完善的Bug过程的一些思路与大家分享一下。Bug描述:RUI在2.2的系统点击推荐图标下载后,就会进入下载队列中下载,如果再次点击相同的图标就会使用Toast提示“**已经在下载队列中”。但是在4.0的系统就会出现异常,第二次点击相同的推荐图标时没有出现Toast提示。相关源码:public static void showMe_安卓4.0不支持uni.showtoast
文章浏览阅读3.3k次。在运行 Windows Server 2003 的计算机上,您可以根据需要对所选的客户端关闭 TCP/IP 上的 NetBIOS (NetBT)。如果您希望只使用 DNS 在一台指定计算机(该计算机用于您网络中的专门角色或安全角色)上提供名称注册和解析,则您可以选择为该计算机上安装的一个或所有网络适配器关闭 NetBT 服务。配置要关闭 WINS/NetBT..._服务器无法与传输绑定,因为网络上的另一部计算机具有相同的名称。服务器无法启动
文章浏览阅读806次。修路方案时间限制:3000 ms | 内存限制:65535 KB难度:5描述南将军率领着许多部队,它们分别驻扎在N个不同的城市里,这些城市分别编号1~N,由于交通不太便利,南将军准备修路。现在已经知道哪些城市之间可以修路,如果修路,花费是多少。现在,军师小工已经找到了一种修路的方案,能够使各个城市都联通起来,而且花费最少。但是,南