首页 > 代码库 > 第一周 8.29 - 9.4

第一周 8.29 - 9.4

2024-08-11 04:34:26   221人阅读

开学了>_<

8.29

Round B APAC Test 2017

B. Sherlock and Watson Gym Secrets

昨天下午做了下 g 家的笔试..真的好菜啊..差好远..好好补下题叭

给出 n,A,B,k ，使得( i^A + j^B) % k == 0 的 i ，j 有多少对(i != j , 1 <= i <= n , 1 <= j <= n)

可以按照 模 k 的余数分类

然后 将 两边的余数 组合起来

cnt[x] * cnt[k-x] (0 <= x <= k-1)，再将 i = j 的统计出来 减掉

好多地方都要取模..找好久错

技术分享
 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 typedef long long LL; 7 const LL mod = 1e9+7; 8 const int maxn = 1e6+5; 9 LL A,B,k,n;10 LL ca[maxn],cb[maxn],cc[maxn];11 LL cnt[maxn];12 13 LL qpow(LL a, LL b,LL MOD)14 {15     LL ret = 1LL;16     while(b)17     {18         if(b & 1) ret = ret * a % MOD;19         a = a * a % MOD;20         b >>= 1;21     }22     return ret;23 }24 25 void solve(){26     LL tot = n/k;27     LL yu = n%k;28     for(int i = 1;i <= k;i++){29         cnt[i%k] = tot;30         if(i <= yu) cnt[i%k]++;31         cnt[i%k] = (cnt[i%k]+mod) % mod;32     }33     for(int i = 1;i <= min(n,k);i++){34         int l = qpow(i,A,k) % k;35         int r = qpow(i,B,k) % k;36         ca[l] = (ca[l] + cnt[i%k]) % mod;37         cb[r] = (cb[r] + cnt[i%k]) % mod;38         if((l+r) % k == 0){39             cc[i%k] = (cc[i%k]+cnt[i%k]) % mod;40         }41     }42     43     /*for(int i = 0;i <= k;i++){44         printf("cnt[%d] = %I64d ca[%d] = %I64d cb[%d] = %I64d cc[%d] = %I64d\n",i,cnt[i],i,ca[i],i,cb[i],i,cc[i]);45     }*/46 47     LL ans = 0;48     for(int i = 0;i < k;i++){49         int l = i;l = l%k;50         int r = k-i;r = r%k;51         LL tmp = (ca[l]*cb[r])%mod;52         ans = (ans+tmp) % mod;53         ans = (ans-cc[i%k]+mod) % mod;54     }55     printf("%I64d\n",ans);56 }57 58 int main(){59     int T,kase = 0;60     freopen("B-large-practice.in","r",stdin);61     freopen("output.out","w",stdout);62     scanf("%d",&T);63     while(T--){64         scanf("%I64d %I64d %I64d %I64d",&A,&B,&n,&k);65         printf("Case #%d: ",++kase);66         memset(ca,0LL,sizeof(ca));67         memset(cb,0LL,sizeof(cb));68         memset(cc,0LL,sizeof(cc));69         memset(cnt,0LL,sizeof(cnt));70         solve();71     }72     return 0;73 }
View Code

 

第一周 8.29 - 9.4


联系
我们