Codechef CNTL Counting is life 生成函数

时间:2022-08-30 15:27:29

传送门——Vjudge


第一问很氵,如果\(K,N\)同奇偶就是\(2^K-1\),否则就是\(2^K-2\)

第二问似乎是可重排列,考虑指数型生成函数。

如何限制某些数必须要出现奇数/偶数次?考虑\(\frac{e^x-e^{-x}}{2}\),可以发现它的展开式中只有次数为奇数的项有值,而\(\frac{e^x+e^{-x}}{2}\)只有次数为偶数的项有值。

于是当\(K,N\)同奇偶时答案是\(N!(\frac{e^x-e^{-x}}{2})^K\),否则是\(N!(\frac{e^x-e^{-x}}{2})^{K-1}\frac{e^x+e^{-x}}{2}\)

暴力二项式定理拆开\((\frac{e^x - e^{-x}}{2})^K\)就可以算了。

#include<iostream>
#include<cstdio>
//This code is written by Itst
using namespace std; inline int read(){
int a = 0;
char c = getchar();
while(!isdigit(c))
c = getchar();
while(isdigit(c)){
a = a * 10 + c - 48;
c = getchar();
}
return a;
} const int MOD = 1e9 + 7;
inline int poww(long long a , int b){
int times = 1;
a = (a + MOD) % MOD;
while(b){
if(b & 1) times = times * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return times;
} const int MAXN = 1e5 + 7;
int T , N , K , jc[MAXN] , inv[MAXN]; void init(){
jc[0] = 1;
for(int i = 1 ; i <= 1e5 ; ++i)
jc[i] = 1ll * jc[i - 1] * i % MOD;
inv[100000] = poww(jc[100000] , MOD - 2);
for(int i = 1e5 - 1 ; i >= 0 ; --i)
inv[i] = inv[i + 1] * (1ll + i) % MOD;
} int binom(int b , int a){
return b < a ? 0 : 1ll * jc[b] * inv[a] % MOD * inv[b - a] % MOD;
} int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
//freopen("out","w",stdout);
#endif
init();
for(T = read() ; T ; --T){
N = read(); K = read();
if((N ^ K) & 1){
cout << poww(2 , K) - 2 << ' ';
int ans = 0;
for(int i = 0 ; i < K ; ++i)
ans = (ans + (i & 1 ? -1ll : 1ll) * binom(K - 1 , i) * (poww(K - 1 - 2 * i + 1 , N) + poww(K - 1 - 2 * i - 1 , N)) % MOD + MOD) % MOD;
cout << 1ll * ans * poww(poww(2 , K) , MOD - 2) % MOD << '\n';
}
else{
cout << poww(2 , K) - 1 << ' ';
int ans = 0;
for(int i = 0 ; i <= K ; ++i)
ans = (ans + (i & 1 ? -1ll : 1ll) * binom(K , i) * poww(K - 2 * i , N) % MOD + MOD) % MOD;
cout << 1ll * ans * poww(poww(2 , K) , MOD - 2) % MOD << '\n';
}
}
return 0;
}

