[ 每 日 一 题]AcWing 3800. 奇数还是偶数

目录

• 前言
• 思路
• 总结
• CODE

前言

基础优化— 反向思维

(太久没做了 都忘了 阿巴阿巴)

思路

对于一个数的奇偶性 我们只需要看个位数即可

因为k比较大 所以我们只能考虑个位数

然后就普通的走一遍模拟

但是仔细思考会发现 我们这个复杂度是 O(k* k *t) 1e11的级别去了

（但是写的时候一直没发现 脑中给自己下了一个 O(t * k) 的 想法 ）

那么怎么样才能少一层k呢 ?

按照dp的思想

把之前的 用来推现在的

也就是我们可以 通过 k(1) -> k(2) 所以我们就没必要每次都 求 b(k-1)…

总结

好久没写代码了 (虽然多校有再写 但是没补)

都忘记要先确定时间复杂度再做题了 QAQ

下次记得看准时间复杂度

CODE

#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
const int N = 1e5+10;
int a[N];
void solve()
{
   int b,k;
   cin>>b>>k;
   int ans = 0 ;
   int t = 1;
   
   for(int i = 0 ;i<k;i++)
   cin>>a[i];

   
   ///将公式反过来了
   for(int i  = 0;i<k;i++)
   {
     ans = (ans+t*a[k-1-i])%10;
     t= t*b%10; ///反过来的公式正好可以 每次都对b(k-1) 求尾数
   }
   
   if(ans&1)
   cout<<"odd"<<endl;
   else
   cout<<"even"<<endl;
}
int main(void)
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t -- )
        solve();
}