本文主要是介绍牛客网暑期ACM多校训练营(第四场)C(Chiaki Sequence Reloaded),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
Chiaki is interested in an infinite sequence a1, a2, a3, ..., which defined as follows:
Chiaki would like to know the sum of the first n terms of the sequence, i.e. . As this number may be very large, Chiaki is only interested in its remainder modulo (109 + 7).
输入描述:
There are multiple test cases. The first line of input contains an integer T (1 ≤ T ≤ 105), indicating the number of test cases. For each test case: The first line contains an integer n (1 ≤ n ≤ 1018).
输出描述:
For each test case, output an integer denoting the answer.
示例1
输入
10 1 2 3 4 5 6 7 8 9 10
输出
0 1 2 2 4 4 6 7 8 11
题意:根据所给公式求绝对值之和
思路:官方题解
直接数位dp记忆化搜索。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;
const int mod=1e9+7;
typedef long long LL;
LL dp[70][3][140];
int dig[70];
int judge (int i,int j)
{
return i==j?1:-1;
}
LL dfs(int pos,int limit,int num,int front)
{
if (pos<0) return abs(70-num);
if (!limit&&dp[pos][front][num]!=-1) return dp[pos][front][num];
int end=limit?dig[pos]:1;
LL res=0;
for (int i=0;i<=end;i++)
{
if (front==2&&i==1) res+=dfs(pos-1,limit&(i==end),num,i);
else if (front==2&&i==0) res+=dfs(pos-1,limit&(i==end),num,2);
else res+=dfs(pos-1,limit&(i==end),num+judge(i,front),i);
res%=mod;
}
if (!limit)
dp[pos][front][num]=res;
return res;
}
int main()
{
memset(dp,-1,sizeof(dp));
LL n;
LL t;
scanf("%lld",&t);
while (t--)
{
scanf("%lld",&n);
int len=0;
while (n) dig[len++]=n&1, n>>=1;
printf("%lld\n",dfs(len-1,1,70,2));
}
return 0;
}
这篇关于牛客网暑期ACM多校训练营(第四场)C(Chiaki Sequence Reloaded)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!