UOJ 外星人

题目：

2044年，Picks建成了人类第一台基于量子理论的银河系信息传递机。Picks游遍了宇宙，雇用了n个外星人来帮他作为信息传递机的中转站。我们将外星人依次编号为1 到n，其中i 号外星人有ai 根手指。外星人都是很低级的，于是Picks花费了很大的精力，才教会他们学会扳手指数数。Picks现在准备传递x 个脉冲信号给VFleaKing，于是他把信号发给1号外星人，然后1号外星人把信号发送给2号外星人，2号外星人把信号发送给3号外星人，依次类推，最后n号外星人把信号发给VFleaKing。但是事情没有Picks想象的那么顺利，由于外星人手指个数有限，所以如果i 号外星人收到了t 个脉冲信号，他会错误的以为发送过来的是tmodai 个脉冲信号，导致只发送了tmodai个脉冲信号出去。Picks希望他发送出去的脉冲信号数量x 与VFleaKing收到的脉冲信号数量y 的差的绝对值尽量小。于是他决定通过重新排列这些外星人的顺序来达到这一目的。请你求出与x 之差最小的y。除此之外，请求出有多少种排列外星人的方式能达到最优解，你只需要输出方案数对998244353（7×17×223+1，一个质数）取模后的结果。

分析：

先把元素从大到小排序，对于新出现的最小值点ai就是关键点。设dp[i][j]为对前i个数取模后余数为j的方案数。当ai为关键点时状态转移方程为：dp[i][j%a[i]]+=dp[i-1][j]，当ai为非关键点时状态转移方程为dp[i][j]+=(n-1)*dp[i-1][j]。

#include <iostream>

#include <string>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <vector>

#include <queue>

#define range(i,a,b) for(int i=a;i<=b;++i)

#define LL long long

#define rerange(i,a,b) for(int i=a;i>=b;--i)

#define fill(arr,tmp) memset(arr,tmp,sizeof(arr))

using namespace std;

int n,d,a[],dp[][];

const int DEV=;

bool cmp(int a,int b){

    return a>b;

}

void init(){

    cin>>n>>d;

    range(i,,n)cin>>a[i];

    sort(a+,a++n,cmp);

    dp[][d]=;

}

void solve(){

    range(i,,n){

        range(j,,d)dp[i][j]=((LL)dp[i][j]+(LL)dp[i-][j]*(n-i)%DEV)%DEV;

        range(j,,d)dp[i][j%a[i]]=((LL)dp[i][j%a[i]]+dp[i-][j])%DEV;

    }

    rerange(i,a[n]-,)if(dp[n][i]){

        cout<<i<<endl<<dp[n][i]<<endl;

        break;

    }

}

int main() {

    init();

    solve();

    return ;

}

巴特西

UOJ 外星人

最新文章

热门文章