列表

详情

NC221005. 离线版OEIS

描述

想必你一定做过很多找规律的题目吧

用1*2的多米诺骨牌铺2*n的方格......

用1*2的多米诺骨牌铺4*n的方格.......

n条直线可以把平面分割成几个区域呢？n条折线呢？

这类题目有很多...智乃酱在AC掉很多找规律的线性地推题目后，灵机一动，为什么不写个程序帮我找规律呢？

给你使用暴力程序得出在n=1,2,3,4,....时的答案。

如果你认为存在递推关系，请输出递推表达式，否则请输出"No_solution"。

我们规定，如果输入的数字存在线性递推关系，则仅会包含。
1、该项的前k项分别乘以一个整数系数求和的递推关系。
2、最高次数最多为3次的常数多项式，且多项式的系数也为整数。

换句话说，你要求得的递推式是下式的一个子式。


如果这个数据虽然存在系数为实数的递推关系，但是不存在系数为整数的递推关系时，也认为是无解的，此时也应当输出“No_solution”。

输入的测试数据还保证，如果存在符合题目要求的递推式，则至少存在一个递推式的各项系数在32位int型能表示的范围内，并且在计算前的值时，计算过程和最终结果不会超过64位整形的最大范围。

输入描述

第一行一个正整数，表示有T组样例

对于每组样例，第一行一个正整数。

输入数据保证maxn远大于最简递推式的阶数（如果存在的话）。

接下来一行maxn个整数，表示暴力程序跑出的答案。

输出描述

如果输入数据中不存在由前k项的常数倍与常数多项式组成的递推式，请输出"No_solution"
输入数据保证如果递推式中存在常数多项式，则最高次数为3次。

注意你输出的各种系数都必须是整数，并且保证该递推式在计算递推的中间过程不会有数据超过64位整形能够表示的最大范围。

如果存在一个各项系数为整数的递推式，请按照如下规则输出：

如需定义前k项的初始值。请先输出一行定义初始值，但是最多只能指定前5项的初始值。
请输出  a[i]=val  i表示第几项(i<=k)，val表示初始值。当k不等于1时，每一项之间使用一个","隔开。


比如定义斐波那契数列1 1 2 3 5 8 11 23 34 .....的前两项
就可输出"a[1]=1,a[2]=1"或者"a[2]=1,a[1]=1"

当定义完初始值或者无需定义初始值时

请输出a[i]=(递推表达式)
比如在定义完斐波那契数列的前两项后，请输出一行a[i]=a[i-1]+a[i-2]

对于常数多项式，三次幂要写成k*i*i*i的形式，两次幂要写成k*i*i的形式，一次幂次写成k*i，常数直接写k。

对于表达式的格式没有特定要求。特判程序可以识别连加表达式。

比如a[i]=a[i-1]+a[i-2]
如果写成a[i]=+1*a[i-1]+1a[i-2]+0a[i-3]+0*a[i-4]+0*i*i*i+0*i+0（系数直接写在项的前面，或者写成系数*项都是可以的，并且当系数的绝对值为1时可以省略不写，没有的项既可以不写也可以写成0*的形式），也能得到AC的结果。

但是每一项之间必须使用符号隔开，且不允许两符号直接相连。也就是输出的表达式必须合法。

同时，如果某个数列有多种表述方式的话，你可以输出任意一种，但是请注意最多只能指定前5项的初始值。

比如数列1 2 3 4 5 6 7 8 9 10 11 12 13 14...

既可以输出一行：
a[i]=i

也可以输出两行：
a[1]=1
a[i]=a[i-1]+1

示例1

输入: 

12
20
1300000264 2400000529 4900000736 9400000819 16500000712 26800000349 40899999664 59399998591 82899997064 111999995017 147299992384 189399989099 238899985096 296399980309 362499974672 437799968119 522899960584 618399952001 724899942304 842999931427
20
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
20
0 -3 248 -1001 4742 -21475 98124 -447437 2041170 -9310743 42471608 -193736321 883738622 -4031220235 18388624164 -83880680117 382626152490 -1745369401983 7961594705168 -36317234721641
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20
-1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19 -20
20
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
20
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
20
1 -2 3 -4 5 -560 -1504 -2339 -2874 -1654 1982 5758 6146 -2489 -24255 -50815 -59158 -17723 94346 241315
20
1 -2 3 -4 5 -553 -1507 -2336 -3978 -5791 -6267 -7826 -9795 -8947 -11468 -16675 -15702 -21764 -33809 -28091
20
1 -2 3 -4 5 -550 -1510 -2333 -3978 -5794 -7902 -14000 -21336 -29509 -45317 -59863 -79716 -124151 -166100 -226259
20
1 -2 3 -4 5 -6 7 -8 9 -10 11 -12 13 -14 15 -16 17 -18 19 -20
20
1 96 5 4 6 21 3 1 5 6 4 8 9 5 4 6 3 2 1 5

输出: 

a[i]=99999989*i*i*i+100000037*i*i+100000231*i+1000000007

a[1]=1,a[2]=1
a[i]=a[i-1]+a[i-2]

a[1]=0,a[2]=-3
a[i]=-5*a[i-1]-2*a[i-2]+233

a[i]=i

a[i]=-i

a[i]=8

a[1]=0
a[i]=-a[i-1]+1

a[1]=1,a[2]=-2,a[3]=3,a[4]=-4,a[5]=5
a[i]=a[i-1]-a[i-2]-3*a[i-4]-3*i*i*i+2*i*i+1

