NOI2002Robot
Description
Input
Output
Sample Input
3
2 1
3 2
5 1
2 1
3 2
5 1
Sample Output
8
6
75
6
75
HINT
90号机器人有10个老师，加上它自己共11个。其中政客只有15号；军人有3号和5号；学者有8个，它们的编号分别是：2,6,9,10,18,30,45,90。
题解
为何我觉得这题十分恶心
f[i][0]表示前i个因数（不含2）的乘积m和它的老师中政客的独立数之和（包括自己）
f[i][1]表示前i个因数（不含2）的乘积m和它的老师中军人的独立数之和（包括自己）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include<iostream> #include<cstdio> #define mod 10000 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();} return x*f; } int n,m=1; int f[1005][2];//偶数，奇数 int p[1005],e[1005]; int a[1005]; int mul(int x,int y) { int ans=1; while(y) { if(y&1)ans=(ans*x)%mod; x=x*x%mod; y>>=1; } return ans; } int main() { n=read(); f[1][0]=1; for(int i=1;i<=n;i++) { p[i]=read();e[i]=read(); m=m*mul(p[i],e[i])%mod; if(p[i]!=2)a[++a[0]]=p[i]; } m--; f[1][0]=1;f[1][1]=a[1]-1; for(int i=2;i<=a[0];i++) { f[i][0]=(f[i-1][1]*(a[i]-1)+f[i-1][0])%mod; f[i][1]=(f[i-1][0]*(a[i]-1)+f[i-1][1])%mod; } f[a[0]][0]--; printf("%d\n",(mod+f[a[0]][0])%mod); printf("%d\n",(mod+f[a[0]][1])%mod); printf("%d\n",(2*mod+m-f[a[0]][1]-f[a[0]][0])%mod); return 0; } |
计数器 9854720
OI 课件=>
OI 课件=>
f[a[0]][0]–是什么意思？