p1377发奖金

关键词：

输入

输出

样例输入

2 1 5

样例输出

3

对于p：设p=p1^c1 * p2^c2 * p3^c3 * … *pt ^ ct，pi为质数。

20%的数据：1 ≤ n, m≤ 15；

40%的数据：1≤n, m≤1000，p=10007；

60%的数据：保证t=1，ci=1，pi^ci≤10^5；

80%的数据：t≤2，ci=1，pi≤10^5；

100%的数据：1≤ n, m≤10^9，1≤pi^ci≤10^5，所有P不超过2^31-1。

这道题是多种数学方法的组合，代码要求有点高。

首先答案是C(m,n+m),这个就用隔栏法吧，想像成m个实心球，拿到算1块钱。这样在中间放n-1个栏，分成n分，因为可以不拿钱，加上n个球，每个人得到的钱是分到的球数-1.。就是C(m+n-1,n-1)m from 0 to M;=C(n+m,m),画个杨辉三角理解一下

然后就是求C(n+m,m)%P的值了

如果P是个质数的话，维护n!%p的值以及n!%p的值在%p意义下的逆元即可。

但P不是个质数，这时我们把P分解，

对于p：设p=p1^c1 * p2^c2 * p3^c3 * … *pt ^ ct，pi为质数。

如果我们知道x%(p1^c1)=a1,%(p2^c2)=a2...%(pt^ct)=at,就可以用中国剩余定理求x%p的值了

太巧妙了

参考LHQ的代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
const ll MAXN=100005;
ll fac[MAXN],inv[MAXN],A[MAXN],M[MAXN];
ll p[MAXN],c[MAXN];
ll n,m,cntp,Mod;
ll power(ll a,ll b,ll p)
{
    //cout<<"power"<<endl;
    ll ret=1;
    while (b)
    {
        if (b&1)
        {
            ret*=a;
            if (p!=-1) ret%=p;
        }
        a*=a;
        if (p!=-1) a%=p;
        b>>=1;
    }
    return ret; 
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    //cout<<"exgcd"<<endl;
    if (b==0) {x=1; y=0; return a;}
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;   
}
ll er(ll a,ll b)
{
    //cout<<"er"<<endl;
    ll x,y;
    exgcd(a,b,x,y);
    return (x%b+b)%b;
}
ll calcfac(ll n,ll &cnt,const ll &P,const ll &p)
{
    //cout<<"calfac"<<endl;
    if (n<p) return fac[n];
    ll seg=n/P,rem=n%P;
    ll ret=power(fac[P-1],seg,P);
    ret=ret*fac[rem]%P;
    cnt+=n/p;
    return ret*calcfac(n/p,cnt,P,p)%P;  
}
ll calcinv(ll n,ll &cnt,const ll &P,const ll &p)
{
    //cout<<"calcinv"<<endl;
    if (n<p) return inv[n];
    ll seg=n/P,rem=n%P;
    ll ret=power(inv[P-1],seg,P);
    ret=ret*inv[rem]%P;
    cnt-=n/p;
    return ret*calcinv(n/p,cnt,P,p)%P;  
}
void cal_c(ll n,ll m)
{
    //cout<<"cal_c"<<endl;
    for(ll i=1;i<=cntp;i++)
    {
        ll P=power(p[i],c[i],-1);
        fac[0]=1;
        for(ll j=1;j<P;j++)
        {
            fac[j]=fac[j-1];
            if(j%p[i]!=0)
            fac[j]=fac[j-1]*j%P;
        }
        inv[0]=1;
        for(ll j=1;j<P;j++)
        {
            inv[j]=inv[j-1];
            if(j%p[i]!=0)
            inv[j]=inv[j-1]*er(j,P)%P;
        }
        ll cnt=0;
        ll ret=calcfac(n,cnt,P,p[i]);
        ret=ret*calcinv(m,cnt,P,p[i])%P;
        ret=ret*calcinv(n-m,cnt,P,p[i])%P;
        ret=ret*power(p[i],cnt,P)%P;
        A[i]=ret; M[i]=P;     
    }
}
ll CRT(ll a[],ll m[],ll n)
{
    ll M=1,ans=0,x,y,Mi,d;
    for(ll i=1;i<=n;i++)
    M*=m[i];
    for(ll i=1;i<=n;i++)
    {
        Mi=M/m[i];
        d=exgcd(Mi,m[i],x,y);
        ans=(ans+Mi*x*a[i])%M;
    }
    if(ans<0) ans+=M;
    return ans;
}
int main()
{
    scanf("%lld %lld %lld",&n,&m,&Mod);
    for(ll i=2;i*i<=Mod;i++)
    if(Mod%i==0)
    {
        p[++cntp]=i;
        while(Mod%i==0){
            Mod/=i;c[cntp]++;
        }
    }
    if(Mod>1)p[++cntp]=Mod,c[cntp]=1;
    cal_c(n+m,n);
    cout<<CRT(A,M,cntp)<<endl;
}

 还有中国剩余定理中两两互质的时候的求法。

对于n个方程x=Ai*y+Bi，令M=lcm(A1*A2*...*An)

ans=sigma(lcm(S|Ai!∈S)*Xi)其中Xi是第1个满足=Ai*y+Bi的数。

理解一下就是算出每个条件对应的最小数并且不影响其他位子上的值

宁波市赛2014小李发奖金(代码片段)

