自定义指令 Eclipse CANopen curl model Uploadify HammerJS centos查看php版本 oracle一键卸载工具 linuxmysql启动命令 二分查找python python手册 python基础教程免费 java接口文档 java获得当前日期 获取当前时间java 怎么装linux系统 Ext2Fsd 摩斯密码翻译 ps怎么插入表格 微信昵称找人的软件 蓝牙测试软件 mac画图工具 男网红头像 windows游戏编程 top命令详解 sprutcam python保存文件 微信小程序循环 网卡漫画控 fleaphp 迅捷cad转换器 jsp页面跳转 苹果视频剪辑 ps怎么取色 js取余 steam怎么改名 apk提取 steam游戏闪退 php编写
当前位置: 首页 > 学习教程  > 编程语言

51nod 1829 函数 第二类斯特林数

2020/10/8 20:25:42 文章标签:

题意就是把n个不同的物体放到m个不同的盒子里,斯特林数是求相同的盒子,所以就是求S*(n,m)m!*S(n,m) 用递推的解法S(n,m)m*S(n-1,m)S(n-1,m-1)是O(n^2)肯定会t,所以直接用容斥推的式子。 //#pragma GCC optimize(3,"Ofast","i…

题意就是把n个不同的物体放到m个不同的盒子里,斯特林数是求相同的盒子,所以就是求S*(n,m)=m!*S(n,m)

用递推的解法S(n,m)=m*S(n-1,m)+S(n-1,m-1)是O(n^2)肯定会t,所以直接用容斥推的式子。

在这里插入图片描述

//#pragma GCC optimize(3,"Ofast","inline")
#include<unordered_map>
//#include<unordered_set>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<functional>
#include<cstring>
#include<string>
#include<cstdlib>
#include<queue>
#include<map>
#include<algorithm>
#include<set>
#include<stack>
#include<vector>
#include<sstream>
#include<list>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int mod=1000000007;
const int N=2e3+10;
const int maxn=1e6+7;
ll mul[maxn];
ll inv[maxn];
ll c(int n,int m)
{
    return (mul[n]*inv[m])%mod*inv[n-m]%mod;
}
ll qpow(ll a,ll b,ll p)
{
    ll ans=1%p;
    a%=p;
    while(b)
    {
        if(b&1)ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}
int main()
{
    int n,m;
    cin>>n>>m;
    mul[0]=inv[0]=inv[1]=1;
    for(int i=1;i<=m;i++)mul[i]=mul[i-1]*i%mod;
    for(int i=2;i<=m;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<=m;i++)inv[i]=inv[i-1]*inv[i]%mod;
    ll ans=0;
    for(int i=0,e=1;i<=m;i++,e*=-1)
        ans=(ans+c(m,i)*qpow(m-i,n,mod)%mod*e)%mod;
    cout<<(ans+mod)%mod<<endl;
    return 0;
}

本文链接: http://www.dtmao.cc/news_show_250294.shtml

附件下载

上一篇:P2678跳石头

下一篇:Django 后台管理

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?