a[1]=1,a[2]=-2,a[3]=3,a[4]=-4,a[5]=5
a[i]=a[i-1]-a[i-2]+2*a[i-3]-3*a[i-4]+a[i-5]-3*i*i*i+2*i*i+1

a[1]=1,a[2]=-2,a[3]=3,a[4]=-4,a[5]=5
a[i]=a[i-1]-a[i-2]+2*a[i-3]-3*a[i-4]+4*a[i-5]-3*i*i*i+2*i*i+1

a[1]=1,a[2]=-2
a[i]=-2*a[i-1]-a[i-2]

No_solution

说明:

多组样例之间的空行是为了让大家看的更清楚，实际上你的程序不被要求样例与样例之间的额外空行。

如果你的运算过程使用了实数计算，请使用long double类型代替double，避免精度不足导致的WA。

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 18ms, 内存消耗: 792K, 提交时间: 2021-10-25 21:53:38 

#include<bits/stdc++.h> 
using namespace std;
#define ll long long
#define C getchar()-48
inline ll read()
{
    ll s=0,r=1;
    char c=C;
    for(;c<0||c>9;c=C) if(c==-3) r=-1;
    for(;c>=0&&c<=9;c=C) s=(s<<3)+(s<<1)+c;
    return s*r;
} 
const int N=210;
const double eps=1e-8;
int number;
int ans;
double a[N][N],del;
long long arr[N],ki[30];
bool flag;
inline int gauss(int n)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++) if(fabs(a[j][i])>=eps)
		{
			for(int k=i;k<=n+1;k++) swap(a[i][k],a[j][k]);
			break;
		}
//		if(fabs(a[i][i])<eps) return 0;
		for(int k=n+1;k>=i;k--) a[i][k]/=a[i][i];
		for(int j=1;j<=n;j++)
		{
			if(i==j) continue;
			for(int k=n+1;k>=i;k--) a[j][k]-=a[j][i]*a[i][k];
		}
	}
	for(int i=1;i<=n;i++) if(!a[i][i]&&(a[i][n+1])) return 0;
	return 1;
}
void work(long long k)
{
    memset(a,0,sizeof(a));
    for(long long i=1;i<=k+4;++i)
    {
        for(long long j=1;j<=k;++j){a[i][j]=arr[i+j-1];}
        a[i][k+1]=1;
        a[i][k+2]=(i+k);
        a[i][k+3]=(i+k)*(i+k);
        a[i][k+4]=(i+k)*(i+k)*(i+k);
        a[i][k+5]=arr[i+k];
    }
    if(gauss(k+4))
    {
        memset(ki,0,sizeof(ki));
        for(int i=1;i<=k+4;++i){ki[i]=round(a[i][k+5]);}
        for(int i=1;i<=k/2;++i){swap(ki[i],ki[k-i+1]);}
        for(long long i=k+1;i<=number;++i)
        {
            long long sum=0;
            for(int j=1;j<=k;++j){sum+=arr[i-j]*ki[j];}
            sum+=ki[k+1];
            sum+=ki[k+2]*i;
            sum+=ki[k+3]*i*i;
            sum+=ki[k+4]*i*i*i;
            if(arr[i]!=sum)return;
        }
        flag=true;
        return;
    }
}
int main()
{
	int t=read();
    while(t--)
    {
        number=read();
        for(int i=1;i<=number;++i){scanf("%lld",&arr[i]);}
        flag=false;
        for(int i=0;i<=5;++i)
        {
            work(i);
            if(flag){ans=i;break;}
        }
        if(flag)
        {
            if(ans){printf("a[1]=%d",arr[1]);}
            for(int i=2;i<=ans;++i){printf(",a[%d]=%d",i,arr[i]);}
            if(ans)printf("\n");
            printf("a[i]=");
            bool fi=true;
            for(int i=1;i<=ans;++i)
            {
                if(ki[i])
                {
                    if(ki[i]>0){if(!fi)printf("+");}
                    else{printf("-");}
                    if(abs(ki[i])!=1){printf("%lld*a[i-%d]",abs(ki[i]),i);}
                    else{printf("a[i-%d]",i);}
                    fi=false;
                }
            }
            if(ki[ans+4])
            {
                if(ki[ans+4]>0){if(!fi)printf("+");}
                else{printf("-");}
                if(abs(ki[ans+4])!=1){printf("%lld*i*i*i",abs(ki[ans+4]));}
                else{printf("i*i*i");}
                fi=false;
            }
            if(ki[ans+3])
            {
                if(ki[ans+3]>0){if(!fi)printf("+");}
                else{printf("-");}
                if(abs(ki[ans+3])!=1){printf("%lld*i*i",abs(ki[ans+3]));}
                else{printf("i*i");}
                fi=false;
            }
            if(ki[ans+2])
            {
                if(ki[ans+2]>0){if(!fi)printf("+");}
                else{printf("-");}
                if(abs(ki[ans+2])!=1){printf("%lld*i",abs(ki[ans+2]));}
                else{printf("i");}
                fi=false;
            }
            if(ki[ans+1])
            {
                if(ki[ans+1]>0){if(!fi)printf("+");} 
                else{printf("-");}
                printf("%lld",abs(ki[ans+1]));
                fi=false;
            }
            if(fi)printf("0");
            printf("\n");
        }
        else{printf("No_solution\n");}
    }
    return 0;
}

上一题

© 2024 nowcoder.com