题面传送门贪心#include<cstdio>#include<iostream>#include<algorithm>usingnamespacestd;inta[50000];intmain()intn;cin>>n;for(inti=0;i<n;i++)cin>>a[i];sort(a,a+n);intans=0;for(i 查看详情

又是别人家的公司！李彦宏给创新员工发超2000万奖金……

...”、“潮汐”、“拨云”三支团队分别颁发最高奖，奖金折合人民币超2000万元。（截图自百度同学视频号）超2000万元奖金，别人家的公司2022年9月7日， 查看详情

拓扑排序——奖金

奖金【问题描述】　　由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，YaliCompany总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。于是Mr.Z下令召开m方会谈... 查看详情

#图##拓扑排序#-----奖金

奖金【题目描述】由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，YaliCompany总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。于是Mr.Z下令召开m方会谈。每... 查看详情

拓扑排序1.奖金

...选中胜出，YaliCompany总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工a的奖... 查看详情

人均“奖金”2400万元！雷军狂发“大红包”，网友：喜欢发钱的男人，真帅

任正非曾经说过一句话，我很喜欢：“钱给多了,不是人才也变人才。” 1发钱第一步，人均39万7月2日，小米集团（1810.HK）发布公告称，公司董事会根据股份奖励计划，向集团3904名员工授予总共7023... 查看详情

sdoi2008p1377仪仗队

欧拉函数的应用原题：作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N*N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)... 查看详情

4040ez系列之奖金

4040EZ系列之奖金 时间限制:1s空间限制:64000KB题目等级:钻石Diamond    题目描述Description由于无敌的WRN在2015年世界英俊帅气男总决选中胜出，EZ总经理Mr.Lin心情好，决定给每位员工发奖金。EZ决定以每个人本年在EZ... 查看详情

4040ez系列之奖金

4040EZ系列之奖金 时间限制:1s空间限制:64000KB题目等级:钻石Diamond 题目描述Description由于无敌的WRN在2015年世界英俊帅气男总决选中胜出，EZ总经理Mr.Lin心情好，决定给每位员工发奖金。EZ决定以每个人本年在EZ的贡献为标准... 查看详情

p1377[tjoi2011]树的序：离线nlogn建二叉搜索树

题目链接：https://www.luogu.org/problemnew/show/P1377题意：　　有一棵n个节点的二叉搜索树。　　给出它的插入序列，是一个1到n的排列。　　问你使得树的形态相同的字典序最小的插入序列。 题解：　　由于插入序列为1到n的排列... 查看详情

《新下级学》第八章第七节——信息不透明导致奖金失效等

8.5信息不透明导致奖金失效如上一章所述，奖惩也是重要的沟通频道。发奖金是为了让员工有干劲，但这里要揭示一个常见的现象：由于企业推行薪酬保密制度，反而使奖金的效力不那么大了。薪酬保密已经很流行了，自有其道... 查看详情

老板发了我2千奖金，原因是我用java实现了管理员可以修改任意用户session的功能(代码片段)

大家好，我曹尼玛；家里穷，所以我非常努力，白天上班，晚上加班学习，虽然大专刚毕业，工资只有8千，长得也丑，没有女朋友，但是我依然热爱生活，努力工作；前2个月，... 查看详情

2022-07-01：某公司年会上，大家要玩一食发奖金游戏，一共有n个员工，每个员工都有建设积分和捣乱积分，他们需要排成一队，在队伍最前面的一定是老板，老板也有建设积分和捣乱积分，排好队后，所有(代码

2022-07-01：某公司年会上，大家要玩一食发奖金游戏，一共有n个员工，每个员工都有建设积分和捣乱积分，他们需要排成一队，在队伍最前面的一定是老板，老板也有建设积分和捣乱积分，排好队后... 查看详情

小米机试厨艺大赛奖金(代码片段)

...到比自己分数高的人的分数）的评分。比赛结束之后要发奖金，以1K为单位，每位厨师至少会发1K的奖金，另外，如果一个厨师发现自己的奖金没有高于比自己评分低的厨师的奖金，就会不满意，作为比赛组织方，小米食堂至少... 查看详情

极客日报：雷军回应小米对标苹果遭冷嘲热讽；惨遭对手挖墙脚，苹果发高额股票奖金挽留人才；antdesign4.18.0发布

...专利获授权100名工程师被脸书挖走苹果发放最多18万美元奖金挽留人才特斯拉V11版软件的用户界面变化遭到司机的强烈批评受半导体短缺影响Switch明年初预计依旧缺货LG明年将向苹果供应120Hz刷新率屏幕，用于高端iPhone14RforWind... 查看详情

年终奖怎么发才能起到激励作用

...滋生企业内部矛盾，引发一系列后遗症。企业实行的年终奖金分配发放往往直接与岗位基本工资挂钩，对 查看详情

区块链技术网络安全应用创新大赛报名中！超80万奖金等您来！

近年，区块链技术持续创新，区块链产业逐步形成，开始在供应链金融、征信、产品溯源、版权交易、数字身份、电子证据等领域快速应用，助力实体经济和数字经济实现技术变革、组织变革和效率变革，为... 查看详情

奖金游戏java

...成绩，每名员工只能看到前后俩名员工的成绩，每人初始奖金1万，每名员工所获奖金必须比低于他成绩的前后员工的奖金高。最少需要多少钱。1importjava.util.ArrayList;2importjava.util.Collections;3importjava.util.Scanner;45classTest{6//奖金7staticA... 查看详情