BZOJ 3823 定情信物

VictorWonder posted @ 2015年1月05日 15:22 in BZOJ with tags 解题报告 数论 递推 乘法逆元 , 1647 阅读
这道题目刚出来的时候(大概是十二月二十七八日左右)觉得特别水,花了一点时间做了出来,谁知道最后还是被卡掉了……我的AC率啊!!!
 
于是稍稍推了一下递推式。
点动成线,所以一条线有两个点,线动成面,所以一个面有四条线,面的两边各有一条线,而两侧由于点的运动,又多了两条线。
面动成体,正对着的有两个面了,四周由于四条边在动,形成了四个新的面……
这样下去,一个k(k>0)维超正方体是由k*2个k-1维超正方体组成的。
还有一个规律,对于一个k维超正方体来说,k维的超正方体有1个,k-1维的超正方体有k*2个。
但是k-2维的超正方体并非k*2*(k-1)*2个,因为每两个k-1维超正方体之间都有2个k-2维的超正方体相交,所以要除以2,相对应的,k-3维超正方体=k-2维超正方体的数目*(k-2)*2/3……
但是,这道题最主要的问题是取模,有除法,所以需要求逆元,但是,用exgcd求逆元是O(log n)的,不过,Claris向我提供了一份O(n)求出所有逆元的代码,到目前为止,我还没有搞清楚这段代码的原理TAT
我怕这道题目变成权限题,于是马上就提交了这题,结果,有人加强了一下数据,把大多数人都卡掉了,于是我整个人就顿时不好了。
原来,还有一种神奇的情况就是,维数是模数的倍数,那么就不能求逆元了,我立马就束手无策了,好在Claris提供了帮助,对于一个数x,如果[tex]x=p*mod^k[/tex],那么我们就不用管mod,将其逆元当作是p的逆元,递推的时候,再计算一下,当前的答案是否为mod的倍数,如果是mod的倍数的话,那么答案就是0,否则答案就是我们求出来的值。另外,如果模的数是2的话,发现答案永远是1,可以特判加速。
具体的可以看一下代码。
PS:这种时候,递推式算好像比通项公式要快。
 
UPD:关于线性递推求逆元的证明
    对于一个数i,其逆元inv[i]满足i*inv[i]%P=1
    设P=i*j+k,则j=P/i,k=P%i
    所以i=(P-k)/j%P=-k/j
    那么,inv[i]=1/i=-j/k=-j*inv[k]
    证毕
 
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=10001000;
int n,x,num;
ll t,last,ans=1,mod;
int r[N],a[N];
char c[N];
int main() {
    int i;
    scanf("%d%lld",&n,&mod);
    if (mod==2) return puts("1"),0;
    for(r[1]=a[1]=1,i=2;i<=n;i++) if (i%mod==0) {
        x=i;
        while (x%mod==0) {
            c[i]++;
            x/=mod;
        } r[i]=r[a[i]=x];
    } else {
        a[i]=i;
        if (i>=mod) r[i]=r[i%mod];
        else {
            r[i]=-(ll)r[mod%i]*(mod/i)%mod;
            while (r[i]<0) r[i]+=mod;
        }
    }
    for (last=i=1;i<=n;i++) {
        last=(((last*a[n-i+1]%mod)<<1)%mod)*r[i]%mod;
        num+=c[n-i+1]-c[i];
        if (!num) ans^=last;
    } cout<<ans<<endl;
    return 0;
}

 

MP Plus One Previous 说:
2022年8月16日 22:01

The Intermediate education system in this State is governed and controlled by the MP board. Additionally, it addresses numerous educational tasks including setting curriculum, holding tests, and accrediting universities. All of the educational institutions in this state are likewise governed and managed by this board. MP Plus One Previous Paper 2023 The MP Plus One Previous Paper 2023 for these examinations will be available very soon on the official website of MP Board, which is the board that administers the 9th+2 test each year. In the previous academic year (2013), the MP Board Class 11th examinations were also held. MP Plus One Previous Paper 2023 The procedures listed below would be extremely helpful for checking the MP Board Class 11th Important Question Paper 2023.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter