stone
有 \(n\) 枚符石，第 \(i\) 枚符石参数为正整数 \(a_i,b_i\)，初始充能槽能量 \(s=0\)，放入一枚符石时产生 \(s\cdot b_i\) 的损耗，之后 \(s\) 变为 \(s+a_i\)，可以任意安排放入顺序，求最小总损耗下的方案数，对 \(1000000007\) 取模，同时输出最优顺序中字典序最小的编号序列。数据范围：\(1 \le n \le 2\times 10^5\)，\(1 \le a_i,b_i \le 10^4\)。
Key Observation：相邻两个元素产生的贡献只跟这两个元素有关，跟前面的无关，于是可以尝试邻项交换推导贪心策略。
设原有能量为 \(s\)，相邻两个石头一、二的权值分别为 \((a_1,b_1),(a_2,b_2)\)。则：
- 先一后二：\(\Delta s_1=s_0b_1+(s_0+a_1)b_2=s_0b_1+s_0b_2+a_1b_2\)
- 先二后一：\(\Delta s_2=s_0b_2+(s_0+a_2)b_1=s_0b_1+s_0b_2+a_2b_1\)
发现 \(a_1b_2,a_2b_1\) 是这两种方案的区别，直接按照 \(a_1b_2<a_2b_1\) 排序即可，注意相同时按照编号小的在前面。
计数也非常简单，容易发现连续 \(k\) 个满足 \(a_{i-1}b_{i}=a_{i}b_{i-1}\) 的 \(i(1 \le i < n)\) 可产生 \(k!\) 的贡献，每个连续段相互独立，用乘法原理。
时间复杂度 \(O(n \log n)\).
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N=2e5+7;
constexpr ll mod=1e9+7;
int n; ll ans=1,fac[N];
struct node{ll a,b;int id;}p[N];
ll calc()
{ll res=0,s=0;for(int i=1;i<=n;i++){res+=s*p[i].b;s+=p[i].a;}return res;
}
int main()
{freopen("stone.in","r",stdin);freopen("stone.out","w",stdout);cin.tie(0)->sync_with_stdio(0);cin>>n;fac[1]=1;for(int i=2;i<=n+2;i++) fac[i]=(fac[i-1]*i)%mod;for(int i=1;i<=n;i++) cin>>p[i].a>>p[i].b;for(int i=1;i<=n;i++) p[i].id=i;sort(p+1,p+n+1,[&](node A,node B){if(A.a*B.b==B.a*A.b) return A.id<B.id;else return A.a*B.b<B.a*A.b;});cout<<calc()<<" ";// for(int i=1;i<=n;i++) cerr<<p[i].a<<" "<<p[i].b<<"\n";ll continuous=0; //连续for(int i=2;i<=n;i++){if(p[i-1].a*p[i].b==p[i].a*p[i-1].b){// cerr<<i<<endl;continuous++;}else{ans=(ans*fac[continuous+1])%mod;// cerr<<"contribution"<<continuous+1<<'\n';continuous=0;}// cerr<<continuous<<' '<<fac[continuous+1]<<'\n';}ans=(ans*fac[continuous+1])%mod;cout<<ans<<"\n";for(int i=1;i<=n;i++) cout<<p[i].id<<" \n"[i==n];cout.flush();return 0;
}
/*
整场比赛策略：T1正解+对拍 -> T2T3T4暴力 -> T2正解Observations：
1.a[i]相同时，按照b[i]从大到小的顺序放置,b[i]相同时，按照a[i]从小到大的顺序排序
2.相邻两个元素产生的贡献只跟这两个元素有关，跟前面的无关？假设原始有s0能量，然后有两个(a1,b1),(a2,b2)
先一后二：Δs=s0*b1+(s0+a1)*b2
先二后一：Δs=s0*b2+(s0+a2)*b1展开后都包含s0b1+s0b2项，唯一有区别的是第一个有a1b2，第二个有a2b1！！！
贪心正解就如同探囊取物a1b2=a2b1的相邻元素是计数的关键
*/