Codechef CNTL Counting is life 生成函数的更多相关文章

  1. Codechef TAPAIR Counting the important pairs 随机化、树上差分

    传送门 题意:给出一个$N$个点.$M$条边的无向连通图,求有多少组无序数对$(i,j)$满足:割掉第$i$条边与第$j$条边之后,图变为不连通.$N \leq 10^5 , M \leq 3 \ti ...

  2. scau 2015寒假训练

    并不是很正规的.每个人自愿参与自愿退出,马哥找题(马哥超nice么么哒). 放假第一周与放假结束前一周 2015-01-26 http://acm.hust.edu.cn/vjudge/contest ...

  3. bzoj 3509&colon; &lbrack;CodeChef&rsqb; COUNTARI&rsqb; &lbrack;分块 生成函数&rsqb;

    3509: [CodeChef] COUNTARI 题意:统计满足\(i<j<k, 2*a[j] = a[i] + a[k]\)的个数 \(2*a[j]\)不太好处理,暴力fft不如直接暴 ...

  4. CodeChef Counting on a directed graph

    Counting on a directed graph Problem Code: GRAPHCNT All submissions for this problem are available. ...

  5. Counting The Important Pairs CodeChef - TAPAIR

    https://vjudge.net/problem/CodeChef-TAPAIR 合法的删除方法: 第一种:桥边与其余任意边(1)桥*(桥-1)/2(两条桥边)(2)桥*(m-桥)(桥边+其他边) ...

  6. 2019&period;01&period;02 poj3046 Ant Counting(生成函数&plus;dp)

    传送门 生成函数基础题. 题意:给出nnn个数以及它们的数量,求从所有数中选出i∣i∈[L,R]i|i\in[L,R]i∣i∈[L,R]个数来可能组成的集合的数量. 直接构造生成函数然后乘起来f(x) ...

  7. bzoj 2023&colon; &lbrack;Usaco2005 Nov&rsqb;Ant Counting 数蚂蚁【生成函数&vert;&vert;dp】

    用生成函数套路推一推,推完老想NTT--实际上把这个多项式乘法看成dp然后前缀和优化一下即可 #include<iostream> #include<cstdio> using ...

  8. 【xsy2479】counting 生成函数&plus;多项式快速幂

    题目大意:在字符集大小为$m$的情况下,有多少种构造长度为$n$的字符串$s$的方案,使得$C(s)=k$.其中$C(s)$表示字符串$s$中出现次数最多的字符的出现次数. 对$998244353$取 ...

  9. 【BZOJ】1630&colon; &lbrack;Usaco2007 Demo&rsqb;Ant Counting(裸dp&sol;dp&sol;生成函数)

    http://www.lydsy.com/JudgeOnline/problem.php?id=1630 题意,给你n种数,数量为m个,求所有的数组成的集合选长度l-r的个数 后两者待会写.. 裸dp ...

随机推荐

  1. CSS3之新UI方案

    border-radius 圆角 参数可为像素 也可为百分比 当一个参数时 作用范围为四个角 当两个参数时 作用范围为 左上右下 右上左下 当三个参数时 作用范围为 左上 右上左下 右下 当四个参数时 ...

  2. RT-thread学习笔记(一)

    我的基础:能在现有C程序下做些修改,不会移植,不会写驱动,很难从头到尾自己写程序. RT-thread基础:之前看了一点rtthread_manual.zh.pdf(即RT-thread使用手册),发 ...

  3. ps制作哈7海报字体

    模仿也需要较强的功底和分析思路.如下面的教程,作者模仿的是电影海报字.文字构造虽不复杂,不过思路不对的话就容易走弯路.最终效果 1.先来分析文字的构造,大致由两部分组成,一部分是浮雕字,另一部分是质感 ...

  4. wp上一款应用的出生与死亡

    起因 因为自己买了个wp手机,所以对于微软的这个wp系统还是非常喜欢,无奈软件质量不高,过年前便买了个wp的开发者帐号,不是很贵,还想着为wp的生态系统做点贡献.无奈工作繁忙,一直没有机会去做.但是自 ...

  5. 4K加速普及,8K近在咫尺,下一个是?

        从铺天盖地的厂商宣传到亲戚朋友家的客厅.不可否认4K时代已全面到来------业内人士估计2015年是4K电视的一个突破年.知名市场调查机构StrategyAnalytics对4K电视进行了调 ...

  6. android之使用GridView&plus;仿微信图片上传功能

    由于工作要求最近在使用GridView完成图片的批量上传功能,我的例子当中包含仿微信图片上传.拍照.本地选择.相片裁剪等功能,如果有需要的朋友可以看一下,希望我的实际经验能对您有所帮助. 直接上图,下 ...

  7. git 忽略文件夹

    $ vim .gitignore 添加要忽略的文件或文件夹 esc + :wq 退出vim命令行

  8. ListView 与ContextMenu的关联管理

    <span style="font-family: Arial, Helvetica, sans-serif;">package com.example.listvie ...

  9. &lbrack;是男人就过8题——Pony&period;ai&rsqb;Perfect N-P Arrays

    [是男人就过8题--Pony.ai]Perfect N-P Arrays 题目大意: 一棵\(n(\sum n\le5\times10^6)\)个结点的树,每个结点都有一个括号.求树上一个合法的括号序 ...

  10. &sol;usr&sol;bin&sol;ld&colon; 找不到 -lmsc----解决方案

    系统的默认搜索依赖库路径为,/usr/local/lib 在camkelists.txt文件中对可执行文件链接libmsc.so add_executable(iat_publish src/iat_ ...