开通网站后,中国建设银行电话,网站建设 推广400电话,站长之家是干嘛的G - Eating Plan
题意#xff1a;
一个1到n组成的排列#xff0c;每个数的价值为其阶乘#xff0c;有m个询问ki#xff0c;要求你在排列中选取连续的一块#xff0c;使得价值和mod 998857459 后#xff0c;大于ki#xff0c;问最短区间长度#xff0c;如果不存在输出…G - Eating Plan
题意
一个1到n组成的排列每个数的价值为其阶乘有m个询问ki要求你在排列中选取连续的一块使得价值和mod 998857459 后大于ki问最短区间长度如果不存在输出-1
题解
t998857459我们对t进行质因数分解发现t 461 * 773 * 2803 因为每个数的价值为其阶乘也就是说如果数2803那么mod t 就等于0也就是大于2803的数对答案没有贡献了所以我们直接两重循环暴力求出所有区间的价值和然后找到个数最小的
代码
#include iostream
#include cstring
#include cstdio
using namespace std;
typedef long long ll;
const int N1e55;
const int mod998857459;
const int inf0x3f3f3f3f;
int cnt;
struct node{ll val;int id;
}res[2900];
ll sum[2900],ans[N],jc[N],a[N],n,m;
int main()
{memset(a,0,sizeof(a));memset(ans,0,sizeof(ans));jc[0]1;for(ll i1;i2803;i)jc[i](jc[i-1]*i)%mod;//阶乘scanf(%d%d,n,m);for(int i1;in;i){int x;scanf(%d,x);a[i]jc[x];//赋值 }sum[0]0;for(int i1;in;i){if(a[i]){res[cnt].vala[i];res[cnt].idi;sum[cnt]sum[cnt-1]res[cnt].val%mod;}}///暴力求出每个区间长度的最小子段和for(int i1;icnt;i){for(int ji;jcnt;j){ans[res[j].id-res[i].id1]max(ans[res[j].id-res[i].id1],(sum[j]-sum[i-1])%mod);}}while(m--){ll x;scanf(%lld,x);int leninf;for(int i1;in;i)if(ans[i]x){//ans[x]表示区间长度为x的最大价值 leni;break;}if(leninf)printf(-1\n);elseprintf(%d\n,len);}return 0;
}
