兼职 网站建设,如何生成链接,免费做情网站,广东省建设监理协会网站http://acm.whu.edu.cn/land/problem/detail?problem_id1470 大概是给你一个队列,每次移动队头的数到队尾并减1,如果本身这个数为1就删去. 然后ans 这个数 * (队列长度-1),求最小的ans 只要最小的元素最先删除就能保证结果最小 解法: 先对原数列排序 然后模拟原操作 ...但是…http://acm.whu.edu.cn/land/problem/detail?problem_id1470 大概是给你一个队列,每次移动队头的数到队尾并减1,如果本身这个数为1就删去. 然后ans 这个数 * (队列长度-1),求最小的ans 只要最小的元素最先删除就能保证结果最小 解法: 先对原数列排序 然后模拟原操作 ...但是t[i] 太大 .显然不能一个个的模拟...其实稍微推一下就能得出 每次到达能删除元素的时候 整个队列循环了t[i]-1次... 我们维护一下后缀和suffix...就能得到这个公式: 前面等差数列,后面等差数列O(1)就能求出 总共n个数,总共O(n) Notice : 等差数列里面/2不能随意取模,我们要对2求1e97的逆元再取模 过程举例: 2 3 4 5 6 第一轮: 2 3 4 5 6 to 1 2 3 4 5 第二轮: 2 3 4 5 to 1 2 3 4 第三轮: 2 3 4 to 1 2 3 第四轮: 2 3 to 2 第五轮: 2 (结果懒得写了...自己可以拍一下) /********************* Template ************************/
#include set
#include map
#include list
#include cmath
#include ctime
#include deque
#include queue
#include stack
#include bitset
#include cstdio
#include string
#include vector
#include cassert
#include cstdlib
#include cstring
#include sstream
#include fstream
#include numeric
#include iomanip
#include iostream
#include algorithm
#include functional
using namespace std;#define EPS 1e-8
#define MAXN 100005
#define MOD ((int)1e97)
#define PI acos(-1.0)
#define DINF (1e10)
#define LINF ((1LL)50)
#define INF (0x3f3f3f3f)
#define max(a,b) ((a) (b) ? (a) : (b))
#define min(a,b) ((a) (b) ? (a) : (b))
#define max3(a,b,c) (max(max(a,b),c))
#define min3(a,b,c) (min(min(a,b),c))
#define BUG coutBUG! endl
#define line cout--------------endl
#define L(t) (t 1)
#define R(t) (t 1 | 1)
#define Mid(a,b) ((a b) 1)
#define lowbit(a) (a -a)
#define FIN freopen(in.txt,r,stdin)
#define FOUT freopen(out.txt,w,stdout)
#pragma comment (linker,/STACK:102400000,102400000)typedef long long LL;
typedef unsigned long long ULL;
// typedef __int64 LL;
// typedef unisigned __int64 ULL;
// LL gcd(LL a,LL b){ return b?gcd(b,a%b):a; }
// LL lcm(LL a,LL b){ return a*b/gcd(a,b); }/********************* F ************************/
LL suf;
LL a[MAXN];
LL r2 (1000000007)/21;
int main()
{int T;scanf(%d,T);int cas 1;for(int cas 1; cas T; cas){suf 0;int n,num;scanf(%d,n);num n-1;for(int i 0 ; i n ; i)scanf(%lld,a[i]);sort(a,an);for(int i 1 ; i n ; i){suf a[i];}LL res 0;LL ct 0;for(int i 0 ; i n-1 ; i){a[i] a[i] - ct;res (res ((a[i]1)%MOD*a[i]%MOD*r2%MOD*num%MOD))%MOD;int cnt a[i] - 1;if(cnt 0){LL sum (suf (suf - (cnt-1) * num)) % MOD * cnt % MOD * r2 % MOD;res (res (sum*num)%MOD) % MOD;}suf - (num * cnt);suf suf - ((a[i1]-ct) - cnt);num--;ct cnt;}printf(Case %d: ,cas);printf(%lld\n,res);}return 0;
} 转载于:https://www.cnblogs.com/Felix-F/p/3279689.html
