2020-2021:teams:wangzai_milk:20200808比赛记录

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:wangzai_milk:20200808比赛记录 [2020/08/13 19:53]
infinity37 [F - Groundhog Looking Dowdy]
+++ 2020-2021:teams:wangzai_milk:20200808比赛记录 [2020/08/14 16:23] (当前版本)
wzx27
@@ 行 13: / 行 13: @@
 ===== 题解 =====
+==== A - Groundhog and 2-Power Representation ====
+用栈模拟一下，并且用 $\text{py}$ 水一下高精度
+<hidden code> <code cpp>
+s = input().strip()
+stack = []
+ans = 0
+for ch in s:
+	if ch == ')':
+		now = 0
+		while 1:
+			r = stack[-1]
+			stack.pop()
+			if r == '(':
+				break
+			if r != '+':
+				now += int(r)
+		stack.pop()
+		stack.append(2**now)
+	else:
+		stack.append(ch)
+for each in stack:
+	if each != '+':
+		ans += int(each)
+print(ans)
+</code> </hidden>
+\\
 ==== F - Groundhog Looking Dowdy ====
@@ 行 59: / 行 91: @@
 \\
+==== G - Groundhog Chasing Death ====
+求 $\prod_{i=a}^b \prod_{j=c}^d gcd(x^i,y^j)$。
+只有 $x,y$ 的公共质因子会有贡献，枚举这些质因子，然后枚举 $i$，可以用等差数列求出 $j$ 的贡献。
+<hidden code> <code cpp>
+#pragma GCC optimize(2)
+#pragma GCC optimize(3,"Ofast","inline")
+#include<bits/stdc++.h>
+#define ALL(x) (x).begin(),(x).end()
+#define ll long long
+#define db double
+#define ull unsigned long long
+#define pii_ pair<int,int>
+#define mp_ make_pair
+#define pb push_back
+#define fi first
+#define se second
+#define rep(i,a,b) for(int i=(a);i<=(b);i++)
+#define per(i,a,b) for(int i=(a);i>=(b);i--)
+#define show1(a) cout<<#a<<" = "<<a<<endl
+#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl
+using namespace std;
+const ll INF = 1LL<<60;
+const int inf = 1<<30;
+const int maxn = 1e5+5;
+const int M = 998244353;
+inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
+ll qpow(ll a,ll b) {ll s = 1;while(b){if(b&1)s=(s*a)%M;a=(a*a)%M;b>>=1; }return s;}
+vector<int> cop,X,Y;
+int main()
+{
+    fastio();
+    ll a,b,c,d,x,y;
+    cin>>a>>b>>c>>d>>x>>y;
+    //if(!a) a++; if(!b) b++;
+    //if(!c) c++; if(!d) d++;
+    int sqn = 1e5;
+    rep(i,2,sqn){
+        int t1 = 0,t2 = 0;
+        if(i > x && i > y) break;
+        while(x%i==0) x/=i,t1++;
+        while(y%i==0) y/=i,t2++;
+        if(t1 && t2){
+            cop.pb(i);
+            X.pb(t1);
+            Y.pb(t2);
+        }
+    }
+    if(x>1 && y>1 && x==y){
+        cop.pb(x);
+        X.pb(1);
+        Y.pb(1);
+    }
+    int sz = X.size();
+    ll ans = 1;
+    ll M1 = M-1;
+    rep(k,0,sz-1){
+        ll u = X[k],v = Y[k];
+        ll sum = 0;
+        rep(i,a,b){
+            ll un = u*i;
+            ll lim = un / v;
+            if(lim>=d){
+                sum += (c+d)*(d-c+1)/2 * v;
+                sum %= M1;
+            }else if(lim<c){
+                sum += (d-c+1) * un;
+                sum %= M1;
+            }else{
+                sum += (c+lim)*(lim-c+1)/2 * v + (d-lim)*un;
+                sum %=M1;
+            }
+        }
+        ans = ans * qpow(cop[k],sum) % M;
+    }
+    cout<<ans<<endl;
+    return 0;
+}
+/*
+3000000 0 3000000 223092870 223092870
+*/
+</code> </hidden>
+\\
 ==== K - The Flee Plan of Groundhog ====

2020-2021/teams/wangzai_milk/20200808比赛记录.1597319637.txt.gz · 最后更改: 2020/08/13 19:53 由 infinity37