首页 > 其他分享 >How-many

How-many

时间:2024-07-05 11:20:40浏览次数:8  
标签:int many long How read getchar

#include <bits/stdc++.h>
#define int long long
using namespace std ; 
const int mod = 1e9 + 7 ; 
inline int read() {
	int x = 0 , f = 1 ; 
	char c = getchar() ; 

	while (c < '0' || c > '9') {
		if (c == '-') f = -f ; 

		c = getchar() ; 
	}

	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0' ; 
		c = getchar() ; 
	}

	return x * f ; 
}

int N , M ; int dp[52][52] , g[52][52][52] , f[52] ;  
int C[52][52] ; 

int Quick_Pow(int a , int b) {
	int ans = 1 ; 

	while (b) {
		if (b & 1) ans = (ans * a) % mod ; 

		a = (a * a) % mod ; b >>= 1 ; 
	}

	return ans ; 
}

signed main() {
    #ifndef ONLINE_JUDGE
        freopen("1.in" , "r" , stdin) ; 
		freopen("1.out" , "w" , stdout) ; 
    #endif
	N = read() , M = read() ; 

	C[0][0] = 1 ; 
	for (int i = 1 ; i <= N ; ++ i) {
		C[i][0] = 1 ; 

		for (int j = 1 ; j <= i ; ++ j) {
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod ; 
		}
	}

	f[1] = 1 ; dp[1][0] = 1 ; 
	g[1][0][1] = 1 ; 

	for (int n = 2 ; n <= N ; ++ n) {
		f[n] = Quick_Pow(2 , C[n][2]) ; 

		for (int j = 1 ; j < n ; ++ j)
			f[n] = (f[n] + mod - (((C[n - 1][j - 1] * f[j]) % mod) * Quick_Pow(2 , C[n - j][2])) % mod) % mod ; 
		cerr << f[n] << '\n' ; 

		for (int k = 1 ; k <= n ; ++ k) {
			for (int j = 0 ; j <= n - k ; ++ j) {
				for (int i = 1 ; i <= n - k + 1 ; ++ i) {
					for (int x = 0 ; x <= min(j , i - 1) ; ++ x) {
						g[n][j][k] = (g[n][j][k] + ((C[n - 1][i - 1] * dp[i][x]) % mod) * (g[n - i][j - x][k - 1] * i) % mod) % mod ; 
					}
				}
			}
		}

		for (int j = 1 ; j <= n - 1 ; ++ j) {
			for (int i = 1 ; i <= n - j ; ++ i) {
				for (int x = 1 ; x <= j ; ++ x) {
					dp[n][j] = (dp[n][j] + (((dp[i][0] * g[n - i][j - x][x]) % mod) * Quick_Pow(i , x)) % mod) % mod ; 
				}
			}
		}

		dp[n][0] = f[n] ; 
		for (int j = 1 ; j <= n - 1 ; ++ j) {
			dp[n][0] = (dp[n][0] + mod - dp[n][j]) % mod ; 
		}

		cerr << '\n' ; 
	}

	int ans = 0 ; 

	for (int j = 1 ; j <= M ; ++ j) {
		ans = (ans + dp[N][j]) % mod ; 
	}

	printf("%lld" , ans) ; 
}

标签:int,many,long,How,read,getchar
From: https://www.cnblogs.com/hangry/p/18285436

相关文章

  • How to get all subarrays from an array by using JavaScript All In One
    HowtogetallsubarraysfromanarraybyusingJavaScriptAllInOneJavaScript动态生成其所有的子数组算法difficulty:Medium/难度:中等solutionsdemos//双指针???//functionnumberOfSubarrays(nums:number[],k:number):number{//letcount=0......
  • Cobra - How to avoid access global variables in a global variable or init() func
    在同一个package中的init()函数是按照所在文件文件名的字母顺序执行的,如果一个文件排在root.go之前,那么在其中字义的<文件名>Cmd全局变量赋值时将不能使用在root.go中初始化并赋值的全局变量(如globalflags),同样在其init()函数中也不能使用那些全局变量,如果使用则会报空指针错误。......
  • [MdOI R5] Many Minimizations & [ARC164F] Many Increasing Problems 题解
    讲下一个思路比较自然的基于自然数幂和的\(O(n\logn)\)且复杂度与\(m\)几乎无关的做法。不难发现让我们计数的问题是保序回归\(L_1\)中一条链的情况。这个情况有一个简单的slope-trick做法:用堆维护斜率,每次push进去两个当前的数,然后pop出一个最大值。最终所有数的和......
  • [MdOI R5] Many Minimizations & [ARC164F] Many Increasing Problems 题解
    讲下一个思路比较自然的基于自然数幂和的\(O(n\logn)\)且复杂度与\(m\)几乎无关的做法。不难发现让我们计数的问题是保序回归\(L_1\)中一条链的情况。这个情况有一个简单的slope-trick做法:用堆维护斜率,每次push进去两个当前的数,然后pop出一个最大值。最终所有数的和......
  • ctfshow web 其他 web432--web449
    web432过滤了os|open|system|read|eval?code=str(''.__class__.__bases__[0].__subclasses__[185].__init__.__globals__['__builtins__']['__imp'+'ort__']('o'+'s').__dict__['po'+'pen'](......
  • ctfshow 2023 愚人杯 web
    easy_signin观察url,发现base64,进行解码,原来可以访问文件路径,那我们访问一下index.php?img=aW5kZXgucGhw查看源代码发现还是base64解码得到flag被遗忘的反序列化<?php#当前目录中有一个txt文件哦error_reporting(0);show_source(__FILE__);include("check.p......
  • [题解]AT_abc253_g [ABC253G] Swap Many Times
    思路首先,不难看出一个规律,就是对于一个序列\(a\),如果它将操作所有以\(x\)为第一关键字的二元组,那么序列的\(a_{x\simn}\)将循环右移一位。(注意,在这里的\(x\)指的是在\(1\sim(n-1)\)中的任意一个定值)那么,我们就可以将编号分别为\(l\simr\)的这些二元组分为三......
  • 解决Linux中出现Too many open files
    Too many open files  问题出现有两种情况:一种是在搜索的时候出现,多半是由于索引创建完毕之后被移动过,如果创建索引的时候不出现该错误,搜索的时候也一般是不会出现的。如果出现了,有两种处理办法,一种是修改合并因子和最小合并因子,并且使用IndexWriter.Optimize()  优化索引,......
  • mysql SHOW PROFILE
    SHOWPROFILE[type[,type]...][FORQUERYn][LIMITrow_count[OFFSEToffset]]type:{ALL|BLOCKIO|CONTEXTSWITCHES|CPU|IPC|MEMORY|PAGEFAULTS|SOURCE|SWAPS}SHOWPROFILE和SHOWPROFILES语句显示分析信息,这些信......
  • Flink报错 java.lang.IllegalArgumentException: too many arguments
    错误信息/Library/Java/JavaVirtualMachines/zulu-21.jdk/Contents/Home/bin/java-javaagent:/Users/liuyu/Applications/IntelliJIDEAUltimate.app/Contents/lib/idea_rt.jar=51748:/Users/liuyu/Applications/IntelliJIDEAUltimate.app/Contents/bin-Dfile.encoding=UTF-......