T4WA10求条

问题讨论区 提高段
1

捕获
温馨提醒:那个符号表示连乘

#include<bits/stdc++.h>
using namespace std;
const long long N=10000007;
long long dp[100],c[100][100],n;
long long work(long long x)
{
	long long a[100],cnt=0,t;
	long long ans=1;
	memset(a,0,sizeof a);
	while(x)
	{
		a[++cnt]=x%2;
		x/=2;
	}
	for(int i=1;i<cnt;i++)//位数小于限制位数,必定在区间内 
	ans=(ans*dp[i])%N;
	t=1;
	for(int i=cnt-1;i>=1;i--)//最恶心的部分 
	{
		if(a[i]==0)
		{
			continue;
		}
		for(int j=0;j<i;j++)
		{
			ans=(ans*((c[i-1][j]*(t+j))%N))%N;
		}
		t++;
	}
	return (ans*t)%N;
}
int main()
{
	cin>>n;
	for(int i=0;i<=90;i++)//预处理组合数 
	{
		c[i][0]=1;
		for(int j=1;j<=i;j++)
		{
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%N;
		}
	}
	for(int i=1;i<=70;i++)
	{
		dp[i]=1;
		for(int j=0;j<i;j++)
		{
			dp[i]=(dp[i]*((c[i-1][j]*(j+1))%N))%N;
		}
	}
	cout<<work(n);
}
/*
10925604536777
3735963
*/
2

（帖子已被作者删除）

3

什么溢出?怎么溢出的

4

为什么cnt-1?

5

因为要枚举位数不满cnt位的数

6

然后再处理cnt位的数量

7

（帖子已被作者删除）

8

（帖子已被作者删除）

9

啥东西?

10

错误样例

11

谢谢曾天云同学,发现问题了

12

你思路是啥？

13

给个AC代码,自己看吧,实在是讲不动了(别抄)

14 
#include<bits/stdc++.h>
using namespace std;
const long long N=10000007;
long long dp[100],c[100][100],n;
long long qpow(long long x,long long y)
{
	if(y==0)
	{
		return 1;
	}
	long long cnt=qpow(x,y/2);
	if(y%2==0)
	{
		return (cnt*cnt)%N;
	}
	return (((cnt*cnt)%N)*x)%N; 
}
long long work(long long x)
{
	long long a[100],cnt=0,t;
	long long ans=1;
	memset(a,0,sizeof a);
	while(x)
	{
		a[++cnt]=x%2;
		x/=2;
	}
	for(int i=1;i<cnt;i++)//位数小于限制位数,必定在区间内 
	ans=(ans*dp[i])%N;
	t=1;
	for(int i=cnt-1;i>=1;i--)//最恶心的部分 
	{
		if(a[i]==0)
		{
			continue;
		}
		for(int j=0;j<i;j++)
		{
			ans=(ans*qpow(t+j,c[i-1][j]))%N;
		}
		t++;
	}
	return (ans*t)%N;
}
int main()
{
	cin>>n;
	for(int i=0;i<=63;i++)//预处理组合数 
	{
		c[i][0]=1;
		for(int j=1;j<=i;j++)
		{
			c[i][j]=c[i-1][j-1]+c[i-1][j];
		}
	}
	for(int i=1;i<=63;i++)
	{
		dp[i]=1;
		for(int j=0;j<i;j++)
		{
			dp[i]=(dp[i]*qpow(j+1,c[i-1][j]))%N;
		}
	}
	cout<<work(n);
}
/*
10925604536777
3735963
*/
15

AC了,关贴吧