[Codeforces] 475C Alternating Sum
題目連結： http://codeforces.com/contest/964/problem/C 我最近DEBUG能力明顯下降，思緒不清晰......。 以ｋ個做為一個循環，用1+x+x^2+...甚麼的那個公式，然後亂做就好了。 #include<bits/stdc++.h> # define int long long # define MOD 1000000009ll using namespace std ; int n,a,b,k; string s; inline int add (int aa,int bb) { aa += bb; aa %= MOD; if(aa<0) aa += MOD; return aa; } inline int mul (int aa,int bb) { aa *= bb; aa %= MOD; return add( aa,0); } inline int fast (int a,int b=MOD-2) { int res = 1; while(b) { if(b&1) res = mul( res,a); b >>= 1; a = mul( a,a); } return res; } signed main () { cin >> n >> a >> b >> k >> s; int ans = 0, neg = 0; for(int i = 0; i < k; i++) { neg = (s[i] == '+')?1:-1; ans = add( ans,neg* fast ( a,n-i)* fast ( b,i)); } int inv_a = fast( a); a = mul( fast ( inv_a,k), fast ( b,k)); int _ = (n+1)/k; if(a == 1) ans ...