tokitsukaze and Unlimited Array

NC21194. tokitsukaze and Unlimited Array

描述

I am the bone of my number.
Variable is my structure, and function is my member.
I have created over a thousand array.
Unknown to infinity.
Nor known to endless.
Have withstood pain to create many number.
Yet, those hands will never hold anything.
So as I pray, Unlimited Array Works.

tokitsukaze有一个n次多项式函数F(x)。

她按照如下规则定义了一个二维无限数组。

tokitsukaze发现，由任意一个n次多项式函数F(x)确定出的这个无限数组，无穷级数

总是收敛的。
求无穷级数

的和，为了避免这个数过于庞大，你只用输出级数和mod 1000000007后的结果即可。

输入描述

第一行是两个整数n(0≤n≤10^9)表示多项式函数F(x)的最高次数。m(1≤m≤100)表示多项式函数的项数。
接下来一行共2*m个非负整数，这2*m个非负整数分为m组，每组两个非负整数。
对于每一组：第一个整数x(1≤x≤10^9)表示该项的系数，第二个整数y(0≤y≤n)代表该项的次数。
输入数据保证F(x)的最高次项系数不为0且次数为n，保证次数唯一，不保证输入多项式的幂次是递减的。
例如当n=3,m=3时，则输入6个非负整数，如：4 3 2 2 5 0，表示多项式函数F(x)=4x^3+2x^2+5。

输出描述

对于每一组案例,输出一行一个非负整数，表示级数和mod 1000000007后的结果。

示例1

输入:

3 3
4 3 2 2 5 0

输出:

说明:

F(x)=4x^3+2x^2+5
a[0]=5,11,45,131,293,555,941,1475,2181,3083,4205,5571,7205,9131,11373……(这里仅给出一部分)
a[1]=5,6,34,86,162,262,386,534,706,902,1122,1366,1634,1926,2242,2582……(这里仅给出一部分)
a[2]=5,1,28,52,76,100,124,148,172,196,220,244,268,292,316,340,364,388……(这里仅给出一部分)
a[3]=5,-4,27,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24……(这里仅给出一部分)
a[4]=5,-9,31,-3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0……(这里仅给出一部分，并且后面都是0)
所以

=5-9+31-3=24

原站题解

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

C++14(g++5.4) 解法, 执行用时: 838ms, 内存消耗: 504K, 提交时间: 2018-12-07 23:30:02

#include<bits/stdc++.h>
int mod=1e9+7;
int f[]={1,927880474,933245637,668123525,429277690,733333339,724464507,957939114,203191898,586445753,698611116};
int main()
{
    int n,m,a,b,k;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        if(b==n) k=a;
    }
    int ans=f[n/100000000];
    for(int i=n-n%100000000+1;i<=n;i++) ans=1LL*ans*i%mod;
    printf("%lld\n",1LL*ans*k%mod);
}

C++11(clang++ 3.9) 解法, 执行用时: 858ms, 内存消耗: 488K, 提交时间: 2020-03-15 18:01:03

#include<bits/stdc++.h>
int mod=1e9+7;
int f[]={1,927880474,933245637,668123525,429277690,733333339,724464507,957939114,203191898,586445753,698611116};
int main()
{
	int n,m,a,b,k;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		if(b==n) k=a;
	}
	int ans=f[n/100000000];
	for(int i=n-n%100000000+1;i<=n;i++)
	ans=1LL*ans*i%mod;
	printf("%lld\n",1LL*ans*k%mod);
}

上一题

下一题

详情